“盛拓传媒杯”SQL数据库编程大赛第一期评分及所有参赛选手答题揭晓！

solomon_007

原帖由 lastwinner 于 2011-3-16 00:12 发表


C33，这个你漏掉了

喔发现了，谢谢，死的不冤了。。。

rollingpig

2楼中newkid 11g with解法中最后的一部分其实是有瑕疵的
select rownum,all_rows from (select all_rows  from(select all_rows, rank() over(order by col_cnt desc) rnk from balls  )
where  rnk=1 order by all_rows desc);

缺了一个level(lvl)的限定条件，虽然结果是对的，但是逻辑上少了，应该是

select rownum,all_rows from (select all_rows  from(select all_rows, rank() over(order by col_cnt desc) rnk from balls where lvl = 5  )
where  rnk=1 order by all_rows desc);

3楼的lastwinner的就把那个条件加上了~

[ 本帖最后由 rollingpig 于 2011-3-16 09:13 编辑 ]

〇〇

原帖由 rollingpig 于 2011-3-16 09:11 发表
2楼中newkid 11g with解法中最后的一部分其实是有瑕疵的
select rownum,all_rows from (select all_rows  from(select all_rows, rank() over(order by col_cnt desc) rnk from balls  )
where  rnk=1 order by all_rows desc);

缺了一个level(lvl)的限定条件，虽然结果是对的，但是逻辑上少了，应该是

select rownum,all_rows from (select all_rows  from(select all_rows, rank() over(order by col_cnt desc) rnk from balls where lvl = 5  )
where  rnk=1 order by all_rows desc);

3楼的lastwinner的就把那个条件加上了~

这个是我画蛇添足改坏的.
原文

1. 
   
2. WITH r AS (    ---------- 一行里放M个球，这M个球所处的列位置的所有组合
   
3. SELECT s as one_row
   
4.   FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(x,','),',') s
   
5.           FROM (SELECT 1 x FROM DUAL UNION ALL SELECT 0 x FROM DUAL)
   
6.          WHERE LEVEL=:N
   
7.         CONNECT BY LEVEL<=:N
   
8.        )
   
9. WHERE LENGTH(s)-NVL(LENGTH(REPLACE(s,'1')),0)=:M
   
10. )
    
11. ,balls (row_cnt    -- 当前行数
    
12.        ,all_rows   -- 截至当前行，所有行的摆法拼接的结果
    
13.        ,col_cnt    -- 把每一列看作十进制的一位，此数字表示在列方向的各位和
    
14.        ,diag_cnt1  -- 此数字表示在右上至左下的斜线上各位的和
    
15.        ,diag_cnt2  -- 此数字表示在左上至右下的斜线上各位的和
    
16.        )
    
17. AS (
    
18.    SELECT 1,one_row,TO_NUMBER(one_row),TO_NUMBER(one_row),TO_NUMBER(one_row) ---初始化第一行数据
    
19.      FROM r
    
20.    UNION ALL
    
21.    SELECT balls.row_cnt+1  ---- 行数递增
    
22.          ,balls.all_rows||r.one_row  ---当前行拼入总结果
    
23.          ,balls.col_cnt+r.one_row    --- 在列方向各位进行累加
    
24.          ,balls.diag_cnt1*10+r.one_row  ---- 在斜线方向各位进行累加
    
25.          ,balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt)
    
26.      FROM balls,r
    
27.     WHERE balls.row_cnt<:N ---- 递归出口
    
28.           AND INSTR(balls.col_cnt+r.one_row,:M+1)=0 ---- 把带M+1的结果拦截掉
    
29.           AND INSTR(balls.diag_cnt1*10+r.one_row,:M+1)=0
    
30.           AND INSTR(balls.diag_cnt2+r.one_row*POWER(10,balls.row_cnt),:M+1)=0
    
31. )
    
32. SELECT ROWNUM,all_rows
    
33.   FROM (SELECT all_rows
    
34.           FROM balls
    
35.          WHERE row_cnt=:N
    
36.         ORDER BY 1 DESC
    
37.        );
    

复制代码

那个非递归的with也是我参照第2期答案改的，用K排序就妥了，如果存在1行全0的最终解
select rownum,all_rows from (select all_rows  from(select all_rows, rank() over(order by K desc)rnk from balls  )
where  rnk=1 order by all_rows desc);

[ 本帖最后由 〇〇 于 2011-3-16 09:22 编辑 ]

rollingpig

3 楼的lastwinner的code同样有提升空间。

with t1 as
(select rownum-1 c from dual connect by rownum < 3),
t2 as
(select a.c a, b.c b, c.c, d.c d, e.c e
    from t1 a, t1 b, t1 c, t1 d, t1 e
   where a.c + b.c + c.c + d.c + e.c < 3),
t3 as
(select a.a || a.b || a.c || a.d || a.e || b.a || b.b ||
         b.c || b.d || b.e || c.a || c.b || c.c || c.d ||
         c.e || d.a || d.b || d.c || d.d || d.e || e.a ||
         e.b || e.c || e.d || e.e x,
         (a.a + a.b + a.c + a.d + a.e + b.a + b.b +
         b.c + b.d + b.e + c.a + c.b + c.c + c.d +
         c.e + d.a + d.b + d.c + d.d + d.e + e.a +
         e.b + e.c + e.d + e.e) y,
         max(a.a + a.b + a.c + a.d + a.e + b.a + b.b + b.c + b.d + b.e + c.a + c.b + c.c + c.d + c.e + d.a + d.b + d.c + d.d + d.e + e.a + e.b + e.c + e.d + e.e)over() z
    from t2 a, t2 b, t2 c, t2 d, t2 e
   where a.a + b.a + c.a + d.a + e.a < 3
     and a.b + b.b + c.b + d.b + e.b < 3
     and a.c + b.c + c.c + d.c + e.c < 3
     and a.d + b.d + c.d + d.d + e.d < 3
     and a.e + b.e + c.e + d.e + e.e < 3
     and a.c + b.b + c.a < 3
     and a.d + b.c + c.b + d.a < 3
     and a.e + b.d + c.c + d.b + e.a < 3
     and b.e + c.d + d.c + e.b < 3
     and c.e + d.d + e.c < 3
     and a.c + b.d + c.e < 3
     and a.b + b.c + c.d + d.e < 3
     and a.a + b.b + c.c + d.d + e.e < 3
     and b.a + c.b + d.c + e.d < 3
     and c.a + d.b + e.c < 3)
select rank() over(order by x desc)rn ,x from t3 where y = z

最简单的就是在t2中预先计算 a.c+b.c +c.c+d.c + e.c 和 a.c||b.c||c.c||d.c||e.c，避免在笛卡尔积时做这些运算，同时获得代码的精简性和性能,也降低copy paste出错概率

with t1 as   
(select rownum-1 c from dual connect by rownum < 3),
t2 as
(select a.c a, b.c b, c.c, d.c d, e.c e ,a.c+b.c +c.c+d.c + e.c n,a.c||b.c||c.c||d.c||e.c s
    from t1 a, t1 b, t1 c, t1 d, t1 e
   where a.c + b.c + c.c + d.c + e.c < 3) ,
t3 as
(select   a.s || b.s || e.s ||d.s || e.s  x,
        (a.n + b.n + c.n + d.n +  e.n ) y,
         max(a.n + b.n + c.n + d.n +  e.n)over() z
    from t2 a, t2 b, t2 c, t2 d, t2 e
   where a.a + b.a + c.a + d.a + e.a < 3
     and a.b + b.b + c.b + d.b + e.b < 3
     and a.c + b.c + c.c + d.c + e.c < 3
     and a.d + b.d + c.d + d.d + e.d < 3
     and a.e + b.e + c.e + d.e + e.e < 3
     and a.c + b.b + c.a < 3
     and a.d + b.c + c.b + d.a < 3
     and a.e + b.d + c.c + d.b + e.a < 3
     and b.e + c.d + d.c + e.b < 3
     and c.e + d.d + e.c < 3
     and a.c + b.d + c.e < 3
     and a.b + b.c + c.d + d.e < 3
     and a.a + b.b + c.c + d.d + e.e < 3
     and b.a + c.b + d.c + e.d < 3
     and c.a + d.b + e.c < 3)
select rank() over(order by x desc)rn ,x from t3 where y = z

old code:  381 word,     1410  char, run time 5.6 sec
new code:  269  word ,  1051 char, tun time 3.7 sec

accelerator

"第一届“盛拓传媒杯”SQL数据库编程大赛宗旨并非考核脑筋急转弯或高深的算法考核各位puber的算法能力，而且主要以PL/SQL的技巧和技能，以及对SQL新功能的掌握能力，性能优化能力，并附带考核对数据库体系结构的综合理解。题目均以oracle自带的HR或Scott示例数据库为平台。"


为什么这么多人都考虑到可以直接写 =2 ,而不用 <=2, 可用看出大家都是基于第一期的要求 "性能优化能力", 把<=2改为 =2, 性能可以提高10倍,为什么不能加? 这明显是应当加分,而不是减分!

还有很多人因为没加注释而减分,我认为,好的程序是不需要注释的,如果一个算法(高深的算法),要加一大堆注释,人家才能理解,就不是一个好的解法.

有些程序,不需要注释,人家就看懂了
有些程序加了一大堆注释,人家还看不懂, ,两个性能一样,你选哪个?


衡量一个结果最重要的一个标准是什么? 我认为是结果的正确性,如果输出的结果没满足要求,或者甚至是错的,再高效有什么用? "算法高效，可惜最后粗心，导致结果全错了，最终结果由于少写一个数字，很遗憾显示的全错了",这样的结果怎么能比大多数答题正确的结果分还高,怎么解释?


呵呵,一口怨气,不吐不快.

rollingpig

另外，最后的地方用分析函数看似很炫，但是，单纯从代码量以及性能来看，其实，还是不如直接用
y=(select max(y) from t3)


old code:  381 word,     1410  char, run time 5.6 sec
new code1 :  269  word ,  1051 char, tun time 3.7 sec
new code2:  258 word ,  1011 char, tun time 3.4 sec

with
t1 as(select rownum-1 c from dual connect by rownum < 3),
t2 as
(select a.c a, b.c b, c.c, d.c d, e.c e ,a.c+b.c +c.c+d.c + e.c n,a.c||b.c||c.c||d.c||e.c s
    from t1 a, t1 b, t1 c, t1 d, t1 e
   where a.c + b.c + c.c + d.c + e.c < 3) ,
t3 as
(select   a.s || b.s || e.s ||d.s || e.s  x,
        (a.n + b.n + c.n + d.n +  e.n ) y
    from t2 a, t2 b, t2 c, t2 d, t2 e
   where a.a + b.a + c.a + d.a + e.a < 3
     and a.b + b.b + c.b + d.b + e.b < 3
     and a.c + b.c + c.c + d.c + e.c < 3
     and a.d + b.d + c.d + d.d + e.d < 3
     and a.e + b.e + c.e + d.e + e.e < 3
     and a.c + b.b + c.a < 3
     and a.d + b.c + c.b + d.a < 3
     and a.e + b.d + c.c + d.b + e.a < 3
     and b.e + c.d + d.c + e.b < 3
     and c.e + d.d + e.c < 3
     and a.c + b.d + c.e < 3
     and a.b + b.c + c.d + d.e < 3
     and a.a + b.b + c.c + d.d + e.e < 3
     and b.a + c.b + d.c + e.d < 3
     and c.a + d.b + e.c < 3)
select rank() over(order by x desc)rn ,x from t3 where y =(select max(y)from t3)

ccnp

呵呵， 我也可以我算出来92种答案直接select 出来， 我也证明了，只有92种答案，在纸上，哈哈，和用=2是半斤八两

ccnp

要不然你找个第93种出来。。。嘿嘿

〇〇

原帖由 rollingpig 于 2011-3-16 09:36 发表
另外，最后的地方用分析函数看似很炫，但是，单纯从代码量以及性能来看，其实，还是不如直接用
y=(select max(y) from t3)


old code:  381 word,     1410  char, run time 5.6 sec
new code1 :  269  word ,  1051 char, tun time 3.7 sec
new code2:  258 word ,  1011 char, tun time 3.4 sec

我这里11.2.0.1

new code1 : 00: 00: 02.04

new code2 : 00: 00: 02.20

accelerator

另外,贴一下我的答案,序号RT,我就认为很不错   因为

性能考虑 where l1.c+l2.c+l3.c+l4.c+l5.c =2)  , 我最后改为 =2 from <3.

算法跟lastwinner贴出的基本一致,不然也可以成为good model 了.





with
a as (SELECT 1 c FROM DUAL UNION SELECT 0 FROM DUAL)        
,b as (select l1.c c1,l2.c c2,l3.c c3,l4.c c4,l5.c c5,  l1.c+l2.c+l3.c+l4.c+l5.c cnt, l1.c||l2.c||l3.c||l4.c||l5.c  str
         from a l1,a l2,a l3,a l4,a l5
         where l1.c+l2.c+l3.c+l4.c+l5.c =2)  
,c as(
        select  str
        from
        (   
        select
        rank() over(order by l1.cnt+l2.cnt+l3.cnt+l4.cnt+l5.cnt  desc )seq  ,          
         l1.str||l2.str||l3.str||l4.str||l5.str   str            
        from b l1, b l2, b l3, b l4, b l5
        where   l1.c1+l2.c1+l3.c1+l4.c1+l5.c1 <3
            and l1.c2+l2.c2+l3.c2+l4.c2+l5.c2<3
            and l1.c3+l2.c3+l3.c3+l4.c3+l5.c3 <3
            and l1.c4+l2.c4+l3.c4+l4.c4+l5.c4 <3
            and l1.c5+l2.c5+l3.c5+l4.c5+l5.c5 <3                         
            and l3.c1+l4.c2+l5.c3<3
            and l2.c1+l3.c2+l4.c3+l5.c4<3
            and l1.c1+l2.c2+l3.c3+l4.c4+l5.c5<3
            and l1.c2+l2.c3+l3.c4+l4.c5<3
            and l1.c3+l2.c4+l3.c5<3             
            and l1.c3+l2.c2+l3.c1<3
            and l1.c4+l2.c3+l3.c2+l4.c1<3
            and l1.c5+l2.c4+l3.c3+l4.c2+l5.c1<3
            and l2.c5+l3.c4+l4.c3+l5.c2<3
            and l3.c5+l4.c4+l5.c3<3       
        ) t where seq =1
        order by str desc       
  )
select rownum, str from c