算法問題 用PL/SQL寫出當(dāng)M*N時的螺旋矩陣算法
如下是一個4*4的矩陣:
1 12 11 10
2 13 16? 9
3 14 15? 8
4? 5? 6? 7
按照上面矩陣的規(guī)律, 請用PL/SQL寫出當(dāng)M*N時的矩陣算法
1996年我考程序員時候見過類似問題
代碼:--------------------------------------------------------------------------------
試題三
閱讀以下程序說明和C程序，將應(yīng)填入程序中 （n） 處的字句，寫在答卷的對應(yīng)欄內(nèi)。
[程序說明]
本程序?qū)⒆匀粩?shù) 1，2，……，N2 按蛇形方式逐個順序存入 N 階矩陣。 例如，當(dāng) 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）順序填入自然數(shù)，交替地對每一斜列從左上元素向右下元素或從右下元素向左上元素存數(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
? --尋找"下一個位置"
? 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
---------------
再包一層，多玩點花樣：
代碼:--------------------------------------------------------------------------------
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
?
??? --尋找"下一個位置"
??? 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
?
??? --尋找"下一個位置"
??? 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???????????????????????????????
---