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

newkid · 发表于 2010-12-21 23:50

Q34:

写了个不甚优雅的SQL竟然很不优雅地溢出了：
WITH t AS (SELECT ROWNUM n,TO_CHAR(ROWNUM) s FROM DUAL CONNECT BY ROWNUM<=9999999)
SELECT * FROM t
WHERE  DECODE(SUBSTR(s,1,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,2,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,3,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,4,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,5,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,6,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,7,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   =n

ERROR:
ORA-30009: Not enough memory for CONNECT BY operation

6位的没有问题, 但是比NB哥的写法慢了两倍：
WITH t AS (
SELECT t.*
   ,DECODE(SUBSTR(s,1,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,2,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,3,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,4,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,5,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,6,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,7,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   AS sm
  FROM (SELECT ROWNUM n,TO_CHAR(ROWNUM) s FROM DUAL CONNECT BY ROWNUM<=999999) t
)
SELECT * FROM t
WHERE sm=n OR 1+sm=1e6+n OR 2+sm=2e6+n OR 6+sm=3e6+n OR 24+sm=4e6+n
   OR 120+sm=5e6+n OR 720+sm=6e6+n OR 5040+sm=7e6+n OR 40320+sm=8e6+n OR 362880+sm=9e6+n;

[ 本帖最后由 newkid 于 2010-12-21 23:51 编辑 ]

newkid · 发表于 2010-12-22 02:16

Q35 的纯SQL做法：

WITH t0 AS (
SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 1E6/2-1-1
),
t AS(SELECT rn from t0
   where mod(rn,3)<>0
         and mod(rn,5)<>0
         and mod(rn,7)<>0
         and mod(rn,11)<>0
)
,t2 AS (
SELECT TO_CHAR(rn) s,LENGTH(rn) l
FROM (SELECT rn from t
      MINUS
      SELECT t1.rn * t2.rn
         FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 13 AND 1000
            AND t1.rn * t2.rn <1E6
   )
WHERE TRANSLATE(rn, '$1379','$') IS NULL
)
SELECT SUM(MAX(l))+5 AS cnt ---- 前5个是已知的
  FROM (SELECT DECODE(l,2,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1))
                     ,3,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2))
                     ,4,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3))
                     ,5,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3),SUBSTR(s,5)||SUBSTR(s,1,4))
                     ,6,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3),SUBSTR(s,5)||SUBSTR(s,1,4),SUBSTR(s,6)||SUBSTR(s,1,5))
                  ) AS s
            ,l
      FROM t2
   )
GROUP BY s
HAVING COUNT(*)=MAX(l)
/

   CNT
----------
      55

Elapsed: 00:00:06.03

肯定是不如PLSQL快，但是NB哥提供的过滤帮了大忙，所以总体时间可以忍受。

newkid · 发表于 2010-12-22 02:27

Q34, 盗用NB哥的人肉成果，7位情况下前面不超过2, 所以后面的OR都可以丢弃了：
WITH t AS (
SELECT t.*
   ,DECODE(SUBSTR(s,1,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,2,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,3,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,4,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,5,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,6,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   +DECODE(SUBSTR(s,7,1),0,1,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,0)
   AS sm
  FROM (SELECT ROWNUM n,TO_CHAR(ROWNUM) s FROM DUAL CONNECT BY ROWNUM<=999999) t
)
SELECT * FROM t
WHERE sm=n OR 1+sm=1e6+n OR 2+sm=2e6+n;

      N S                                              SM
---------- ---------------------------------------- ----------
      1 1                                              1
      2 2                                              2
   145 145                                           145
   40585 40585                                        40585

Elapsed: 00:00:08.57

newkid · 发表于 2010-12-22 02:50

前面Q35的SQL不太严密，因为n个1构成的循环数可能也是素数。把这几个也排除掉：
WITH t0 AS (
SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= 1E6/2-1-1
),
t AS(SELECT rn from t0
   where mod(rn,3)<>0
         and mod(rn,5)<>0
         and mod(rn,7)<>0
)
,t2 AS (
SELECT TO_CHAR(rn) s,LENGTH(rn) l
FROM (SELECT rn from t
      MINUS
      SELECT t1.rn * t2.rn
         FROM t t1, t t2
      WHERE t1.rn <= t2.rn
            AND t1.rn BETWEEN 11 AND 1000
            AND t1.rn * t2.rn <1E6
   )
WHERE TRANSLATE(rn, '$1379','$') IS NULL
)
SELECT SUM(CASE WHEN s IN ('11','111','1111','11111','111111') THEN 1 ELSE MAX(l) END)+4 AS cnt ---- 前4个是已知的
  FROM (SELECT DECODE(l,2,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1))
                     ,3,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2))
                     ,4,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3))
                     ,5,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3),SUBSTR(s,5)||SUBSTR(s,1,4))
                     ,6,LEAST(s,SUBSTR(s,2)||SUBSTR(s,1,1),SUBSTR(s,3)||SUBSTR(s,1,2),SUBSTR(s,4)||SUBSTR(s,1,3),SUBSTR(s,5)||SUBSTR(s,1,4),SUBSTR(s,6)||SUBSTR(s,1,5))
                  ) AS s
            ,l
      FROM t2
   )
GROUP BY s
HAVING COUNT(*)=MAX(l) OR s IN ('11','111','1111','11111','111111')
/

   CNT
----------
      55

Elapsed: 00:00:07.28

tree_new_bee · 发表于 2010-12-22 11:21

原帖由 newkid 于 2010-12-22 02:50 发表
前面Q35的SQL不太严密，因为n个1构成的循环数可能也是素数。把这几个也排除掉：

SQL取质数的操作，无论怎么优化，还是太慢。

[ 本帖最后由 tree_new_bee 于 2010-12-22 11:31 编辑 ]

tree_new_bee · 发表于 2010-12-22 11:37

原帖由 newkid 于 2010-12-21 23:50 发表
Q34:

写了个不甚优雅的SQL竟然很不优雅地溢出了：

在我这里，通常connect by rownum<=1e6的情况下，就会溢出。

需要修改sort_area_size,或者pga_aggregate_target.

tree_new_bee · 发表于 2010-12-22 13:03

Q36 Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

The decimal number, 585 = 1001001001_(2) (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

tree_new_bee · 发表于 2010-12-22 13:06

用递归的方法进行二进制转换，性能有点让人担心。
所以我借助to_char('X') 来借道十六进制再转换成二进制。

with thex as (
select '0' hex, '0000' bin from dual union all
select '1' hex, '0001' bin from dual union all
select '2' hex, '0010' bin from dual union all
select '3' hex, '0011' bin from dual union all
select '4' hex, '0100' bin from dual union all
select '5' hex, '0101' bin from dual union all
select '6' hex, '0110' bin from dual union all
select '7' hex, '0111' bin from dual union all
select '8' hex, '1000' bin from dual union all
select '9' hex, '1001' bin from dual union all
select 'A' hex, '1010' bin from dual union all
select 'B' hex, '1011' bin from dual union all
select 'C' hex, '1100' bin from dual union all
select 'D' hex, '1101' bin from dual union all
select 'E' hex, '1110' bin from dual union all
select 'F' hex, '1111' bin from dual)
,t as (select * from (select rownum n from dual connect by rownum<=1000000) where n = reverse(to_char(n)))
,t1 as (select n, to_char(n, 'fmXXXXX') hex, pos, bin
from t, thex, (select rownum pos from dual connect by rownum<=5) tpos --1000000=F4240
where pos<=length( to_char(n, 'fmXXXXX')) and substr(to_char(n, 'fmXXXXX'),pos,1) = hex )
,t2 as (select n, hex, ltrim(replace(sys_connect_by_path(bin,'/'),'/', ''),'0') bin from t1
where level = length(hex) start with pos=1 connect by n=prior n and pos=prior pos+1)
--select * from t2 where bin = reverse(bin)
select sum(n) from t2 where bin = reverse(bin)

SUM(N)
----------
872187

Executed in 2.297 seconds

这个性能还可以接受。

产生的中间结果：

      N HEX BIN
---------- ------ --------------------------------------------------------------------------------
      1 1    1
      3 3    11
      5 5    101
      7 7    111
      9 9    1001
      33 21    100001
      99 63    1100011
   313 139 100111001
   585 249 1001001001
   717 2CD 1011001101
   7447 1D17 1110100010111
   9009 2331 10001100110001
   15351 3BF7 11101111110111
   32223 7DDF 111110111011111
   39993 9C39 1001110000111001
   53235 CFF3 1100111111110011
   53835 D24B 1101001001001011
   73737 12009  10010000000001001
585585 8EF71  10001110111101110001

19 rows selected

tree_new_bee · 发表于 2010-12-22 13:12

实际用递归来试验一下，结果发现上面的担心是多余的：递归的性能并不差。
其实主要的原因是，100万以内的回文数(10进制)本来就不太多。

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)

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

Executed in 2.375 seconds

tree_new_bee · 发表于 2010-12-22 13:17

可以稍微优化一点的地方是：
偶数的二进制结尾都是0，既然不能计算前导0，所以所有的偶数可以跳过。

with t0 as (select * from (select rownum*2-1 n from dual connect by rownum<=1000000/2+1) 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 *  from tbin where d=0 and bin = reverse(bin)

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

Executed in 1.39 seconds

节省了将近一半的时间。