# 有趣的算法

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;

--

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;

--

--寻找"下一个位置"

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;

--

--寻找"下一个位置"

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

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;

--

--寻找"下一个位置"

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

SQL实现

SQL> -- 逆时针的

SQL
> select --i,

2 sum(decode(j, 1, rn)) as co11,

3 sum(decode(j, 2, rn)) as co12,

4 sum(decode(j, 3, rn)) as co13,

5 sum(decode(j, 4, rn)) as co14

6 from
(select i, j, rank() over(order by tag) as rn

7 from
(select i,

8 j,

9 -- 逆时针螺旋特征码 counter-clockwise

10
case least(j - 1, 4 - i, 4 - j, i - 1)

11 when j - 1 then

12
(<

• 博文量
6
• 访问量
301968