算法问题 用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
---