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

tree_new_bee

另外200p的循环可以去掉， 就两个情况， =1的话只有一个组合， 所以只考虑=0，然后最后加1就行了。
辛辛苦苦加那么多提示信息， 就怕优化器不理睬你， 加个RULE, 确保让这些信息派上用场。

with t as (select /*+ RESULT_CACHE */  rownum-1 n from dual connect by rownum<=41)
select /*+ RULE */ sum(floor((200-(t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 ))/2)+1)+1
from
(select * from t where n<=40) t3,
(select * from t where n<=20) t4,
(select * from t where n<=10) t5,
(select * from t where n<=5) t6,
(select * from t where n<=2) t7
where --t8.n in(0,1) and t7.n in(0,1,2) and t6.n<=4 and t5.n <=10 and t4.n<=20 and t3.n<=40 and t2.n<=100 and
    mod(200 - ( t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 ),5) = 0
and mod(200 - (          t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 ),10) = 0
and mod(200 - (                              t6.n*50 + t7.n*100 ),50) = 0
and mod(200 - (                                        t7.n*100 ),100) = 0
and t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100  >=0
and t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100  <=200

SUM(FLOOR((200-(T3.N*5+T4.N*10
------------------------------
                         73682

Executed in 0.563 seconds

SQL>

tree_new_bee

原帖由 newkid 于 2010-12-20 22:34 发表
NB哥真快，看题都赶不上你做题了。
那个硬币问题我也做过，还用过递归WITH。
Q29我想把100以内的数分解质因子，然后把幂变成系数，看看总共有几种。你后来用的方法更好，只关心那些可能重复的。

呵呵。最近比较闲， 就把精力全放这个上了， 过几天一忙就没那么多时间搞了。


Q29我开始的思路也是往分解质因子考虑的， 后来发现比如6与2与3都没冲突，就放弃了那条思路。

newkid

不含人肉成分：
SELECT COUNT(*) FROM
(SELECT 2 c,2*(ROWNUM-1) v FROM DUAL CONNECT BY 2*(ROWNUM-1)<=200) t2
,(SELECT 5 c,5*(ROWNUM-1) v FROM DUAL CONNECT BY 5*(ROWNUM-1)<=200) t5
,(SELECT 10 c,10*(ROWNUM-1) v FROM DUAL CONNECT BY 10*(ROWNUM-1)<=200) t10
,(SELECT 20 c,20*(ROWNUM-1) v FROM DUAL CONNECT BY 20*(ROWNUM-1)<=200) t20
,(SELECT 50 c,50*(ROWNUM-1) v FROM DUAL CONNECT BY 50*(ROWNUM-1)<=200) t50
,(SELECT 100 c,100*(ROWNUM-1) v FROM DUAL CONNECT BY 100*(ROWNUM-1)<=200) t100
,(SELECT 200 c,200*(ROWNUM-1) v FROM DUAL CONNECT BY 200*(ROWNUM-1)<=200) t200
WHERE t2.v+t5.v+t10.v+t20.v+t50.v+t100.v+t200.v <=200
;

  COUNT(*)
----------
     73682

Elapsed: 00:00:23.91

tree_new_bee

原帖由 newkid 于 2010-12-20 23:53 发表
不含人肉成分：

不含人肉成分，竟然都能20多秒， 机器性能强啊。

newkid

呵呵，i5-750 CPU+4G ram, 不算什么好机器。

不能说没有人肉，我其实去掉了1便士的表。把2磅的表也去掉：

jsu@JSU> SELECT COUNT(*) FROM
  2  (SELECT 2 c,2*(ROWNUM-1) v FROM DUAL CONNECT BY 2*(ROWNUM-1)<=200) t2
  3  ,(SELECT 5 c,5*(ROWNUM-1) v FROM DUAL CONNECT BY 5*(ROWNUM-1)<=200) t5
  4  ,(SELECT 10 c,10*(ROWNUM-1) v FROM DUAL CONNECT BY 10*(ROWNUM-1)<=200) t10
  5  ,(SELECT 20 c,20*(ROWNUM-1) v FROM DUAL CONNECT BY 20*(ROWNUM-1)<=200) t20
  6  ,(SELECT 50 c,50*(ROWNUM-1) v FROM DUAL CONNECT BY 50*(ROWNUM-1)<=200) t50
  7  ,(SELECT 100 c,100*(ROWNUM-1) v FROM DUAL CONNECT BY 100*(ROWNUM-1)<=200) t100
  8  WHERE t2.v+t5.v+t10.v+t20.v+t50.v+t100.v <=200
  9  ;

  COUNT(*)
----------
     73681

Elapsed: 00:00:11.65

newkid

Q24, 0123456789 排列后第1000000个数：

VAR str VARCHAR2(100);
EXEC :str := '0123456789';

VAR n NUMBER;
EXEC :n := 1000000;


WITH d AS (
SELECT lvl,TRUNC(MOD(:n-MOD(:n+1,2),p*(lvl+1))/p) m  ----对于每位阶乘的权，奇偶数要分别处理
  FROM ( SELECT LEVEL lvl,ROUND(EXP(SUM(LN(LEVEL)) OVER(ORDER BY LEVEL))) p ---- 求阶乘
           FROM DUAL
          CONNECT BY LEVEL<=LENGTH(:str)-1
        )
)
,t (lvl,s) AS (
  SELECT lvl
        ,CAST(SUBSTR(:str,m+CASE WHEN lvl=MOD(:n,2) THEN 0 ELSE 1 END,1) AS VARCHAR2(100)) ---- 奇数的最右边一位要特殊处理
    FROM d
   WHERE lvl=LENGTH(:str)-1
  UNION ALL
  SELECT t.lvl-1
        ,t.s||SUBSTR(TRANSLATE(:str,'$'||t.s,'$'),d.m+CASE WHEN d.lvl=MOD(:n,2) THEN 0 ELSE 1 END,1) ---- 用TRANSLATE求出剩下的字符，算出应该取第几个
    FROM t,d
   WHERE t.lvl-1=d.lvl
   )
SELECT s||TRANSLATE(:str,'$'||t.s,'$') s FROM t WHERE lvl=1;


S
---------------------
2783915460

用了一次递归，阶乘用了对数反对数其实也是递归。通过观察发现奇偶数的计算方法略有不同，利用MOD 2整合到一起，就是代码比较难懂。

newkid

Q25用浮点数的方法很巧妙，只是不知道是否误差会积累？

newkid

用大数算法做Q25,

WITH t(r
      ,a1
      ,a2
      ,a3
      ,a4
      ,a5
      ,a6
      ,a7
      ,a8
      ,a9
      ,a10
      ,a11
      ,a12
      ,a13
      ,a14
      ,a15
      ,a16
      ,a17
      ,a18
      ,a19
      ,a20
      ,a21
      ,a22
      ,a23
      ,a24
      ,a25
      ,a26
      ,a27
      ,a28
      ,a29
      ,a30
      ,b1
      ,b2
      ,b3
      ,b4
      ,b5
      ,b6
      ,b7
      ,b8
      ,b9
      ,b10
      ,b11
      ,b12
      ,b13
      ,b14
      ,b15
      ,b16
      ,b17
      ,b18
      ,b19
      ,b20
      ,b21
      ,b22
      ,b23
      ,b24
      ,b25
      ,b26
      ,b27
      ,b28
      ,b29
      ,b30
      )
AS (
SELECT 1 R
      ,0 a1
      ,0 a2
      ,0 a3
      ,0 a4
      ,0 a5
      ,0 a6
      ,0 a7
      ,0 a8
      ,0 a9
      ,0 a10
      ,0 a11
      ,0 a12
      ,0 a13
      ,0 a14
      ,0 a15
      ,0 a16
      ,0 a17
      ,0 a18
      ,0 a19
      ,0 a20
      ,0 a21
      ,0 a22
      ,0 a23
      ,0 a24
      ,0 a25
      ,0 a26
      ,0 a27
      ,0 a28
      ,0 a29
      ,0 a30
      ,1 b1
      ,0 b2
      ,0 b3
      ,0 b4
      ,0 b5
      ,0 b6
      ,0 b7
      ,0 b8
      ,0 b9
      ,0 b10
      ,0 b11
      ,0 b12
      ,0 b13
      ,0 b14
      ,0 b15
      ,0 b16
      ,0 b17
      ,0 b18
      ,0 b19
      ,0 b20
      ,0 b21
      ,0 b22
      ,0 b23
      ,0 b24
      ,0 b25
      ,0 b26
      ,0 b27
      ,0 b28
      ,0 b29
      ,0 b30
FROM DUAL
UNION ALL
SELECT r+1
      ,b1
      ,b2
      ,b3
      ,b4
      ,b5
      ,b6
      ,b7
      ,b8
      ,b9
      ,b10
      ,b11
      ,b12
      ,b13
      ,b14
      ,b15
      ,b16
      ,b17
      ,b18
      ,b19
      ,b20
      ,b21
      ,b22
      ,b23
      ,b24
      ,b25
      ,b26
      ,b27
      ,b28
      ,b29
      ,b30
      ,MOD(a1  + b1 ,1e34)
      ,MOD(a2  + b2  + CASE WHEN a1  + b1 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a3  + b3  + CASE WHEN a2  + b2 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a4  + b4  + CASE WHEN a3  + b3 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a5  + b5  + CASE WHEN a4  + b4 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a6  + b6  + CASE WHEN a5  + b5 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a7  + b7  + CASE WHEN a6  + b6 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a8  + b8  + CASE WHEN a7  + b7 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a9  + b9  + CASE WHEN a8  + b8 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a10 + b10 + CASE WHEN a9  + b9 >1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a11 + b11 + CASE WHEN a10 + b10>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a12 + b12 + CASE WHEN a11 + b11>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a13 + b13 + CASE WHEN a12 + b12>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a14 + b14 + CASE WHEN a13 + b13>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a15 + b15 + CASE WHEN a14 + b14>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a16 + b16 + CASE WHEN a15 + b15>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a17 + b17 + CASE WHEN a16 + b16>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a18 + b18 + CASE WHEN a17 + b17>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a19 + b19 + CASE WHEN a18 + b18>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a20 + b20 + CASE WHEN a19 + b19>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a21 + b21 + CASE WHEN a20 + b20>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a22 + b22 + CASE WHEN a21 + b21>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a23 + b23 + CASE WHEN a22 + b22>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a24 + b24 + CASE WHEN a23 + b23>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a25 + b25 + CASE WHEN a24 + b24>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a26 + b26 + CASE WHEN a25 + b25>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a27 + b27 + CASE WHEN a26 + b26>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a28 + b28 + CASE WHEN a27 + b27>1e34 THEN 1 ELSE 0 END,1e34)
      ,MOD(a29 + b29 + CASE WHEN a28 + b28>1e34 THEN 1 ELSE 0 END,1e34)
      ,a30 + b30 + CASE WHEN a29 + b29>1e34 THEN 1 ELSE 0 END
  FROM t
WHERE b30<1e13
)      
CYCLE r SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT MAX(r) FROM t;

    MAX(R)
----------
      4782

Elapsed: 00:00:00.10

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

tree_new_bee

原帖由 newkid 于 2010-12-21 05:17 发表
Q25用浮点数的方法很巧妙，只是不知道是否误差会积累？

精度问题的风险确实有。

不过对于38位的精度，传递到1000位的数字，要引起位数的变化还是比较难的。

测试了一下，人为设置6位以上的精度， 得到的位数就已经稳定下来了。

不管怎么说，还是大数运算保险。

tree_new_bee

原帖由 newkid 于 2010-12-21 05:05 发表
Q24, 0123456789 排列后第1000000个数：


WITH d AS (
SELECT lvl,TRUNC(MOD(:n-MOD(:n+1,2),p*(lvl+1))/p) m  ----对于每位阶乘的权，奇偶数要分别处理
  FROM ( SELECT LEVEL lvl,ROUND(EXP(SUM(LN(LEVEL)) OVER(ORDER BY LEVEL))) p ---- 求阶乘
           FROM DUAL
          CONNECT BY LEVEL<=LENGTH(:str)-1
        )

原来这一段直接就能得到那些序号， 我用递归搞得复杂化了。