Project Euler解题汇总(更新至309在1楼)

newkid

我要求把:N=5也作为变量。
'0'的特性可以用，像96983这类不能用。

lastwinner

原帖由 newkid 于 10-11-5 01:46 发表
我要求把:N=5也作为变量。
'0'的特性可以用，像96983这类不能用。

N不能超过相邻两个0之间的距离的最大值，N过大反而没意义

newkid

原帖由 lastwinner 于 2010-11-5 02:09 发表

N不能超过相邻两个0之间的距离的最大值，N过大反而没意义

不对吧？假如串里面有两个0相连，那么N=2就不行了？N又不一定会覆盖到0.

lastwinner

原帖由 newkid 于 10-11-5 02:30 发表

不对吧？假如串里面有两个0相连，那么N=2就不行了？N又不一定会覆盖到0.

意思是从第一个0到最后一个0，中间可能出现很多0
前一个0到后一个0，中间间隔X位数
N要是大于最大的X，那结果就一定为0了
（{X}包括开头到第一个0之间的位数以及最后一个0到结尾的位数）

newkid

1-20公倍数：递归就是好就是好！

WITH n AS (
SELECT LEVEL n FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<=20
)
,p AS (SELECT * FROM n
       MINUS
       SELECT n1.n * n2.n
         FROM n n1, n n2
       WHERE n1.n <= n2.n
     )
,t(n,p,n_left,path) AS (
SELECT n.n,p.n,n.n/p.n,'/'||TO_CHAR(p.n) FROM n,p WHERE MOD(n.n,p.n)=0
UNION ALL
SELECT t.n,p.n,t.n_left/p.n,t.path||'/'||TO_CHAR(p.n)
  FROM t,p
WHERE t.n_left>1 AND MOD(t.n_left,p.n)=0 AND t.p<=p.n
)
,t2 AS (
SELECT t.*
  FROM t,(SELECT * FROM t WHERE n_left=1) t1
WHERE t1.path||'/' LIKE t.path||'/%' AND t.n=t1.n
)
SELECT EXP(SUM(LN(POWER(p,MAX(cnt)))))
  FROM (SELECT p,COUNT(*) cnt
          FROM t2
         GROUP BY n,p
        )
GROUP BY p;

232792560

MODEL留给OO去做，他最近进步很大。

newkid

借用一下：


with src as (select '73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450' xx from dual),
s as (select regexp_replace(xx,'[^0-9]','') x from src),
sp as (select rownum rn , substr(x, rownum, :n) num from s connect by rownum<=length(x)-:n-1)
SELECT * FROM (
SELECT rn,num,EXP(SUM(LN(SUBSTR(num,l,1)))) prod,RANK() OVER(ORDER BY EXP(SUM(LN(SUBSTR(num,l,1)))) DESC) rnk
  FROM sp,(SELECT LEVEL L FROM DUAL CONNECT BY LEVEL<=:N)
WHERE INSTR(num,'0')=0
GROUP BY rn,num
)
WHERE rnk=1;


        RN
----------
NUM
------------------------------
      PROD        RNK
---------- ----------
       365
99879
     40824          1

〇〇

原帖由 lastwinner 于 2010-11-5 01:27 发表


最后部分可以用reverse函数简化的
另外根据乘法交换律，完全可以认为 b.x>=c.x
而且可以从数字特征去优化算法
比如9只可能由3×3或者1×9得到，8只能是1×8或者2×4，7只能是1×7                  ——略有成效

   select max(a.x) from (select b.x*c.x x from
(select level+100 x from dual connect by level 100000 and substr(a.x,1,3)=reverse(substr(a.x,4));


优先搜索7、8、9为尾数的（说明首位也是7、8、9），找不到再找下面的               
而首位为7的6位数，如果是由两个三位数的乘积构成的，那这个三位数一定不小于700  ——此举大大降低了无谓的劳动

   select max(a.x) from (select b.x*c.x x from
(select level+700 x from dual connect by level 100000 and substr(a.x,1,3)=reverse(substr(a.x,4));

sql无法提前退出查找

〇〇

原帖由 newkid 于 2010-11-5 02:53 发表
借用一下：


with src as (select '73167176531330624919225119674426574742355349194934
。。。。。
71636269561882670428252483600823257530420752963450' xx from dual),
s as (select regexp_replace(xx,'[^0-9]','') x from src),
sp as (select rownum rn , substr(x, rownum, :n) num from s connect by rownum

用log积化和就是好

〇〇

原帖由 newkid 于 2010-11-5 02:53 发表
借用一下：


with src as (select '73167176531330624919225119674426574742355349194934
。。。
71636269561882670428252483600823257530420752963450' xx from dual),
s as (select regexp_replace(xx,'[^0-9]','') x from src),
sp as (select rownum rn , substr(x, rownum, :n) num from s connect by rownum

再次修改一下，要求出最大的连续积及这些连续数字是什么

lastwinner

原帖由 〇〇 于 10-11-5 09:11 发表

再次修改一下，要求出最大的连续积及这些连续数字是什么

这样子这题目将会很难，支持