ITPub博客

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

ITPUB SQL大赛第二期

原创 Linux操作系统 作者:Nalternative 时间:2011-04-02 16:07:26 0 删除 编辑

/**解题思路:
*1、找出所有6*6的满足条件的矩阵
*2、每个解为一行,共求出n个解,得到n行的一个表
*3、对每行经过7种变换,以及自身,每行能够变换出不同的m种
*4、对于总共的n行记录,相同的m即为在一个集合当中
*5、以m分组,每组的数目比上m即为每组的不同解的个数
*6、对每组不同解个数求和即为所得
*其中:由题目可知,总共12个球,每列最多2个,则可以直接得到每列是两个球,在下边条件中直接应用
*/
WITH
EVERY_CELL--每个格子的两种情况
 AS
 ( SELECT 1 P1 FROM DUAL
   UNION
   SELECT 0 FROM DUAL
 ),
EVERY_ROW--每行的情况
 AS
 (
 SELECT A.P1 P1,B.P1 P2,C.P1 P3,D.P1 P4,E.P1 P5,F.P1 P6
 FROM EVERY_CELL A,EVERY_CELL B,EVERY_CELL C,EVERY_CELL D,EVERY_CELL E,EVERY_CELL F
 WHERE A.P1+B.P1+C.P1+D.P1+E.P1+F.P1=2
 ),
RESULT--六行的结果
 AS
 (
SELECT A1.P1 W1 ,A1.P2 W2 ,A1.P3 W3 ,A1.P4 W4 ,A1.P5 W5 ,A1.P6 W6,
       A2.P1 W7 ,A2.P2 W8 ,A2.P3 W9 ,A2.P4 W10,A2.P5 W11,A2.P6 W12,
       A3.P1 W13,A3.P2 W14,A3.P3 W15,A3.P4 W16,A3.P5 W17,A3.P6 W18,
       A4.P1 W19,A4.P2 W20,A4.P3 W21,A4.P4 W22,A4.P5 W23,A4.P6 W24,
       A5.P1 W25,A5.P2 W26,A5.P3 W27,A5.P4 W28,A5.P5 W29,A5.P6 W30,
       A6.P1 W31,A6.P2 W32,A6.P3 W33,A6.P4 W34,A6.P5 W35,A6.P6 W36,rownum rn
FROM EVERY_ROW A1,EVERY_ROW A2,EVERY_ROW A3,EVERY_ROW A4,EVERY_ROW A5,EVERY_ROW A6
WHERE A1.P1+A2.P1+A3.P1+A4.P1+A5.P1+A6.P1=2--每列符合条件
AND A1.P2+A2.P2+A3.P2+A4.P2+A5.P2+A6.P2=2
AND A1.P3+A2.P3+A3.P3+A4.P3+A5.P3+A6.P3=2
AND A1.P4+A2.P4+A3.P4+A4.P4+A5.P4+A6.P4=2
AND A1.P5+A2.P5+A3.P5+A4.P5+A5.P5+A6.P5=2
AND A1.P6+A2.P6+A3.P6+A4.P6+A5.P6+A6.P6=2
AND A1.P1+A2.P2+A3.P3+A4.P4+A5.P5+A6.P6<=2--对角线
AND A1.P2+A2.P3+A3.P4+A4.P5+A5.P6<=2
AND A1.P3+A2.P4+A3.P5+A4.P6<=2
AND A1.P4+A2.P5+A3.P6<=2
AND A2.P1+A3.P2+A4.P3+A5.P4+A6.P5<=2
AND A3.P1+A4.P2+A5.P3+A6.P4<=2
AND A4.P1+A5.P2+A6.P3<=2
AND A1.P5+A2.P6<=2
AND A5.P1+A6.P2<=2
AND A1.P2+A2.P1<=2--对角线
AND A1.P3+A2.P2+A3.P1<=2
AND A1.P4+A2.P3+A3.P2+A4.P1<=2
AND A1.P5+A2.P4+A3.P3+A4.P2+A5.P1<=2
AND A1.P6+A2.P5+A3.P4+A4.P3+A5.P2+A6.P1<=2
AND A2.P6+A3.P5+A4.P4+A5.P3+A6.P2<=2
AND A3.P6+A4.P5+A5.P4+A6.P3<=2
AND A4.P6+A5.P5+A6.P4<=2
AND A5.P6+A6.P5<=2
),
symmetry_group as--对称分组
(
select W1,W2,W3,W4,W5,W6,
        W7,W8,W9,W10,W11,W12,
        W13,W14,W15,W16,W17,W18,
        W19,W20,W21,W22,W23,W24,
        W25,W26,W27,W28,W29,W30,
        W31,W32,W33,W34,W35,W36,rn
from RESULT
union--左右
select W6,W5,W4,W3,W2,W1,
        W12,W11,W10,W9,W8,W7,
        W18,W17,W16,W15,W14,W13,
        W24,W23,W22,W21,W20,W19,
        W30,W29,W28,W27,W26,W25,
        W36,W35,W34,W33,W32,W31,rn
from RESULT
union --上下对称
select W31,W32,W33,W34,W35,W36,
        W25,W26,W27,W28,W29,W30,
        W19,W20,W21,W22,W23,W24,
        W13,W14,W15,W16,W17,W18,
        W7,W8,W9,W10,W11,W12,
        W1,W2,W3,W4,W5,W6,rn
from RESULT
union --左下右上
select w1,w7,w13,w19,w25,w31,
        W2,W8,W14,W20,W26,W32,
        W3,W9,W15,W21,W27,W33,
        W4,W10,W16,W22,W28,W34,
        W5,W11,W17,W23,W29,W35,
        W6,W12,W18,W24,W30,W36,rn
from RESULT
union --左上右下
select  w36,w30,w24,w18,w12,w6,
        W35,W29,W23,W17,W11,W5,
        W34,W28,W22,W16,W10,W4,
        W33,W27,W21,W15,W9,W3,
        W32,W26,W20,W14,W8,W2,
        W31,W25,W19,W13,W7,W1,rn
from RESULT
union --旋转90度
select   W31,W25,W19,W13,W7,W1,
         W32,W26,W20,W14,W8,W2,
         W33,W27,W21,W15,W9,W3,
         W34,W28,W22,W16,W10,W4,
         W35,W29,W23,W17,W11,W5,
         w36,w30,w24,w18,w12,w6,rn
from RESULT
union --旋转180度
select   w36,w35,w34,w33,w32,w31,
         w30,w29,w28,w27,w26,w25,
         w24,w23,w22,w21,w20,w19,
         w18,w17,w16,w15,w14,w13,
         w12,w11,w10,w9,w8,w7,
         w6,w5,w4,w3,w2,w1,rn
from RESULT
union--倒转90度
select w6,w12,w18,w24,w30,w36,
        w5,w11,w17,w23,w29,w35,
        w4,w10,w16,w22,w28,w34,
        w3,w9,w15,w21,w27,w33,
        w2,w8,w14,w20,w26,w32,
        w1,w7,w13,w19,w25,w31,rn
from RESULT
),
symmetry_num as --对称数目
(
select rn,count(*) num from symmetry_group group by rn
)--求出总共不重复解的个数
select sum(count(*)/num) from symmetry_num group by num

思路比较清晰,代码稍显臃肿,一些不必要的条件如AND A5.P1+A6.P2<=2其实是可以去掉的。使用symmetry_group实现了行列转换,变换了思路求出了结果,注释够简洁但略欠清晰。作者的思路是:每个不同的结果加上其各种变换,总共8个结果,去掉重复的之后,可能就没8种了,可能就是X种(X为8、4、2、1中的一个)。如果某结果的x种变换完全不一样,那么根据对称性,说明其他(x-1)种的不同变换也不一样,也就是其他(x-1)种变换也会被计数,所以所有的有x种不同变换的方阵个数相加,再除以x,就可以得到不重复的方阵个数了。人肉构造各种变形的解比较辛苦。

分咋那么低。。。。。。。。。。。。。。。。。。。

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

上一篇: 导出ddl定义.sql
请登录后发表评论 登录
全部评论

注册时间:2011-02-09

  • 博文量
    123
  • 访问量
    177848