posts - 189,comments - 115,trackbacks - 0
 算法问题 用SQL写出当M*N时的螺旋矩阵算法

算法问题 用SQL写出当M*N时的螺旋矩阵算法
如下是一个4*4的矩阵:

1 12 11 10
2 13 16  9
3 14 15  8
4  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 i
SQL> /

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 i
SQL> /
输入 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 = 1
connect by j - 1 = prior j and i = prior i
 group by i
-----------------------------------------------------------------------------------------------

posted on 2006-04-07 21:31 MEYE 阅读(513) 评论(0)  编辑  收藏 所属分类: Study

只有注册用户登录后才能发表评论。


网站导航: