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

lastwinner · 发表于 2010-11-6 00:56

一直觉得大数计算很神奇，只是一直未深究其原理
但自己也有思路计算大数相乘、相加、相减，不过对于相除还是没啥好招

newkid · 发表于 2010-11-6 01:05

原帖由 lastwinner 于 2010-11-6 00:56 发表
一直觉得大数计算很神奇，只是一直未深究其原理
但自己也有思路计算大数相乘、相加、相减，不过对于相除还是没啥好招

相除要在前面几种的基础上做，老杨的博客有一系列文章。
我在大学上汇编课时，竟然用汇编把四种都实现了，最后得了个低分因为老师看不懂

想想那时候可真猛，现在没那个劲头了。

newkid · 发表于 2010-11-6 01:29

你的前半截比我写得好，再次借用一下，嘻嘻。

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 st pos,en-st len FROM (
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
ORDER BY sum_ln_num DESC
)
WHERE ROWNUM=1
)
,t2 AS (
SELECT LEVEL n, TO_NUMBER(SUBSTR(x,pos+LEVEL-1,1)) val,pos,len
  FROM sln
   ,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
;

lastwinner · 发表于 2010-11-6 02:02

原帖由 newkid 于 10-11-6 00:01 发表
你只能知道个大概2.4124E+42，我知道它是2412446685431734624320887406251212800000000，这就是区别。

嘿嘿，显示问题而已

SCOTT@lw.lw> column product format 999999999999999999999999999999999999999999999999999999999999

  ST EN NUMGROUP                                                             SUM_LN_NUM                                              PRODUCT       RK
---- ----- ---------------------------------------------------------------------- ---------- ------------------------------------------------------------- ----------
674 743 863465674813919123162824586178664583591245665294765456828489128831426  97.5892154             2412446685431734624320887406251212800350000    1
  15 58 6249192251196744265747423553491949349698352                         60.3528832                         162526479904431459532800000       2
633 673 6585412275886668811642717147992444292823                            54.9074834                            701482833551774711808000       3

你的：2412446685431734624320887406251212800000000
我的：2412446685431734624320887406251212800350000

最后几位不一样，不过我相信这是累计误差导致的。肉眼看了下，串中包含的5有6个，偶数很多，所以尾数至少应该是6个0
直接用乘法算就应该不会有问题了

lastwinner · 发表于 2010-11-6 02:06

原帖由 newkid 于 10-11-6 01:05 发表

相除要在前面几种的基础上做，老杨的博客有一系列文章。
我在大学上汇编课时，竟然用汇编把四种都实现了，最后得了个低分因为老师看不懂想想那时候可真猛，现在没那个劲头了。

你基础真是强悍
相除的我也理解了，反正就是模拟稿纸上演算的过程了

相减相加相乘，我都打算采用分段计算的办法去处理，不知这跟你的思路是否一致？

lastwinner · 发表于 2010-11-6 02:17

原帖由 newkid 于 10-11-6 01:29 发表
你的前半截比我写得好，再次借用一下，嘻嘻。

新瓶装老醋

http://www.itpub.net/redirect.ph ... 227&ptid=355415

newkid · 发表于 2010-11-6 03:42

原帖由 lastwinner 于 2010-11-6 02:06 发表

你基础真是强悍
相除的我也理解了，反正就是模拟稿纸上演算的过程了

相减相加相乘，我都打算采用分段计算的办法去处理，不知这跟你的思路是否一致？

就是分段计算，和我们在小学学到的方法一样（那时候是一位一段）。

〇〇 · 发表于 2010-11-6 05:35

原帖由〇〇于 2010-11-5 21:44 发表
最小公倍数，不知道哪里错了
with t as(select level l from dual connect by level1 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-6 05:48

其他题目
题目24 ：What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

题目简介：将数字0, 1, 2, 3, 4, 5, 6, 7, 8 ,9的所有排列按字典顺序排序，求排在第1,000,000位的那个数字。(注

意：从第一位记起)

问题41 ：What is the largest n-digit pandigital prime that exists?

题目简介：一个数称为pandigital，如果它是数字1，2，……，n的一个排列。比如2143就是一个4位的
pandigital。

　　现在求所有pandigital中最大的那个素数。

newkid · 发表于 2010-11-6 06:05

原帖由〇〇于 2010-11-6 05:35 发表

错在哪里呢

最近有些忙还顾不上看。你为什么用辗转相除法？

[转载] Project Euler解题汇总(更新至309在1楼)

回复 #40 newkid 的帖子