posts - 189,comments - 115,trackbacks - 0
题 用PL/SQL写出当M*N时的螺旋矩阵算法   

算法问题 用PL/SQL写出当M*N时的螺旋矩阵算法
如下是一个4*4的矩阵:

1 12 11 10
2 13 16  9
3 14 15  8
4  5  6  7

按照上面矩阵的规律, 请用PL/SQL写出当M*N时的矩阵算法

1996年我考程序员时候见过类似问题

代码:--------------------------------------------------------------------------------
试题三
  阅读以下程序说明和C程序,将应填入程序中 (n) 处的字句,写在答卷的对应栏内。

[程序说明]
  本程序将自然数 1,2,……,N2 按蛇形方式逐个顺序存入 N 阶矩阵。 例如,当 N = 3 和 4 时分别如图 3.1 和图 3.2。
                       7  13  14  16
              6  7  9     6  8  12  15
              2  5  8     2  5  9  11
              1  3  4     1  3  4  10
               图3.1       图3.2
从 an0 开始到 a0n 为止(n = N-1)顺序填入自然数,交替地对每一斜列从左上元素向右下元素或从右下元素向左上元素存数。

[程序]
#include
#define SIZE 10
int a[SIZE] [SIZE], k;
main()
{ int i, j, n, N;
for (N = 3;N<=SIZE; N++)
{ k = 1;
makeArray (n = N-1);
printf ("nN = %d;n",n+1);
for (i = 0;i<=n; i++)
{ for (j = 0; j<=n; j++)printf("%4d",a[i][j]);
printf ("n");
}
}
}
makeline (int row_start, int col_start, int row_end)
{ /*完成矩阵一条斜线的整数填写*/
int i, j, sign = ____(1)____;
for (i = row_start, j = col_start;____(2)____ >=0; i += sign,j += sign)
a[i][j] = k++;
}
makeArray (int n)
{ /* 完成矩阵每条斜线的整数填写*/
int d;
for (d = 1; d <= ___(3)___; d++)
if (d <= n);
if (d%2) makeline (____(4)____); else makeline(____(5)____);
else
if (d%2) makeline (____(6)____); else makeline(____(7)____);
}

PL?SQL
代码:--------------------------------------------------------------------------------
declare
  type t_matrix is table of number index by binary_integer;
  v_helix   t_matrix;
  i         number;
  j         number;
  direction pls_integer; -- right:0, up:1, left:2, down:3
  M         number;
  N         number;
 
  -- 模拟2维数组 begin
  function new_matrix (rows integer, cols integer) return t_matrix is
    v_result t_matrix;
  begin
    v_result(0):=cols;
    for i in 1 .. rows*cols loop
        v_result(i) := null;
    end loop;
    return v_result;
  end;

  procedure set_val(p_matrix in out t_matrix, i integer, j integer, val number) is
  begin
    p_matrix( (i-1)* p_matrix(0) +j ) := val;
  end;
 
  function get_val(p_matrix t_matrix, i integer, j integer) return number is
  begin
    return p_matrix( (i-1)* p_matrix(0) +j );
  end;

  procedure print_matrix(m t_matrix) is
    i integer;
    j integer;
  begin
    for i in 1 .. m.count/m(0) loop
      for j in 1 .. m(0) loop
        dbms_output.put(to_char(m((i-1)*m(0)+j),'9999990'));
      end loop;
      dbms_output.new_line;
    end loop;
  end;
  -- 模拟2维数组 end

  --寻找"下一个位置"
  function go_next
  (
    p_helix  in out t_matrix,
    p_i      in out number,
    p_j      in out number,
    p_dir    in out pls_integer,
    p_altdir char
  ) return boolean is
    dir_offset constant varchar2(16) := '+0+1-1+0+0-1+1+0'; -- i,j offset in each direction
    ii    number;
    jj    number;
    times pls_integer := 0;
  begin
    loop
      ii    := p_i + substr(dir_offset, p_dir * 4 + 1, 2);
      jj    := p_j + substr(dir_offset, p_dir * 4 + 2 + 1, 2);
      times := times + 1;
   
      exit when(ii between 1 and p_helix.count/p_helix(0)
               and jj between 1 and p_helix(0)
               and get_val(p_helix,ii,jj) is null);
   
      if times >= 4 then
        return false;
      end if;
      if p_altdir = 'L' then      -- turn left
        p_dir := mod(p_dir + 1, 4);
      elsif p_altdir = 'R' then   -- turn right
        p_dir := mod(p_dir + 3, 4);
      end if;
    end loop;
    p_i := ii;
    p_j := jj;
    return true;
  end;

--主程序
begin
  M := 4;
  N := 5;

  v_helix   := new_matrix(M, N);
  i         := 1;
  j         := 1;
  direction := 3;
  for x in 1 .. M * N loop
    set_val(v_helix, i, j,  x);
    exit when not go_next(v_helix, i, j, direction, 'L');
  end loop;
  print_matrix(v_helix);

  --已经完成任务,以下可以叫做画蛇添足:)

  dbms_output.new_line;

  v_helix   := new_matrix(M, N);
  i         := 1;
  j         := 1;
  direction := 0;
  for x in 1 .. M * N loop
    set_val(v_helix, i, j,  x);
    exit when not go_next(v_helix, i, j, direction, 'R');
  end loop;
  print_matrix(v_helix);

  dbms_output.new_line;

  v_helix   := new_matrix(M, N);
  i         := 1;
  j         := 1;
  direction := 3;
  for x in 1 .. M * N loop
    set_val(v_helix, i, j, M*N-x+1);
    exit when not go_next(v_helix, i, j, direction, 'L');
  end loop;
  print_matrix(v_helix);

  dbms_output.new_line;

  v_helix   := new_matrix(M, N);
  i         := 1;
  j         := 1;
  direction := 0;
  for x in 1 .. M * N loop
    set_val(v_helix, i, j, M*N-x+1);
    exit when not go_next(v_helix, i, j, direction, 'R');
  end loop;
  print_matrix(v_helix);
end;

       1      14      13      12      11
       2      15      20      19      10
       3      16      17      18       9
       4       5       6       7       8

       1       2       3       4       5
      14      15      16      17       6
      13      20      19      18       7
      12      11      10       9       8

      20       7       8       9      10
      19       6       1       2      11
      18       5       4       3      12
      17      16      15      14      13

      20      19      18      17      16
       7       6       5       4      15
       8       1       2       3      14
       9      10      11      12      13

---------------
再包一层,多玩点花样:


代码:--------------------------------------------------------------------------------
declare
  procedure draw_helix ( M number, N number, init_i integer, init_j integer, init_dir integer, screw_dir char, asc_order boolean := true) is
    type t_matrix is table of number index by binary_integer;
    v_helix   t_matrix;
    element   number;
    i         integer := init_i;
    j         integer := init_j;
    direction integer := init_dir; -- right:0, up:1, left:2, down:3
 
    -- 模拟2维数组 begin
    function new_matrix( rows integer, cols integer ) return t_matrix is
      v_result t_matrix;
    begin
      v_result(0) := cols;
      for i in 1 .. rows * cols loop
        v_result(i) := null;
      end loop;
      return v_result;
    end;
 
    procedure set_val (p_matrix in out t_matrix, i integer, j integer, val number ) is
    begin
      p_matrix((i - 1) * p_matrix(0) + j) := val;
    end;
 
    function get_val ( p_matrix t_matrix, i integer, j integer ) return number is
     begin
      return p_matrix((i - 1) * p_matrix(0) + j);
    end;
 
    procedure print_matrix(m t_matrix) is
      i integer;
      j integer;
    begin
      for i in 1 .. m.count / m(0) loop
        for j in 1 .. m(0) loop
          dbms_output.put( lpad(nvl(to_char(m((i - 1) * m(0) + j)), ' '), 8, ' ') );
        end loop;
        dbms_output.new_line;
      end loop;
    end;
    -- 模拟2维数组 end
 
    --寻找"下一个位置"
    function go_next (p_helix  in t_matrix, p_i in out number, p_j in out number, p_dir in out pls_integer, p_altdir char) return boolean is
      dir_offset constant varchar2(16) := '+0+1-1+0+0-1+1+0'; -- i,j offset in each direction
      ii    number;
      jj    number;
      times pls_integer := 0;
    begin
      loop
        ii    := p_i + substr(dir_offset, p_dir * 4 + 1, 2);
        jj    := p_j + substr(dir_offset, p_dir * 4 + 2 + 1, 2);
        times := times + 1;
     
        exit when(ii between 1 and p_helix.count / p_helix(0) and jj between 1 and p_helix(0) and
                  get_val(p_helix, ii, jj) is null);
     
        if times >= 4 then
          return false;
        end if;
        if p_altdir = 'L' then
          -- turn left
          p_dir := mod(p_dir + 1, 4);
        elsif p_altdir = 'R' then
          -- turn right
          p_dir := mod(p_dir + 3, 4);
        end if;
      end loop;
      p_i := ii;
      p_j := jj;
      return true;
    end;
    --begin of draw_helix
  begin
    v_helix := new_matrix(M, N);
    for x in 1 .. M*N loop
      if asc_order then
        element := x;
      else
        element := M*N - x + 1;
      end if;
      set_val(v_helix, i, j, element);
      exit when not go_next(v_helix, i, j, direction, screw_dir);
    end loop;
    print_matrix(v_helix);
    dbms_output.new_line;
  end;

--begin of main
begin
  draw_helix(4, 5, 1, 1, 3, 'L', true);
  draw_helix(4, 5, 1, 1, 0, 'R', true);
  draw_helix(4, 5, 1, 1, 3, 'L', false);
  draw_helix(4, 5, 4, 5, 2, 'R', true);
  draw_helix(4, 5, 1, 5, 2, 'L', true);
  draw_helix(4, 5, 1, 5, 3, 'R', false);

  draw_helix(4, 5, 3, 3, 3, 'R', true);
  draw_helix(4, 5, 2, 3, 3, 'R', true);
end;

       1      14      13      12      11
       2      15      20      19      10
       3      16      17      18       9
       4       5       6       7       8

       1       2       3       4       5
      14      15      16      17       6
      13      20      19      18       7
      12      11      10       9       8

      20       7       8       9      10
      19       6       1       2      11
      18       5       4       3      12
      17      16      15      14      13

       8       9      10      11      12
       7      18      19      20      13
       6      17      16      15      14
       5       4       3       2       1

       5       4       3       2       1
       6      17      16      15      14
       7      18      19      20      13
       8       9      10      11      12

      10       9       8       7      20
      11       2       1       6      19
      12       3       4       5      18
      13      14      15      16      17

       7       8       9      10      11
       6      19      18      17      12
       5      20       1      16      13
       4       3       2      15      14

       8       9      10      11      12
       7               1      18      13
       6               2      17      14
       5       4       3      16      15


---
把 dir_offset改一下,就走斜线了


代码:--------------------------------------------------------------------------------
declare
  procedure draw_helix ( M number, N number, init_i integer, init_j integer, init_dir integer, screw_dir char, asc_order boolean := true) is
    type t_matrix is table of number index by binary_integer;
    v_helix   t_matrix;
    element   number;
    i         integer := init_i;
    j         integer := init_j;
    direction integer := init_dir; -- right:0, up:1, left:2, down:3
 
    -- 模拟2维数组 begin
    function new_matrix( rows integer, cols integer ) return t_matrix is
      v_result t_matrix;
    begin
      v_result(0) := cols;
      for i in 1 .. rows * cols loop
        v_result(i) := null;
      end loop;
      return v_result;
    end;
 
    procedure set_val (p_matrix in out t_matrix, i integer, j integer, val number ) is
    begin
      p_matrix((i - 1) * p_matrix(0) + j) := val;
    end;
 
    function get_val ( p_matrix t_matrix, i integer, j integer ) return number is
     begin
      return p_matrix((i - 1) * p_matrix(0) + j);
    end;
 
    procedure print_matrix(m t_matrix) is
      i integer;
      j integer;
    begin
      for i in 1 .. m.count / m(0) loop
        for j in 1 .. m(0) loop
          dbms_output.put( lpad(nvl(to_char(m((i - 1) * m(0) + j)), ' '), 8, ' ') );
        end loop;
        dbms_output.new_line;
      end loop;
    end;
    -- 模拟2维数组 end
 
    --寻找"下一个位置"
    function go_next (p_helix  in t_matrix, p_i in out number, p_j in out number, p_dir in out pls_integer, p_altdir char) return boolean is
      --dir_offset constant varchar2(16) := '+0+1-1+0+0-1+1+0'; -- i,j offset in each direction
      dir_offset constant varchar2(16) := '-1+1-1-1+1-1+1+1'; -- i,j offset in each direction
      ii    number;
      jj    number;
      times pls_integer := 0;
    begin
      loop
        ii    := p_i + substr(dir_offset, p_dir * 4 + 1, 2);
        jj    := p_j + substr(dir_offset, p_dir * 4 + 2 + 1, 2);
        times := times + 1;
     
        exit when(ii between 1 and p_helix.count / p_helix(0) and jj between 1 and p_helix(0) and
                  get_val(p_helix, ii, jj) is null);
     
        if times >= 4 then
          return false;
        end if;
        if p_altdir = 'L' then
          -- turn left
          p_dir := mod(p_dir + 1, 4);
        elsif p_altdir = 'R' then
          -- turn right
          p_dir := mod(p_dir + 3, 4);
        end if;
      end loop;
      p_i := ii;
      p_j := jj;
      return true;
    end;
    --begin of draw_helix
  begin
    v_helix := new_matrix(M, N);
    for x in 1 .. M*N loop
      if asc_order then
        element := x;
      else
        element := M*N - x + 1;
      end if;
      set_val(v_helix, i, j, element);
      exit when not go_next(v_helix, i, j, direction, screw_dir);
    end loop;
    print_matrix(v_helix);
    dbms_output.new_line;
  end;

--begin of main
begin
  draw_helix(9, 9, 1, 5, 3, 'R', true);
end;

                                       1                               
                              16               2                       
                      15              17               3               
              14              24              18               4       
      13              23              25              19               5
              12              22              20               6       
                      11              21               7               
                              10               8                       
                                       9                               


---

posted on 2006-04-07 21:30 MEYE 阅读(675) 评论(0)  编辑  收藏 所属分类: Study

只有注册用户登录后才能发表评论。


网站导航: