算法問(wèn)題 用PL/SQL寫出當(dāng)M*N時(shí)的螺旋矩陣算法
如下是一個(gè)4*4的矩陣:
1 12 11 10
2 13 16? 9
3 14 15? 8
4? 5? 6? 7
按照上面矩陣的規(guī)律, 請(qǐng)用PL/SQL寫出當(dāng)M*N時(shí)的矩陣算法
1996年我考程序員時(shí)候見(jiàn)過(guò)類似問(wèn)題
代碼:--------------------------------------------------------------------------------
試題三
閱讀以下程序說(shuō)明和C程序，將應(yīng)填入程序中 （n） 處的字句，寫在答卷的對(duì)應(yīng)欄內(nèi)。
[程序說(shuō)明]
本程序?qū)⒆匀粩?shù) 1，2，……，N2 按蛇形方式逐個(gè)順序存入 N 階矩陣。 例如，當(dāng) N = 3 和 4 時(shí)分別如圖 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 開(kāi)始到 a0n 為止（n = N-1）順序填入自然數(shù)，交替地對(duì)每一斜列從左上元素向右下元素或從右下元素向左上元素存數(shù)。
[程序]
#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)
{ /*完成矩陣一條斜線的整數(shù)填寫*/
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)
{ /* 完成矩陣每條斜線的整數(shù)填寫*/
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維數(shù)組 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維數(shù)組 end
? --尋找"下一個(gè)位置"
? 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);
? --已經(jīng)完成任務(wù)，以下可以叫做畫蛇添足：）
? 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
---------------
再包一層，多玩點(diǎn)花樣：
代碼:--------------------------------------------------------------------------------
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維數(shù)組 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維數(shù)組 end
?
??? --尋找"下一個(gè)位置"
??? 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維數(shù)組 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維數(shù)組 end
?
??? --尋找"下一個(gè)位置"
??? 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???????????????????????????????
---