ITPub博客

首页 > Linux操作系统 > Linux操作系统 > ITPUB SQL大赛第二期(一)

ITPUB SQL大赛第二期(一)

原创 Linux操作系统 作者:yangtingkun 时间:2011-03-28 23:38:31 0 删除 编辑

贴一下第二期的第一道题。

第二期题目参考:http://www.itpub.net/thread-1403356-1-1.html

版主newkid点评参考:http://www.itpub.net/thread-1411980-1-1.html

 

 

简单描述一下问题:

问题1(80)

在一个6*6的棋盘中,放置12个球,每行、每列、每个正负45度的斜线上最多放置2个球,请用一个SQL语句(不可以用PL/SQLT-SQL匿名块、过程或函数,也不可以用Java等外部语言)求出不“重复”的摆法的个数(剔除上下对称、左右对称、中心对称,沿中心点旋转等各种变形)

对于这个问题,其实就是在第一题的基础上加大了难度。个人认为最困难地方是搞清楚存在多少种变形的方法,这并没有什么太好的办法,不过好在有第一题的基础,我们可以在第一题结果上,通过手工画图的方式来搞清楚各种变形和原图形的关系。当然后来题目给出了进一步提示,明确了8种等价的变形,这相当于降低了一部分难度。

SQL>  with c as
  2  (select rownum - 1 c from dual connect by rownum <= 2),
  3  lines as
  4  (select to_number(c1.c || c2.c || c3.c || c4.c || c5.c || c6.c) line, c1.c c1, c2.c c2, c3.c c3, c4.c c4, c5.c c5, c6.c c6
  5  from c c1, c c2, c c3, c c4, c c5, c c6
  6  where c1.c + c2.c + c3.c + c4.c + c5.c + c6.c = 2
  7  order by 1 desc),
  8  result as (select rownum,
  9     ltrim(to_char(line1.line, '099999'))
 10             || chr(10) || ltrim(to_char(line2.line, '099999'))
 11             || chr(10) || ltrim(to_char(line3.line, '099999'))
 12             || chr(10) || ltrim(to_char(line4.line, '099999'))
 13             || chr(10) || ltrim(to_char(line5.line, '099999'))
 14             || chr(10) || ltrim(to_char(line6.line, '099999')) result1,
 15     reverse(ltrim(to_char(line1.line, '099999')))
 16             || chr(10) || reverse(ltrim(to_char(line2.line, '099999')))
 17             || chr(10) || reverse(ltrim(to_char(line3.line, '099999')))
 18             || chr(10) || reverse(ltrim(to_char(line4.line, '099999')))
 19             || chr(10) || reverse(ltrim(to_char(line5.line, '099999')))
 20             || chr(10) || reverse(ltrim(to_char(line6.line, '099999'))) result2,
 21     ltrim(to_char(line6.line, '099999'))
 22             || chr(10) || ltrim(to_char(line5.line, '099999'))
 23             || chr(10) || ltrim(to_char(line4.line, '099999'))
 24             || chr(10) || ltrim(to_char(line3.line, '099999'))
 25             || chr(10) || ltrim(to_char(line2.line, '099999'))
 26             || chr(10) || ltrim(to_char(line1.line, '099999')) result3,
 27     reverse(ltrim(to_char(line6.line, '099999')))
 28             || chr(10) || reverse(ltrim(to_char(line5.line, '099999')))
 29             || chr(10) || reverse(ltrim(to_char(line4.line, '099999')))
 30             || chr(10) || reverse(ltrim(to_char(line3.line, '099999')))
 31             || chr(10) || reverse(ltrim(to_char(line2.line, '099999')))
 32             || chr(10) || reverse(ltrim(to_char(line1.line, '099999'))) result4,
 33     line1.c1 || line2.c1 || line3.c1 || line4.c1 || line5.c1  || line6.c1
 34             || chr(10) || line1.c2 || line2.c2 || line3.c2 || line4.c2 || line5.c2 || line6.c2
 35             || chr(10) || line1.c3 || line2.c3 || line3.c3 || line4.c3 || line5.c3 || line6.c3
 36             || chr(10) || line1.c4 || line2.c4 || line3.c4 || line4.c4 || line5.c4 || line6.c4
 37             || chr(10) || line1.c5 || line2.c5 || line3.c5 || line4.c5 || line5.c5 || line6.c5
 38             || chr(10) || line1.c6 || line2.c6 || line3.c6 || line4.c6 || line5.c6 || line6.c6 result5,
 39     line6.c1 || line5.c1 || line4.c1 || line3.c1 || line2.c1 || line1.c1
 40             || chr(10) || line6.c2 || line5.c2 || line4.c2 || line3.c2 || line2.c2 || line1.c2
 41             || chr(10) || line6.c3 || line5.c3 || line4.c3 || line3.c3 || line2.c3 || line1.c3
 42             || chr(10) || line6.c4 || line5.c4 || line4.c4 || line3.c4 || line2.c4 || line1.c4
 43             || chr(10) || line6.c5 || line5.c5 || line4.c5 || line3.c5 || line2.c5 || line1.c5
 44             || chr(10) || line6.c6 || line5.c6 || line4.c6 || line3.c6 || line2.c6 || line1.c6 result6,
 45     line1.c6 || line2.c6 || line3.c6 || line4.c6 || line5.c6 || line6.c6
 46             || chr(10) || line1.c5 || line2.c5 || line3.c5 || line4.c5 || line5.c5 || line6.c5
 47             || chr(10) || line1.c4 || line2.c4 || line3.c4 || line4.c4 || line5.c4 || line6.c4
 48             || chr(10) || line1.c3 || line2.c3 || line3.c3 || line4.c3 || line5.c3 || line6.c3
 49             || chr(10) || line1.c2 || line2.c2 || line3.c2 || line4.c2 || line5.c2 || line6.c2
 50             || chr(10) || line1.c1 || line2.c1 || line3.c1 || line4.c1 || line5.c1 || line6.c1 result7,
 51     line6.c6 || line5.c6 || line4.c6 || line3.c6 || line2.c6 || line1.c6
 52             || chr(10) || line6.c5 || line5.c5 || line4.c5 || line3.c5 || line2.c5 || line1.c5
 53             || chr(10) || line6.c4 || line5.c4 || line4.c4 || line3.c4 || line2.c4 || line1.c4
 54             || chr(10) || line6.c3 || line5.c3 || line4.c3 || line3.c3 || line2.c3 || line1.c3
 55             || chr(10) || line6.c2 || line5.c2 || line4.c2 || line3.c2 || line2.c2 || line1.c2
 56             || chr(10) || line6.c1 || line5.c1 || line4.c1 || line3.c1 || line2.c1 || line1.c1 result8
 57  from lines line1, lines line2, lines line3, lines line4, lines line5, lines line6
 58  where line1.line + line2.line + line3.line + line4.line + line5.line + line6.line = 222222
 59  and ltrim(to_char(line1.line + 10*line2.line + 100*line3.line + 1000*line4.line + 10000*line5.line + 100000*line6.line), '012') is null
 60  and ltrim(to_char(100000*line1.line + 10000*line2.line + 1000*line3.line + 100*line4.line + 10*line5.line + line6.line), '012') is null
 61  )
 62  select count(distinct greatest(result1, result2, result3, result4, result5, result6, result7, result8)) cn
 63  from result;

        CN
----------
       155

已用时间:  00: 00: 18.65

最先完成的SQL无非就是第一题的基础上将5*5变成了6*6,然后根据各种变形的规则生成对应的结果。由于8种变形之间可以相互转换,因此这8种等价的变形的最大值是同一个图形,这样通过COUNT DISTINCT的方式,就获得了去重的解。

虽然结果得到了,但是这个SQL运行速度较慢,需要进一步的优化。

SQL>  with c as
  2  (select rownum - 1 c from dual connect by rownum <= 2),
  3  lines as
  4  (select to_number(c1.c || c2.c || c3.c || c4.c || c5.c || c6.c) line, c1.c c1, c2.c c2, c3.c c3, c4.c c4, c5.c c5, c6.c c6
  5  from c c1, c c2, c c3, c c4, c c5, c c6
  6  where c1.c + c2.c + c3.c + c4.c + c5.c + c6.c = 2
  7  ),
  8  result as (select /*+ ordered */
  9     ltrim(to_char(line1.line, '099999'))
 10             || ltrim(to_char(line2.line, '099999'))
 11             || ltrim(to_char(line3.line, '099999'))
 12             || ltrim(to_char(line4.line, '099999'))
 13             || ltrim(to_char(line5.line, '099999'))
 14             || ltrim(to_char(line6.line, '099999')) result1,
 15     reverse(ltrim(to_char(line1.line, '099999')))
 16             || reverse(ltrim(to_char(line2.line, '099999')))
 17             || reverse(ltrim(to_char(line3.line, '099999')))
 18             || reverse(ltrim(to_char(line4.line, '099999')))
 19             || reverse(ltrim(to_char(line5.line, '099999')))
 20             || reverse(ltrim(to_char(line6.line, '099999'))) result2,
 21     ltrim(to_char(line6.line, '099999'))
 22             || ltrim(to_char(line5.line, '099999'))
 23             || ltrim(to_char(line4.line, '099999'))
 24             || ltrim(to_char(line3.line, '099999'))
 25             || ltrim(to_char(line2.line, '099999'))
 26             || ltrim(to_char(line1.line, '099999')) result3,
 27     reverse(ltrim(to_char(line6.line, '099999')))
 28             || reverse(ltrim(to_char(line5.line, '099999')))
 29             || reverse(ltrim(to_char(line4.line, '099999')))
 30             || reverse(ltrim(to_char(line3.line, '099999')))
 31             || reverse(ltrim(to_char(line2.line, '099999')))
 32             || reverse(ltrim(to_char(line1.line, '099999'))) result4,
 33     line1.c1 || line2.c1 || line3.c1 || line4.c1 || line5.c1  || line6.c1
 34             || line1.c2 || line2.c2 || line3.c2 || line4.c2 || line5.c2 || line6.c2
 35             || line1.c3 || line2.c3 || line3.c3 || line4.c3 || line5.c3 || line6.c3
 36             || line1.c4 || line2.c4 || line3.c4 || line4.c4 || line5.c4 || line6.c4
 37             || line1.c5 || line2.c5 || line3.c5 || line4.c5 || line5.c5 || line6.c5
 38             || line1.c6 || line2.c6 || line3.c6 || line4.c6 || line5.c6 || line6.c6 result5,
 39     line6.c1 || line5.c1 || line4.c1 || line3.c1 || line2.c1 || line1.c1
 40             || line6.c2 || line5.c2 || line4.c2 || line3.c2 || line2.c2 || line1.c2
 41             || line6.c3 || line5.c3 || line4.c3 || line3.c3 || line2.c3 || line1.c3
 42             || line6.c4 || line5.c4 || line4.c4 || line3.c4 || line2.c4 || line1.c4
 43             || line6.c5 || line5.c5 || line4.c5 || line3.c5 || line2.c5 || line1.c5
 44             || line6.c6 || line5.c6 || line4.c6 || line3.c6 || line2.c6 || line1.c6 result6,
 45     line1.c6 || line2.c6 || line3.c6 || line4.c6 || line5.c6 || line6.c6
 46             || line1.c5 || line2.c5 || line3.c5 || line4.c5 || line5.c5 || line6.c5
 47             || line1.c4 || line2.c4 || line3.c4 || line4.c4 || line5.c4 || line6.c4
 48             || line1.c3 || line2.c3 || line3.c3 || line4.c3 || line5.c3 || line6.c3
 49             || line1.c2 || line2.c2 || line3.c2 || line4.c2 || line5.c2 || line6.c2
 50             || line1.c1 || line2.c1 || line3.c1 || line4.c1 || line5.c1 || line6.c1 result7,
 51     line6.c6 || line5.c6 || line4.c6 || line3.c6 || line2.c6 || line1.c6
 52             || line6.c5 || line5.c5 || line4.c5 || line3.c5 || line2.c5 || line1.c5
 53             || line6.c4 || line5.c4 || line4.c4 || line3.c4 || line2.c4 || line1.c4
 54             || line6.c3 || line5.c3 || line4.c3 || line3.c3 || line2.c3 || line1.c3
 55             || line6.c2 || line5.c2 || line4.c2 || line3.c2 || line2.c2 || line1.c2
 56             || line6.c1 || line5.c1 || line4.c1 || line3.c1 || line2.c1 || line1.c1 result8
 57  from lines line1, lines line2, lines line3, lines line4, lines line5, lines line6
 58  where line1.line + line2.line + line3.line + line4.line + line5.line + line6.line = 222222
 59  and ltrim(line1.line + line2.line + line3.line, '012') is null
 60  and ltrim(line1.line + line2.line + line3.line + line4.line, '012') is null
 61  and ltrim(line1.line + line2.line + line3.line + line4.line + line5.line, '012') is null
 62  and ltrim(to_char(line1.line + 10*line2.line + 100*line3.line + 1000*line4.line + 10000*line5.line + 100000*line6.line), '012') is null
 63  and ltrim(to_char(line1.line + 10*line2.line + 100*line3.line), '012') is null
 64  and ltrim(to_char(line1.line + 10*line2.line + 100*line3.line + 1000*line4.line), '012') is null
 65  and ltrim(to_char(line1.line + 10*line2.line + 100*line3.line + 1000*line4.line + 10000*line5.line), '012') is null
 66  and ltrim(to_char(100000*line1.line + 10000*line2.line + 1000*line3.line + 100*line4.line + 10*line5.line + line6.line), '012') is null
 67  and ltrim(to_char(100*line1.line + 10*line2.line + line3.line), '012') is null
 68  and ltrim(to_char(1000*line1.line + 100*line2.line + 10*line3.line + line4.line), '012') is null
 69  and ltrim(to_char(10000*line1.line + 1000*line2.line + 100*line3.line + 10*line4.line + line5.line), '012') is null
 70  )
 71  select count(distinct greatest(result1, result2, result3, result4, result5, result6, result7, result8))
 72  from result;

COUNT(DISTINCTGREATEST(RESULT1,RESULT2,RESULT3,RESULT4,RESULT5,RESULT6,RESULT7,RESULT8))
----------------------------------------------------------------------------------------
                                                                                     155

已用时间:  00: 00: 00.64

这里优化的主要思路是,在连接过程中,如果发现当前的组合已经不满足题目的要求,那么就尽早过滤掉。比如如果将前三行各个列相加,发现某列的结果已经出现了3,那么这种变形显然不可能满足题目要求,因此就可以被舍弃。所以这里添加了判断,当前3行结果的所有变形获得后,过滤掉列和两个斜线上出现大于2的情况。同样在前4行和前5行结果中进行相同的过滤,这使得大量不符合条件的结果没有参加到后续的连接中,从而极大的提高了性能。

另外之所以添加了/*+ ORDERED */这个提示,是因为在存在6张表连接时,Oracle打乱了连接顺序,先从line6开始进行连接,这会导致两个结果,一是5×5矩阵中正确的排序被打乱,二是前面的优化手段将不起作用,因为我们认为连接从line1开始。加上提示后,确保Oracle按照指定的顺序进行表连接,从而达到优化目的。

 

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

请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10525137