ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 第一届SQL大赛第一期优秀解题思路汇总

第一届SQL大赛第一期优秀解题思路汇总

原创 Linux操作系统 作者:regonly1 时间:2011-03-17 12:33:24 0 删除 编辑

SQL大赛第一期解题方法的公布,让我领略了各种新颖巧妙的解题方法。精神也为之一振,就决定写篇总结,把大家好的方法记下来。

第一期题目大意如下:
给定一个5×5的矩阵,要求:
1、每行不得超过两个球;
2、每列不得超过两个球;
3、每个45度斜线不得超过两个球(包括左倾斜和右倾斜,及对角线)
问:这样的摆法有多少种。

解答要求:
以单个SQL语句实现。
通用性(比如说,可扩展到三个球四个球,或者6阶矩阵等)
效率。也就是执行时间。
其他要求就不一一叙述了。

按照以上这个题目及要求,大家都给出了各式奇思妙想。下面是所有答题结果中,我认为比较有代表性或创造性的思路的汇总,并不包含全部的解题方法。其中有些解题过程很长,或者都还没格式化,比较乱,看得我比较眼酸(由此可见,评委要全部仔细的看完更是辛苦啊!),都没仔细看。

其中IR的得分很高,我也特意留意了下他的解题方法,不过他用的递归with需要在11g环境下运行,但是看newkid的分析感觉挺不错的。以后有环境再分析下。

这个题目主要要解决的是两个方面的问题:基础数据的构造和斜线的相加

一、基础数据构造

***************************************************************
1、递归法(这是我自己的方法(GO),所以先拿出来晒晒)
***************************************************************

这个方法利用了connect by构造数据的特性,首先构造出基础数据:5个0和2个1.
SQL> select floor(rownum/(dim + cnt - 1)) n, rownum r, dim
  2    from dual, (select 5 dim, length('11') cnt  from dual) dims
  3  connect by rownum <= dim+cnt
  4  /
 
         N          R        DIM
---------- ---------- ----------
         0          1          5
         .................
         0          5          5
         1          6          5
         1          7          5
 
7 rows selected

构造这个数据的目的是可以通过R列,来实现不同递归层次的关联而得到不同组合的01字符串。但是这个方法有个缺陷,就是只能局限于5+2模式(即5×5矩阵,每行最多两个球的模式),这个newkid也提到了。所以在第二个的解答中我已经将这个方法扩展了:
SQL> with
  2  dims as(select 5 dim, 2 cnt from dual)
  3  select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
  4    from dual, dims
  5  connect by rownum <= dim+cnt
  6  /
 
         N          R        DIM
---------- ---------- ----------
         0          1          5
         ...................
         0          5          5
         1          6          5
         1          7          5
 
7 rows selected

这样就不再局限于5+2,而是适用于任意情况的组合了,根据情况只要修改相应的数值即可:
SQL> with
  2  dims as(select 6 dim, 2 cnt from dual)
  3  select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
  4    from dual, dims
  5  connect by rownum <= dim+cnt
  6  /
 
         N          R        DIM
---------- ---------- ----------
         0          1          6
         ..................
         0          6          6
         1          7          6
         1          8          6
 
8 rows selected

构造了这个基本数据后,我们就可以再套一层层次查询,把这些不同组合的字符串取出来:
SQL> with
  2  dims as(select 5 dim, 2 cnt from dual),
  3  nums as(
  4  select n, to_number(substr(n, 1, 1)) n1,
  5         to_number(substr(n, 2, 1)) n2, to_number(substr(n, 3, 1)) n3,
  6         to_number(substr(n, 4, 1)) n4, to_number(substr(n, 5, 1)) n5
  7    from (select distinct replace(sys_connect_by_path(n, ','), ',') n
  8            from (select decode(sign(rownum-dim),1,1,0) n, rownum r, dim
  9                    from dual, dims
 10                  connect by rownum <= dim+cnt)
 11           where level = dim
 12          connect by nocycle prior r <> r and level <= dim))
 13  select * from nums
 14  /
 
N                   N1         N2         N3         N4         N5
----------- ---------- ---------- ---------- ---------- ----------
00001                0          0          0          0          1
.................................
10001                1          0          0          0          1
11000                1          1          0          0          0
 
16 rows selected


***************************************************************
2、逐个递推法
***************************************************************

这个是LL的方法。说实话,LL的方法很巧妙,要我我怎么也想不到那里去。我觉得跟他得的得分一样有点惭愧,呵呵。他的思路有点类似于我们人的推理,先在第一个位置固定放1,然后在其后的每个位置上向右逐个移动的放1,得到四种情况。
然后在第二个位置固定放1,而后在其后的位置上再逐个移动的放1.依次类推,便得到了10组。但是这个得有个前提,即必须是得事先确定,所有行都是两个球,否则的话还少了0个和1个球的6中情况。这个是它的不足之处。
【代码】:
SQL> with t1 as
  2  (
  3  select iid, x, y, x + y + 25 z1, x - y z2
  4    from (select rownum iid, mod(rownum - 1, 5) + 1 x, ceil(rownum / 5) y
  5            from dual
  6          connect by rownum <= 25)
  7    )
  8  select x,y,substr('00000', 1, y - 1) || '1' ||
  9         substr('00000', y, x - y - 1) || '1' ||
 10         substr('00000', x, 5 - x) rr
 11    from t1
 12   where x > y
 13     and x != y
 14  /
 
         X          Y RR
---------- ---------- --------------------------------
         2          1 11000
         .........
         5          3 00101
         5          4 00011
 
10 rows selected

***************************************************************
3、排列组合法
***************************************************************

这个方法的思路有点类似于我们学概率论时的思路,我想,CA和VL学概率论学的比较好,所以想问题的出发点也是基于概率的。首先,我们知道,5×5的矩阵,每个位置只有0和1两种可能,所以5×5的矩阵,只要将每个位置的两种可能性用笛卡尔积乘起来,就能得到所有的摆法了。不过,写的有点冗长了。
【代码】
(select 0 v11 from dual union all select 1 from dual) a1,
.................
(select 0 v55 from dual union all select 1 from dual) a25
这个可以先用一个with子句构造一个tmp表,然后在from用引用即可。

其中,TK和JJ用的也是类似的方法。不过他们是首先得到一行的所有摆法。然后再扩展到5行的所有摆法。比CA简洁很多。
【代码】
SQL> with c as
  2   (select rownum - 1 c from dual connect by rownum <= 2)
  3  select to_number (c1.c || c2.c || c3.c || c4.c || c5.c) line
  4    from c c1, c c2, c c3, c c4, c c5
  5   where c1.c + c2.c + c3.c + c4.c + c5.c = 2
  6   order by 1 desc
  7  /
 
      LINE
----------
     11000
     .....
       101
        11
 
10 rows selected
 
***************************************************************
4、二进制构造(想不出好的名字,就这么命名了)
***************************************************************

这个方法是先不管多少个球,反正每个位置两种可能,总共有2^5=32种情况给全部列出来。列举的方式很明显是基于二进制转换的思路,即将0-31的每个数字都转换为二进制,就可得到这些不同组合的字符串了。
【代码】
SQL>  select col1 || col2 || col3 || col4 || col5 strings,
  2          col1 + col2 + col3 + col4 + col5 balls,
  3          r.*
  4     from (select mod(floor(rownum / 16), 2) col1,
  5                  mod(floor(rownum / 8), 2) col2,
  6                  mod(floor(rownum / 4), 2) col3,
  7                  mod(floor(rownum / 2), 2) col4,
  8                  mod(floor(rownum), 2) col5
  9             from dual
 10           connect by rownum <= 32) r
 11    where col1 + col2 + col3 + col4 + col5 <= 5
 12    ORDER BY 1 desc
 13  /
 
STRINGS           BALLS       COL1       COL2       COL3       COL4       COL5
------------ ---------- ---------- ---------- ---------- ---------- ----------
11111                5          1          1          1          1          1
..............
00001                1          0          0          0          0          1
00000                0          0          0          0          0          0
 
32 rows selected
 

以上列举了构造数据的几个主要算法,其他的也基本上类似。
上面,我们完成了题目的第一个关键部分:数据构造。接下来就是斜线处理了。


二、斜线的判断与处理

斜线处理思路更加新颖巧妙,主要那么三类:

***************************************************************
1、坐标点相加法(这个是我,也是其他很多人用的)
***************************************************************

这个称谓看上去好像很了不起,但是实际上这是最土、最冗长、也是扩展性最差的办法了。本法是基于最基本的5×5图形的,在得到每个点的值后,将相应45度斜线的坐标点加起来,就得到斜线和了。每条斜线都得这么加,还得看清楚了别写错了就功亏一篑了。
【代码】
n15 + n24 + n33 + n42 + n51 <= 2 --对角线相加
n21 + n32 + n43 + n54 <= 2
n31 + n42 + n53 <= 2
n41 + n52 <= 2
n12 + n23 + n34 + n45 <= 2
n13 + n24 + n35 <= 2
n14 + n24 <= 2--右倾斜
n14 + n23 + n32 + n41 <= 2
n31 + n22 + n13 <= 2
n21 + n12 <= 2
n52 + n43 + n34 + n25 <= 2
n53 + n44 + n35 <= 2
n45 + n54 <= 2

***************************************************************
2、移位相加法
***************************************************************

这个方法灰常巧妙啊,包括TK和newkid用的都是这个。对此,我除了赞叹...........还是赞叹。TK仅用了17行就搞定了,而我用了43行。
言归正传,什么是移位相加法呢?看下面的图就明白了:
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

上面移位后:
        A B C D E
      F G H I J
    K L M N O
  P Q R S T
U V W X Y

第一列:U
第二列:P V
第三列:K Q W
第四列:F L R X
第五列:A G M S Y
第六列:B H N T
第七列:C I O
第八列:D J
第九列:E
仔细观察一下,这些得到的列,不正是我们要取的斜线嘛。只要这些列作sum,就能得到我们想要的判断了。

当然,别忘了右倾斜:
A B C D E
  F G H I J
    K L M N O
      P Q R S T
        U V W X Y

具体做法么,只要给每行的数值乘以10的N倍(N为行号-1, 即=0...4)即可。
【代码】:
with c as
 (select rownum - 1 c from dual connect by rownum <= 2),
lines as
 (select to_number(c1.c || c2.c || c3.c || c4.c || c5.c) line
    from c c1, c c2, c c3, c c4, c c5
   where c1.c + c2.c + c3.c + c4.c + c5.c = 2
   order by 1 desc)
select rownum, ltrim(to_char(line1.line, '09999')) ||
       ltrim(to_char(line2.line, '09999')) ||
       ltrim(to_char(line3.line, '09999')) ||
       ltrim(to_char(line4.line, '09999')) ||
       ltrim(to_char(line5.line, '00009')) result
  from lines line1, lines line2, lines line3, lines line4, lines line5
 where line1.line + line2.line + line3.line + line4.line + line5.line = 22222
   and ltrim(to_char(line1.line + 10 * line2.line + 100 * line3.line + 1000 * line4.line + 10000 * line5.line), '012') is null
   and ltrim(to_char(10000 * line1.line + 1000 * line2.line + 100 * line3.line + 10 * line4.line + line5.line), '012') is null;


这个解法的要求是每个位置的数值最大只能是9,且斜线相加不能超过9。但是对于此题已经绰绰有余了。


***************************************************************
3、等值分组法
***************************************************************

此法我只在LL这边看到了,这是LL真正让我感觉巧妙的地方。他首先列出了矩阵的所有坐标点,然后对这些坐标点标号。并且在给出每个坐标点,横坐标和纵坐标的差值。这个正是该法的精髓所在,它直接为后面的斜线相加做了铺垫。接下来就是裁剪,去掉四个无需判断的顶点,把这些斜线点变成行列成一个结果集。然后与构造的5+2组合进行笛卡尔积。再按照各个斜线点的坐标标号到组合的字符串中取出这些点,并对这些点相加,得到斜线相加的结果。然后取斜线最大点不大于2即可。
【代码】:
with t1 as
(--构造坐标点,对坐标点标号,并取每个坐标点的横竖坐标差和和
select iid, x, y, x + y + 25 z1, x - y z2
  from (select rownum iid, mod(rownum - 1, 5) + 1 x, ceil(rownum / 5) y
          from dual
        connect by rownum <= 25)
  )
,t2 as (
--取出每条斜线坐标点数大于2的集合
select iid, zz
  from (select iid, z1 zz, count(*) over(partition by z1) cnt
          from t1
        union all
        select iid, z2, count(*) over(partition by z2) cnt from t1)
 where cnt > 2
)
,t3 as (--构造5+2
select rr,
       to_number(substr(rr, 1, 1)) c1,
       to_number(substr(rr, 2, 1)) c2,
       to_number(substr(rr, 3, 1)) c3,
       to_number(substr(rr, 4, 1)) c4,
       to_number(substr(rr, 5, 1)) c5
  from (select substr('00000', 1, y - 1) || '1' ||
               substr('00000', y, x - y - 1) || '1' ||
               substr('00000', x, 5 - x) rr
          from t1
         where x > y
           and x != y)
)
select rownum, chr
  from (select chr
          from (select a.chr,
                       b.zz,
                       sum(to_number(substr(a.chr, b.iid, 1))) n1
                  from (select r1.rr || r2.rr || r3.rr || r4.rr || r5.rr chr
                          from t3 r1, t3 r2, t3 r3, t3 r4, t3 r5
                         where r1.c1 + r2.c1 + r3.c1 + r4.c1 + r5.c1 < 3
                           and r1.c2 + r2.c2 + r3.c2 + r4.c2 + r5.c2 < 3
                           and r1.c3 + r2.c3 + r3.c3 + r4.c3 + r5.c3 < 3
                           and r1.c4 + r2.c4 + r3.c4 + r4.c4 + r5.c4 < 3
                           and r1.c5 + r2.c5 + r3.c5 + r4.c5 + r5.c5 < 3) a,
                       t2 b
                 group by a.chr, b.zz)
         group by chr
        having max(n1) < 3
         order by chr desc);

三、 总结
        按道理,每次写blog,都应该写篇总结,尤其是这篇总结的总结。但是由于每次写完blog,能够一样样写好并举例,都感到很疲劳了,本身已经很不易,再写个结论更累。呵呵,所以这次结论是在这篇原始版的blog写完后几天后才补充的。

        说了这么多,开始写结论吧。

        这次题目,主要思想是解决N×N矩阵中,球体摆放的问题。
        面对的最主要问题是如何用只能生成行数据的一个SQL语句来解决二维的矩阵数据的生成和条件的判断。
        因此,我们很自然的把问题分解为两个方面:
        一、数据的生成
        二、数据的判断
        数据的生成,我们又可以按如下思路来考虑:
        首先,按照题目要求,是5×5的矩阵,且每行不得超过2个球,所以,每个行他的可能性只有:
C(5,2) +C(5,1) + 1 = 10 + 5 + 1 = 16种
也就是说,放两个球有C(5,2)种可能性,放1个球有C(5,1)种可能性,没有球,则只有一种可能性,加起来就是16种。
        于是,我们得到了构造一行所需要的16种基本数据,其他行也是这个规则。于是总的可能性就有:
16^5 = 1048576种。
         现在,我们要解决的就是如何从这100多万种方案中筛选出题目所要求的矩阵了。于是,下一步的问题就变成了数据的判断了。其实,数据的判断虽然在方法上比数据的构造多种多样,但是本质却是一致的。就是判断斜线的和不大于2。沿着这个思路,大家充分发挥了想象力,看到其他人尤其是几位得分靠前的高手的答案后,我真是惊叹,大千世界,学无止境啊。
         其中的对斜线分组法及移位相加法,是我很崇拜的方法,因为其扩展性和效率都很好,而且也很简洁。这个是这次大赛值得我们学习的地方。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/12932950/viewspace-689716/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-05-10

  • 博文量
    257
  • 访问量
    1045501