Euler Project 挨个做 - 之一(Q1-50)

〇〇

原帖由 tree_new_bee 于 2010-12-22 13:17 发表
可以稍微优化一点的地方是：
偶数的二进制结尾都是0， 既然不能计算前导0， 所以所有的偶数可以跳过。

with t0 as (select * from (select rownum*2-1 n from dual connect by rownum0
)
select *  from tbin where d=0 and bin = reverse(bin)

  SUM(NUM)
----------
    872187

Executed in 1.39 seconds


节省了将近一半的时间。

with t0 as (select * from (select rownum n from dual connect by rownum<=1000000) where n = reverse(to_char(n)))
, tbin(num,d, bin) as(
select n, n,  '' from t0
union all
select
num,
trunc(d/2),
mod(d,2)||bin
from tbin where d>0
)
select sum(num) from tbin where d=0 and bin = reverse(bin)
;

M(NUM)
------
872187

时间:  00: 00: 01.91
select count(*) from (select rownum n from dual connect by rownum<=1000000) where n = reverse(to_char(n));

UNT(*)
------
  1998

时间:  00: 00: 01.09
可见主要时间用在第1步
如果人肉生成第一步，则可以省很多时间

with
s as (select level-1 n from dual connect by level<=10) --只要不是末位可取值
,t as (select level*2-1 n from dual connect by level<=5) --1位 a
,t0 as (select * from t
union all
select 11*n from s where n>0 --2位aa
union all
select 101*a.n+10*b.n from t a,s b --3位 aba
union all
select 1001*a.n+110*b.n from t a,s b --4位 abba
union all
select 10001*a.n+1010*b.n+100*c.n from t a,s b,s c --5位 abcba
union all
select 100001*a.n+10010*b.n+1100*c.n from t a,s b,s c --6位 abccba
)
select count(*) from t0;

UNT(*)
------
  1114

时间:  00: 00: 00.02
with
s as (select level-1 n from dual connect by level<=10) --只要不是末位可取值
,t as (select level*2-1 n from dual connect by level<=5) --1位 a
,t0 as (select * from t
union all
select 11*n from s where n>0 --2位aa
union all
select 101*a.n+10*b.n from t a,s b --3位 aba
union all
select 1001*a.n+110*b.n from t a,s b --4位 abba
union all
select 10001*a.n+1010*b.n+100*c.n from t a,s b,s c --5位 abcba
union all
select 100001*a.n+10010*b.n+1100*c.n from t a,s b,s c --6位 abccba
)
, tbin(num,d, bin) as(
  select n, n,  '' from t0
  union all
  select
  num,
  trunc(d/2),
  mod(d,2)||bin
  from tbin where d>0
  )
  select sum(num) from tbin where d=0 and bin = reverse(bin)
  ;

M(NUM)
------
872187

时间:  00: 00: 00.43

奇怪的是我和tnb的t0不同，结果居然相同

〇〇

明白了我多算了1倍，算奇数的时候2*n-1,我从上面贴代码n没有减半

〇〇

我的还多算了4个，不过在2进制全被删除了
select 11*n from s where n>0 --2位aa
应该是
select 11*n from t where n>0 --2位aa

〇〇

把问题规模扩大到7位，  
SUM(NUM)
----------
  25846868

已用时间:  00: 00: 03.84

〇〇

其实2进制也有类似规律
1 =2-1
11=2^2-1
101=??
111=2^3-1

〇〇

二进制回文数

with t as (select 0 x from dual union all select 1 from dual)
,bt as(
select power(2,level)-1 n from dual connect by level<=20
union all
select 2^2+2^0+x*2^1 from t --101,111 (111与上面重复了，用union又有排序..)
union all
select 2^3+2^0+x*。。。。

〇〇

186的戏路太繁琐，到后面有8-9个表关联

另一种思路：
对十进制回文数挨个排查
除以power(2,trunc(log(2,n)/2)))的余数和商，从首尾开始对比。。直到找到不一致的退出递归。。。

newkid

这几个思路都挺不错的。

newkid

综合NB哥和OO哥的思路：
WITH n AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') s,LEVEL lvl
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH MOD(n,2)=1
CONNECT BY LEVEL<=3
)
,t AS (
SELECT s||rn||REVERSE(s) s FROM n,(SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10) WHERE n.lvl<3
UNION ALL
SELECT s||REVERSE(s) FROM n
UNION ALL
SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<10
)
SELECT s, b
  FROM (
        SELECT s,
               LTRIM(TRIM(REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(
               REPLACE(TO_CHAR(s,'XXXXXX'),'0','0000')
               ,'1','0001')
               ,'2','0010')
               ,'3','0011')
               ,'4','0100')
               ,'5','0101')
               ,'6','0110')
               ,'7','0111')
               ,'8','1000')
               ,'9','1001')
               ,'A','1010')
               ,'B','1011')
               ,'C','1100')
               ,'D','1101')
               ,'E','1110')
               ,'F','1111')
               ),'0') b
          FROM t
        )
WHERE b = REVERSE(b);

S        B
15351        11101111110111
313        100111001
32223        111110111011111
39993        1001110000111001
585        1001001001
53235        1100111111110011
53835        1101001001001011
717        1011001101
73737        10010000000001001
33        100001
585585        10001110111101110001
7447        1110100010111
99        1100011
9009        10001100110001
1        1
3        11
5        101
7        111
9        1001

19 rows selected.

Elapsed: 00:00:00.07

tree_new_bee

我本以为这个回文数的题目，没有太多优化空间的， 没想到还可以优化到这种程度。
厉害。