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

lastwinner

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

哈哈，就知道会有人用sum log的方法去求乘积
进一步优化就是先求出sum后的最大值，再exp得出结果

lastwinner

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


sql无法提前退出查找

我意思是人为的分步去做，因为第一步所需要的时间其实是很短的，300^2=9万，而900^2=81万，仅此就可以减少91%的组合

〇〇

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


哈哈，就知道会有人用sum log的方法去求乘积
进一步优化就是先求出sum后的最大值，再exp得出结果

我的最后1个修改，求最大连续积没法做的。。
       622 889524345
       632 6585412275886668811642717147992444292823
       673 863465674813919123162824586178664583591245665294765456828489128831426
       743 769

〇〇

最小公倍数，不知道哪里错了
with t as(select level l from dual connect by level<=20)
select l,gcd,a,b,tmp
from t
MODEL IGNORE NAV RETURN UPDATED ROWS
DIMENSION BY (l)
MEASURES (1 a/*最小公倍数*/,1 b, 0 tmp,1 gcd/*最大公约数*/,0 tmpb,1 tmpa,0 flag)
RULES UPDATE ITERATE (20)until tmpa[1]=0 --余数为0表示求出gcd
(
a[1]=1,
gcd[1]=1,
--b[any]=cv[l]+1,
tmpa[1]=case when cv(l)>1 and flag[1]=0 then a[cv()] else tmpa[1] end,
tmpb[1]=case when cv(l)>1 and flag[1]=0 then cv(l)+1 else tmpb[1] end,
--start loop
tmp[1]=tmpa[1], --辗转相除法求gcd，存入tmpb[1]
tmpa[1]=mod(tmpb[1],tmpa[1]),
tmpb[1]=tmp[1],
--end loop
gcd[any]=case when cv(l)>1 and tmpa[1]=0 then tmpb[1] else gcd[cv()] end,
a[any]=case when cv(l)>1 and tmpa[1]=0 then a[cv()-1]*(cv(l)+1)/gcd[cv()-1] else a[cv()] end,
flag[1]=case when cv(l)>1 and tmpa[1]=0 then 0 else 1 end
);

[ 本帖最后由 〇〇 于 2010-11-5 21:45 编辑 ]

lastwinner

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

我的最后1个修改，求最大连续积没法做的。。
       622 889524345
       632 6585412275886668811642717147992444292823
       673 863465674813919123162824586178664583591245665294765456828489128831426
       743 769

overflow了？
那你换个思路，用log，然后相加比大小

其次，既然是最大连续积，就以0为分界点去逐段处理就行

newkid

先用对数和求出最大的，然后用MODEL拼出这个大数。等我有空搞一下。

lastwinner

原帖由 newkid 于 10-11-5 23:13 发表
先用对数和求出最大的，然后用MODEL拼出这个大数。等我有空搞一下。

我一直没学model，诶
不过这问题不用那么复杂，拆分＋分组拆分＋分组求和＋比和的大小就行了，不麻烦的

lastwinner

原帖由 lastwinner 于 10-11-5 23:19 发表


我一直没学model，诶
不过这问题不用那么复杂，拆分＋分组拆分＋分组求和＋比和的大小就行了，不麻烦的

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 substr(x,st+1,en-st-1) numgroup, st+1 st, en from(
            select decode(rn,1,0,instr(x,'0',1,rn-1)) st ,decode(instr(x,'0',1,rn),0,length(x)+1, instr(x,'0',1,rn)) en
            from s, (select rownum rn from s connect by rownum<=length(x)-length(replace(x,'0',''))+1)), s
           where en>st+1  --过滤掉连续的0导致的空
        ),
sln as (select numgroup, st, en, sum(ln(to_number(substr(numgroup, rn, 1)))) sum_ln_num
    from sp, (select rownum rn from (select max(en-st+1) maxlen from sp) connect by rownum<=maxlen)
    where rn<=en-st   group by numgroup, st, en) --分组求出ln的和
select  st, en, numgroup, sum_ln_num, exp(sum_ln_num) product, rank()over(order by sum_ln_num desc) rk from sln;



  ST    EN NUMGROUP                                                               SUM_LN_NUM    PRODUCT         RK
---- ----- ---------------------------------------------------------------------- ---------- ---------- ----------
674   743 863465674813919123162824586178664583591245665294765456828489128831426  97.5892154 2.4124E+42          1
  15    58 6249192251196744265747423553491949349698352                            60.3528832 1.6253E+26          2
633   673 6585412275886668811642717147992444292823                               54.9074834 7.0148E+23          3
530   565 86256932197846862248283972241375657                                    50.8663833 1.2331E+22          4
485   518 632441572215539753697817977846174                                      47.1054138 2.8683E+20          5
940   967 559357297257163626956188267                                            40.5099976 3.9198E+17          6
234   264 987111217223831136222989342338                                          33.423018 3.2767E+14          7
  88   108 18694788518438586156                                                   30.6945771 2.1404E+13          8
353   372 1724271218839987979                                                    27.3752117 7.7429E+11          9
830   846 9878799272442849                                                        27.103278 5.8993E+11         10
285   302 64444866452387493                                                      26.4948721 3.2105E+11         11
196   211 435576689664895                                                         26.365795 2.8218E+11         12
109   125 7891129494954595                                                       24.6918186 5.2908E+10         13
579   596 79729686524145351                                                       24.035039 2.7434E+10         14
156   171 698747158523863                                                        23.4064304 1.4631E+10         15
812   829 96245544436298123                                                       23.098129 1.0750E+10         16
126   143 17379583319528532                                                      23.0542098 1.0288E+10         17
212   231 4452445231617318564                                                    22.9521751 9289728000         18
863   878 979191338754992                                                        22.8434888 8332994880         19
442   457 594752243525849                                                        22.1944894 4354560000         20
267   284 81353362766142828                                                      21.9305239 3344302080         21
396   409 9377665727333                                                          20.2614184  630118440         22
473   484 48395864467                                                              18.75247  139345920         23
  67    80 6326239578318                                                          18.1771059   78382080         24
183   195 963295227443                                                           16.7908115   19595520         25
373   384 87922749219                                                            16.0286715    9144576         26
   1    14 7316717653133                                                          15.4251365    5000940         27
884   894 6368991256                                                             15.2503665    4199040         28
519   529 6495514929                                                             15.0680449    3499200         29
788   797 694165896                                                              14.8449014    2799360         30
902   913 58861164671                                                            14.4758039    1935360         31
623   632 889524345                                                              14.1393317    1382400         32
598   608 4748216637                                                              14.119129    1354752         33
926   937 22569831552                                                            14.0747932    1296000         34
847   855 91888458                                                                13.510723     737280         35
968   978 4282524836                                                              13.510723     737280         36
413   423 5336788122                                                             13.0895096     483840         37
432   441 975125454                                                              12.4371844     252000         38
992  1000 75296345                                                               12.3318239     226800         39
174   182 71569329                                                               11.5333162     102060         40
980   988 82325753                                                               10.8277465      50400         41
336   343 5158593                                                                10.2035921      27000         42
614   620 319989                                                                 9.76972756      17496         43
  81    87 169848                                                                 9.53416149      13824         44
308   314 729629                                                                 9.51841313      13608         45
763   775 556263211111                                                           9.28730141      10800         46
385   391 169972                                                                 8.82526595       6804         47
  59    66 3127745                                                                8.67931204       5880         48
780   787 5442175                                                                8.63052188       5600         49
324   329 77239                                                                  7.88080434       2646         50
458   464 771167                                                                 7.62948992       2058         51
348   352 8667                                                                   7.60887063       2016         52
802   807 71984                                                                  7.60887063       2016         52
424   431 2354218                                                                7.56008047       1920         54
569   573 5749                                                                     7.138867       1260         55
749   756 4224219                                                                7.04925484       1152         56
303   307 3589                                                                   6.98471632       1080         57
856   862 156166                                                                 6.98471632       1080         58
315   320 49156                                                                  6.98471632       1080         58
147   155 55111254                                                               6.90775528       1000         60
919   924 77541                                                                  6.88755257        980         61
392   395 888                                                                    6.23832463        512         62
609   613 4844                                                                   6.23832463        512         63
344   347 796                                                                     5.9348942        378         64
744   747 769                                                                     5.9348942        378         64
895   899 7176                                                                   5.68357977        294         66
776   779 937                                                                    5.24174702        189         67
330   335 71381                                                                  5.12396398        168         68
757   762 22671                                                                  5.12396398        168         68
465   468 556                                                                    5.01063529        150         70
808   811 385                                                                    4.78749174        120         71
144   146 88                                                                     4.15888308         64         72
574   578 2614                                                                   3.87120101         48         73
880   883 524                                                                    3.68887945         40         74
914   916 94                                                                     3.58351894         36         75
566   568 56                                                                     3.40119738         30         76
469   472 136                                                                    2.89037176         18         77
321   323 44                                                                     2.77258872         16         78
800   801 8                                                                      2.07944154          8         79
989   991 42                                                                     2.07944154          8         80
900   901 6                                                                      1.79175947          6         81
917   918 5                                                                      1.60943791          5         82
172   173 5                                                                      1.60943791          5         82
798   799 4                                                                      1.38629436          4         84
232   233 3                                                                      1.09861229          3         85
265   266 3                                                                      1.09861229          3         85
411   412 1                                                                               0          1         87

已选择87行。

已用时间:  00: 00: 00.29
SCOTT@lw.lw>

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)
,d AS (SELECT ROWNUM n FROM s CONNECT BY ROWNUM<=LENGTH(x))
,t AS (
SELECT d1.n pos
      ,d2.n len
      ,d3.n pos2
      ,TO_NUMBER(SUBSTR(x,d1.n+d3.n-1,1)) n
  FROM s,d d1, d d2, d d3
WHERE d1.n + d2.n -1 <= LENGTH(x) AND d3.n<=d2.n
       AND INSTR(SUBSTR(x,d1.n,d2.n),'0')=0
)
,t2 AS (
SELECT LEVEL n, TO_NUMBER(SUBSTR(x,pos+LEVEL-1,1)) val,pos,len
  FROM (SELECT pos,len
          FROM (
                 SELECT pos,len,SUM(LN(n))
                   FROM t
                  GROUP BY pos,len
                  ORDER BY 3 DESC
               )
        WHERE ROWNUM=1
        )
       ,s
CONNECT BY LEVEL<=len
  )
,tmp AS
(SELECT *
   FROM (SELECT n,col,prod,val,len,pos
           FROM t2
               ,( SELECT ROWNUM col
                -- 构造一个30 行的集合，这个集合的每一行用于存放30 位的临时计算结果
                FROM DUAL
                CONNECT BY ROWNUM<=30
                ) -- 上述两个集合做笛卡儿积，就为每个乘数n 分配了30 个col 作临时存放单元，
          -- 最大可表示900 位的数字，用于存放对n 做阶乘的结果
         MODEL IGNORE NAV RETURN UPDATED ROWS
         DIMENSION BY (n,col) -- 用于定位到单元格的唯一标识
         MEASURES (0 prod,val,len,pos ) -- prod 用于存放30 位的计算结果
         RULES (
                prod[any,any] order by n,col
                -- MODEL 的规则指定n 从1～len,每个n 的col 从1～30 的顺序进行下列运算
                =(CASE WHEN cv(n)=1 AND cv(col)=1 THEN val[1,1] -- 递归计算起点
                       ELSE MOD(prod[cv()-1,cv()],1E30)*val[cv(),1]
                            --取出在相同位置（col 相同）
                            --的计算结果的后30 位，乘以当前乘数val[cv(),1]
                            +TRUNC(prod[cv(),cv()-1]/1E30)
                             -- 再加上上一步乘法运算（位置col-1）的结果的进位部分
                  END)
                )
         )
   WHERE n=len -- 在计算的结果中取出最后的那些单元格，用于拼接输出
   )
SELECT SUBSTR(x,pos,len) str,pos,len,prod
  FROM (SELECT MAX(pos) pos
               ,MAX(len) len
               ,LTRIM(REPLACE(MAX(SYS_CONNECT_BY_PATH(LPAD(MOD(prod,1E30),30,'0'),'*')),'*'),'0') as prod
           FROM tmp
         START WITH col=(SELECT MAX(col) FROM tmp WHERE prod>0)
         CONNECT BY col = PRIOR col-1
        )
       ,s
;

STR
----------------------------------------------------------------------------------------
       POS        LEN
---------- ----------
PROD
----------------------------------------------------------------------------------------
863465674813919123162824586178664583591245665294765456828489128831426
       674         69
2412446685431734624320887406251212800000000


Elapsed: 00:00:08.62

newkid

你只能知道个大概2.4124E+42，我知道它是2412446685431734624320887406251212800000000，这就是区别。