算法问题 用SQL写出当M*N时的螺旋矩阵算法如下是一个4*4的矩阵:
1 12 11 102 13 16 93 14 15 84 5 6 7
按照上面矩阵的规律, 请用SQL写出当M*N时的矩阵算法
实现的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 (j - 1) || '1' || i 13 when 4-i then 14 (4 - i) || '2' || j 15 when 4 - j then 16 (4 - j) || '3' || (4 - i) 17 when i - 1 then 18 (i - 1) || '4' || (4 - j) 19 end as tag 20 from (select level as i from dual connect by level <= 4) a, 21 (select level as j from dual connect by level <= 4) b)) 22 group by i 23 /
CO11 CO12 CO13 CO14---------- ---------- ---------- ---------- 1 12 11 10 2 13 16 9 3 14 15 8 4 5 6 7
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 -- 顺时针螺旋特征码 clockwise 10 case least(i - 1, 4 - j, 4 - i, j - 1) 11 when i - 1 then 12 (i - 1) || '1' || j 13 when 4 - j then 14 (4 - j) || '2' || i 15 when 4 - i then 16 (4 - i) || '3' || (4 - j) 17 when j - 1 then 18 (j - 1) || '4' || (4 - i) 19 end as tag 20 from (select level as i from dual connect by level <= 4) a, 21 (select level as j from dual connect by level <= 4) b)) 22 group by i 23 /
CO11 CO12 CO13 CO14---------- ---------- ---------- ---------- 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7
----------------------------------------------------------------------------------------
以上两种旋转都是由外向内的, 如果有兴趣也可以做成由内想外的不过如果大家还要把结果90度旋转, 在顺序固定的情况下, 应该就是行列转换的问题了不过如果要做成圆形的, 我觉得不太可能了, 正n边形倒是可以考虑, 不过要看n的值是多大, 如果趋于正无穷, 那就是圆了, ^_^
对了，jacky，能大概说一下这个螺旋特征码的算法原理么？ --------------------------------------------------------------------------------
螺旋总要有个起点, 就用上面的那个结果来说明吧起点是(1,1), 如果是顺时针的话, 旋转时依次走过的途径是 上->右->下->左->上->右->下->左..., 知道最后在螺旋中心结束, 但是可以注意到旋转是会越来越远离外边界根据这个我们就可以获取螺旋特征码了4*4的矩阵, 那么可以认为 i=1, j=1, i=4, j=4, 这就是这个螺旋的4个边界, 顺时针旋转时, 离边界越近, 那么顺序就越靠前, 当距离边界相同时, 边界的优先级就要根据 上右下左(起点为1,1, 顺时针旋转的边界优先级) 而定了, 如果这个也相同, 那么就要根据这个点离前一个边界的距离而定, 离的越近, 优先级越高, 根据以上规则, 可以得出特征码共有三位, 第一位代表距离边界的距离, 第二位代表距离哪个边界最近(我的sql中用1,2,3,4分别表示四个边界), 第三位代表距离前一个边界的距离(因为目的是为了排序, 计算时没有严格按照这个距离值进行表示^_^)对应上面螺旋特征码的规则, 使用case least(...)判断离边界的距离和距离最近的边界是那个边界, when ... then后的取值再确定距离前一个边界的距离, 这样就完成了特征码, 剩下的就是对特征码排序和行列转换了, 这个就不用说了吧, 大家应该都会了, ^_^
也来学一下JACKYWOOD兄, 写一个SQL:
JACK的实现, 采用了行列转换把生成的序列做成二维表, 所以要求列数是固定的, 若要实现N的矩阵的算法, 行列转换正如其所言, 可以通过二个SQL实现. 现换一下思路, 用SYS_CONNECT_BY_PATH函数, 借用JACK的思路, 实现N的矩阵生成, 如下请各位指点:
代码:--------------------------------------------------------------------------------SQL> var n number;SQL> exec :n := 3;
PL/SQL 过程已成功完成。
SQL> select replace(max(sys_connect_by_path(rank, ',')), ',') str 2 from (select i, j, 3 to_char(rank() over(order by tag), '9999') as rank 4 from (select i, 5 j, 6 -- 逆时针螺旋特征码 counter-clockwise 7 case least(j - 1, :n - i, :n - j, i - 1) 8 when j - 1 then 9 (j - 1) || '1' || i 10 when :n - i then 11 (:n - i) || '2' || j 12 when :n - j then 13 (:n - j) || '3' || (:n - i) 14 when i - 1 then 15 (i - 1) || '4' || (:n - j) 16 end as tag 17 from (select level as i from dual connect by level <= :n) a, 18 (select level as j from dual connect by level <= :n) b 19 ) 20 ) 21 start with j = 1 22 connect by j - 1 = prior j and i = prior i 23 group by i 24 order by i;
STR------------------------------------------------------------------------------------------------- 1 8 7 2 9 6 3 4 5
SQL> exec :n := 4;
PL/SQL 过程已成功完成。
SQL> /
STR------------------------------------------------------------------------------------------------- 1 12 11 10 2 13 16 9 3 14 15 8 4 5 6 7
SQL> exec :n := 5;
PL/SQL 过程已成功完成。
SQL> /
STR------------------------------------------------------------------------------------------------- 1 16 15 14 13 2 17 24 23 12 3 18 25 22 11 4 19 20 21 10 5 6 7 8 9
SQL>不妨也填足一下:
代码:--------------------------------------------------------------------------------SQL> exec :n := 5
PL/SQL 过程已成功完成。
SQL> select replace(max(sys_connect_by_path(rank, ',')), ',') str 2 from (select i, j, 3 case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then ' ' 4 else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank, 5 min(j) over(partition by i) minj 6 from (select i, 7 j, 8 -- 顺时针螺旋特征码 counter-clockwise 9 case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1) 10 when i - j then 11 :n - (i - j) || '1' || i 12 when i + j - :n - 1 then 13 :n - (i + j - :n - 1) || '2' || j 14 when j - i then 15 :n - (j - i) || '3' || (:n - i) 16 when :n - i - j + 1 then 17 :n - (:n - i - j + 1) || '4' || i 18 end as tag 19 from (select level as i from dual connect by level <= :n) a, 20 (select level as j from dual connect by level <= :n) b 21 -- where abs(i - j) < floor(:n / 2 + .6) 22 -- and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n 23 ) 24 ) 25 start with j = minj 26 connect by j - 1 = prior j and i = prior i 27 group by i 28 order by i;
STR---------------------------------------------------------------------------------------------------------------------- 7 8 12 6 1 9 13 11 5 2 10 4 3
SQL> exec :n := 7;
PL/SQL 过程已成功完成。
SQL> /
STR---------------------------------------------------------------------------------------------------------------------- 10 11 19 9 12 20 24 18 8 1 13 21 25 23 17 7 2 14 22 16 6 3 15 5 4
已选择7行。
SQL> exec :n := 9;
PL/SQL 过程已成功完成。
SQL> /
STR---------------------------------------------------------------------------------------------------------------------- 13 14 26 12 15 27 35 25 11 16 28 36 40 34 24 10 1 17 29 37 41 39 33 23 9 2 18 30 38 32 22 8 3 19 31 21 7 4 20 6 5
已选择9行。
SQL> exec :n := 8
PL/SQL 过程已成功完成。
SQL> /
STR---------------------------------------------------------------------------------------------------------------------- 5 4 6 18 17 3 7 19 27 26 16 2 8 20 28 32 31 25 15 1 9 21 29 30 24 14 10 22 23 13 11 12
对于比较大的N值, 需对"顺时针螺旋特征码"的组成进行适当修改:
代码:--------------------------------------------------------------------------------1 select replace(max(sys_connect_by_path(rank, ',')), ',') str 2 from (select i, j, 3 case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then ' ' 4 else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank, 5 min(j) over(partition by i) minj 6 from (select i, 7 j, 8 -- 逆时针螺旋特征码 counter-clockwise 9 case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1) 10 when i - j then 11 chr(:n - (i - j)) || '1' || chr(i) 12 when i + j - :n - 1 then 13 chr(:n - (i + j - :n - 1)) || '2' || chr(j) 14 when j - i then 15 chr(:n - (j - i)) || '3' || chr((:n - i)) 16 when :n - i - j + 1 then 17 chr(:n - (:n - i - j + 1)) || '4' || chr(i) 18 end as tag 19 from (select level as i from dual connect by level <= :n) a, 20 (select level as j from dual connect by level <= :n) b 21 -- where abs(i - j) < floor(:n / 2 + .6) 22 -- and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n 23 ) 24 ) 25 start with j = minj 26 connect by j - 1 = prior j and i = prior i 27 group by i 28* order by iSQL> /
STR------------------------------------------------------------------------------------------------------------------- 19 20 40 18 21 41 57 39 17 22 42 58 70 56 38 16 23 43 59 71 79 69 55 37 15 24 44 60 72 80 84 78 68 54 36 14 1 25 45 61 73 81 85 83 77 67 53 35 13 2 26 46 62 74 82 76 66 52 34 12 3 27 47 63 75 65 51 33 11 4 28 48 64 50 32 10 5 29 49 31 9 6 30 8 7
--------------------------------------------------------------------------------想来是的, 这样你看如何?
代码:--------------------------------------------------------------------------------1 select replace(max(sys_connect_by_path(rank, ',')), ',') str 2 from (select i, j, 3 to_char(rank() over(order by tag), '9999') as rank 4 from (select i, 5 j, 6 -- 逆时针螺旋特征码 counter-clockwise 7 case least(j - 1, &&1 - i, &1 - j, i - 1) 8 when j - 1 then 9 (j - 1) || '1' || i 10 when &1 - i then 11 (&1 - i) || '2' || j 12 when &1 - j then 13 (&1 - j) || '3' || (&1 - i) 14 when i - 1 then 15 (i - 1) || '4' || (&1 - j) 16 end as tag 17 from (select level as i from dual connect by level <= &1) a, 18 (select level as j from dual connect by level <= &1) b 19 ) 20 ) 21 start with j = 1 22 connect by j - 1 = prior j and i = prior i 23 group by i 24* order by iSQL> /输入 1 的值: 5原值 7: case least(j - 1, &&1 - i, &1 - j, i - 1)新值 7: case least(j - 1, 5 - i, 5 - j, i - 1)原值 10: when &1 - i then新值 10: when 5 - i then原值 11: (&1 - i) || '2' || j新值 11: (5 - i) || '2' || j原值 12: when &1 - j then新值 12: when 5 - j then原值 13: (&1 - j) || '3' || (&1 - i)新值 13: (5 - j) || '3' || (5 - i)原值 15: (i - 1) || '4' || (&1 - j)新值 15: (i - 1) || '4' || (5 - j)原值 17: from (select level as i from dual connect by level <= &1) a,新值 17: from (select level as i from dual connect by level <= 5) a,原值 18: (select level as j from dual connect by level <= &1) b新值 18: (select level as j from dual connect by level <= 5) b
STR--------------------------------------------------------------------------------------------
1 16 15 14 13 2 17 24 23 12 3 18 25 22 11 4 19 20 21 10 5 6 7 8 9
SQL>--------------------------------------------------------------------------------使用前, 给声明m和n并赋值
代码:--------------------------------------------------------------------------------var n number;var m number;
exec :n := &n; :m=&m;
with t as ( select :n as n, :m as m from dual)select replace(max(sys_connect_by_path(rank, ',')), ',') str from (select i, j, to_char(rank() over(order by tag), '999999') as rank from (select i, j, -- 顺时针螺旋特征码 clockwise case least(i - 1, m - j, n - i, j - 1) when i - 1 then to_char(i - 1, 'fm0000') || '1' || to_char(j - 1, 'fm0000') when m - j then to_char(m - j, 'fm0000') || '2' || to_char(i - 1, 'fm0000') when n - i then to_char(n - i, 'fm0000') || '3' || to_char(m - j, 'fm0000') when j - 1 then to_char(j - 1, 'fm0000') || '4' || to_char(n - i, 'fm0000') end as tag from (select n, level as i from t connect by level <= n) a, (select m, level as j from t connect by level <= m) b)) start with j = 1connect by j - 1 = prior j and i = prior i group by i-----------------------------------------------------------------------------------------------
转载于:https://www.cnblogs.com/antony1029/archive/2006/04/11/372569.html
相关资源：JAVA上百实例源码以及开源项目