Puzzleup 2010 比赛快开始了，大家用SQL解答啊

lastwinner

嗯，我当时就是按贪吃蛇去想的

newkid

第7题：

Neighboring Digits



We have a number. All the digits of this number are different from one another and all the digits except the first and the last have a greater value than the mean of its neighbors (ie. the digits immediately to the left and to the right).

What can this number be at maximum?

有一个数，它的每一位都不相同。除了首位和末尾，其他的每一位都比它的左右邻居（左边一位数和右边一位数）的平均值更大。这个数最大可能是多少？

递归WITH:
WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<=9
   UNION ALL
   SELECT str||rn
     FROM t,(SELECT ROWNUM RN FROM DUAL CONNECT BY ROWNUM<=9)
    WHERE INSTR(str,rn)=0
          AND (LENGTH(str)<2
               OR rn+SUBSTR(str,-2,1) <SUBSTR(str,-1,1)*2
               )
)
SELECT MAX(TO_NUMBER(str)) FROM t;


MAX(TO_NUMBER(str))
--------------------
              479863

durexlollipop

689740

szusunny

原帖由 newkid 于 2010-8-26 23:16 发表
第7题：

Neighboring Digits



We have a number. All the digits of this number are different from one another and all the digits except the first and the last have a greater value than the mean of its neighbors (ie. the digits immediately to the left and to the right).

What can this number be at maximum?

有一个数，它的每一位都不相同。除了首位和末尾，其他的每一位都比它的左右邻居（左边一位数和右边一位数）的平均值更大。这个数最大可能是多少？

递归WITH:
WITH t(str) AS (
   SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM

newkid为什么忽略0呢?
最大应该是3689740.

szusunny

with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
           and prior x + y < (prior y)*2
           and prior x <> y
           and prior y = x

-- Result

           RES
1        3689740

lastwinner

人肉：
假设有一五位数满足52楼题设条件，记这个数为abcde
那一定有 2b>a+c , 2c>b+d, 2d>c+e
于是c<2b-a, c<2d-e ,推出 2c<2b+2d-a-e ，结合 2c>b+d
可得2b+2d-a-e>b+d， 推出b+d>a+e
即以中间的数为轴心，最靠近中间的两个数之和>次靠近中间的两个数之和>....>最外层两个数之和————（1）

假设有一四位数满足52楼题设条件，记这个数为abcd
则类似可得b+c>a+d,可推出最中间的两个数之和>次中间的两个数之和>....>最外层两个数之和—————（2）

上面表明了一个数要满足52楼的题设，应具备的条件（奇位数满足1，偶位数满足2）

构造方法的论述：
从0～9中任取一个数A开始构造，构造时以该数为中心，逐步往左右两边推出其他数，直至无法再推下去为止。这样的数可能能推出不止一个，最大的一个数称为由A开始构造的最大邻居数。

如果有一个满足题设的数B，其最左边或最右边的数最大，那可以尝试从最大的数的右边或者左边继续构造符合题设的数，直至构造并找出以B为基础的最大邻居数。
——————————————————————————写完发现其实以上都没啥用，不过有助于思考问题————————————————
——————————————————————————我最终无法证明9在最中央才能取得最大的数—————————————————
由前，对于abcde，可得 b>(a+c)/2>c/2, c>(b+d)/2>b/2
可能的b和c总共有16组（考虑对称性，令b>c）

1. with tt as (select rownum-1 r from dual connect by rownum<11)
   
2. select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r
   
3. /
   
4.          B          C
   
5. ---------- ----------
   
6.          3          2
   
7.          4          3
   
8.          5          3
   
9.          5          4
   
10.          6          4
    
11.          6          5
    
12.          7          4
    
13.          7          5
    
14.          7          6
    
15.          8          5
    
16.          8          6
    
17.          8          7
    
18.          9          5
    
19.          9          6
    
20.          9          7
    
21.          9          8
    
22. 
    
23. 已选择16行。

复制代码

左右两边各自衔接自己，得
with tt as (select rownum-1 r from dual connect by rownum<11),
t as (select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r)
--select ta.b, ta.c, tb.c d from t ta, t tb where ta.c=tb.b and ta.c*2>ta.b+tb.c
select ta.c a, tb.b, tb.c, tc.c d from t ta, t tb, t tc where tb.c=tc.b and tb.c*2>tb.b+tc.c
and ta.b=tb.b and tb.b*2>tb.c+ta.c and ta.c<>tc.c and ta.c<>tb.c
/

         A          B          C          D
---------- ---------- ---------- ----------
         4          6          5          3
         5          7          6          4
         6          8          7          5
         6          8          7          4
         5          8          7          4
         8          9          7          4
         6          9          7          4
         5          9          7          4
         7          9          8          6
         7          9          8          5
         6          9          8          5
         5          9          8          6

已选择12行。


再在左右两边各自衔接原始的待选数，发现右边连接不了了，左边还可以连接
with tt as (select rownum-1 r from dual connect by rownum<11),
t as (select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r),
abcd as (select ta.c a, tb.b, tb.c, tc.c d, ta.c||tb.b||tb.c||tc.c str from t ta, t tb, t tc where tb.c=tc.b and tb.c*2>tb.b+tc.c
and ta.b=tb.b and tb.b*2>tb.c+ta.c and ta.c<>tc.c and ta.c<>tb.c)
select tg.c g, abcd.a, abcd.b, abcd.c, abcd.d--, te.c e
from abcd, t tg--, t te
where abcd.a=tg.b and abcd.a*2>abcd.b+tg.c and instr(abcd.str, tg.c)=0
--and abcd.d=te.b and abcd.d*2>abcd.c+te.c and instr(abcd.str, te.c)=0
/

         G          A          B          C          D
---------- ---------- ---------- ---------- ----------
         4          7          9          8          5
         4          7          9          8          6
         5          8          9          7          4
         6          8          9          7          4

四组数是对称的右边既然连接不了了，左边自然也连接不了
考虑到最外侧两个数的特殊性，故而从这几个数开始尝试构造再大一些的邻居数
47985，左侧只能填0，右侧只能填1
47986，左侧只能填0，右侧能填3、2、1
58974，左侧只能填2、1，右侧只能填0
68974，左侧能填3、2、1，右侧只能填0

综上，最大的邻居数为3689740
————————————————————只有得出了结果，我才能说9在最中央才能得到最大的邻居数—————————————————

lastwinner

原帖由 szusunny 于 10-8-27 09:29 发表
with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
           and prior x + y < (prior y)*2
           and prior x <> y
           and prior y = x  

lastwinner

with t as (select 3689740 cd from dual),
sp as (select substr(cd, rownum, 1) spn, rownum rn from t connect by rownum <=length(cd))
select spn, (case when rn between 1+1 and count(*)over() -1 then
                  (case when spn>
                          (sum(spn)over(order by rn asc rows between 1 preceding  and 1 following)-spn)/2
                    then 1 else 0 end )
                  else null end)  rlt
from sp
/

SP RLT
-- ---
3
6    1
8    1
9    1
7    1
4    1
0

已选择7行。

〇〇

nice 花花

newkid

原帖由 szusunny 于 2010-8-27 09:29 发表
with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
           and prior x + y < (prior y)*2
           and prior x <> y
           and prior y = x

-- Result

           RES
1        3689740

我大意了，忘记0也可以用。
你这个帖子我要收藏，原来我也想过用CONNECT BY, 但不知道怎么访问超过一层的数据。看了你写的才茅塞顿开，原来只需先做一个自连接！