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

〇〇

问题8_1:

  Discover the largest product of five consecutive digits in the 1000-digit number.

  在给定的1000个1位数

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
中，求出连续15个数的最大乘积。

或者求出连续给定N个数的最大乘积

[ 本帖最后由 〇〇 于 2010-11-4 20:35 编辑 ]

lastwinner

原帖由 〇〇 于 10-11-3 13:29 发表
问题1:
Add all the natural numbers below one thousand that are multiples of 3 or 5.
求小于1000的自然数中3或5的倍数之和。
SQL> select sum(x) from (select level x from dual connect by level

3和5的最小公倍数为15
3、5、6、9、10、12、15，其和为60，个数为7
各自加上15的整数倍n，即可得下一组3和5的倍数，于是其和为
15×7×n＋60＝60＋105n

trunc(999/15)=66，mod(999/15)=9

故总和为
60*66+105*(65*(65+1)/2)+(3+5+6+9+990*4)
复制粘贴到计算器中得 233168

〇〇多算了个1000

原帖由 〇〇 于 10-11-3 14:34 发表
问题2:
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
对于数列f(n):
　　f(1) =1,f(2) =2
　　f(n) =f(n-1)+f(n-2) (n>2)
求数列f(n)中不大于4000,000且为偶数项之和。

题目解释有误，应为f(1) =1,f(2) =1

原帖由 newkid 于 10-11-3 22:21 发表
〇〇很厉害啊。第三个的4000怎么来的？能不能先把质数表求出来就不用res[1]+1了？

同质疑
那数开根可是 775146的哦

lastwinner

原帖由 〇〇 于 10-11-4 16:35 发表
问题5:What is the smallest number divisible by each of the numbers 1 to 20?

  求1,2,..,19,20的最小公倍数。

这不是很简单么……
已知了1～10的最小公倍数是5040
11、13、17、19都是质数，这些都要乘进去
5040只包含2^3，无法被16整除，所以还要再乘以2
12、14、15、18、20都是5040的因数
所以1～20的最小公倍数是

5040*11*13*17*19*2=465585120

lastwinner

原帖由 〇〇 于 10-11-4 16:52 发表
问题8:

  Discover the largest product of five consecutive digits in the 1000-digit number.

  在给定的1000个1位数

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
中，求出连续5个数的最大乘积。

其实有个字符串查找的算法可以借鉴的，不过似乎无法应用在这里

目前人肉能初步得出
因为9*9*9*9=6561<9*6*9*8*3 (第二行开头的5个数字)
所以可以推定，当连续五个数包含0或者1时，其乘积一定不是最大的
于是有下面的sql

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, 1) num from s connect by rownum<=length(x))
select max(dbms_aw.eval_number(ep)) max_product, max(rnstart) keep (dense_rank first order by dbms_aw.eval_number(ep) desc) rnstart,
   substr(max(ep) keep (dense_rank first order by dbms_aw.eval_number(ep) desc),3) expression from (
select rn-4 rnstart, '1'||sys_connect_by_path(num,'*') ep from sp where level=5 start with rn<=996 and num not in(0,1) connect by level<=5 and rn=prior rn+1 and num not in (0,1))

得到结果为

MAX_PRODUCT    RNSTART              EXPRESSION     
-----------              ----------             --------------------------------------------------------------------------------
      40824             365                      9*9*8*7*9

[ 本帖最后由 lastwinner 于 2010-11-5 01:32 编辑 ]

newkid

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


这不是很简单么……
已知了1～10的最小公倍数是5040
11、13、17、19都是质数，这些都要乘进去
5040只包含2^3，无法被16整除，所以还要再乘以2
12、14、15、18、20都是5040的因数
所以1～20的最小公倍数是

5040*11*13*17*19*2=465585120

你干脆说已知1～20的最小公倍数是xxx不就得了？
把所有质因子分解出来求并集。

newkid

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



其实有个字符串查找的算法可以借鉴的，不过似乎无法应用在这里

目前人肉能初步得出
因为9*9*9*9=6561

不许人肉，将来所有题目都用绑定变量给数据。

lastwinner

原帖由 〇〇 于 10-11-3 15:52 发表
问题4:
Find the largest palindrome made from the product of two 3-digit numbers.
求能分解为两个三位数乘积的最大回文数。

SQL> select max(a.x) from (select b.x*c.x x from
  2  (select level+100 x from dual connect by level <900)b,(select level+100 x from dual connect by level <900)c
  3  )a where a.x>100000 and substr(a.x,1,3)=substr(a.x,6,1)||substr(a.x,5,1)||substr(a.x,4,1);

  MAX(A.X)
----------
    906609

最后部分可以用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 <900)b,(select level+100 x from dual connect by level <900)c
   where b.x>=c.x and substr(b.x, -1) in(1,2,3,4,7,8,9) and substr(c.x, -1) in (1,2,3,4,7,8,9)     --从2.03s降低到
   and (substr(b.x, -1), substr(c.x, -1)) in ((1,7),(1,8),(1,9),(2,4),(3,3),(7,1),(8,1),(9,1),(4,2))     --1.43s
   )a where a.x>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 <300)b,(select level+700 x from dual connect by level <300)c --直接降低到0.25s
   where b.x>=c.x and substr(b.x, -1) in(1,2,3,4,7,8,9) and substr(c.x, -1) in (1,2,3,4,7,8,9)
   and (substr(b.x, -1), substr(c.x, -1)) in ((1,7),(1,8),(1,9),(2,4),(3,3),(7,1),(8,1),(9,1),(4,2))
   )a where a.x>100000 and substr(a.x,1,3)=reverse(substr(a.x,4));

lastwinner

原帖由 newkid 于 10-11-5 01:21 发表

你干脆说已知1～20的最小公倍数是xxx不就得了？
把所有质因子分解出来求并集。

是我用词不当，哈哈
因为从小就知道1～10的最小公倍数是多少了
不过刚才是说错了
1～10的最小公倍数是 2520，不是5040

最后1～20的最小公倍数应该是
2520*11*13*17*19*2=232792560

lastwinner

原帖由 newkid 于 10-11-5 01:23 发表

不许人肉，将来所有题目都用绑定变量给数据。

那可以依据任何数与0的乘积都是0来简化么？

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, 1) num from s connect by rownum<=length(x))
select max(dbms_aw.eval_number(ep)) max_product, max(rnstart) keep (dense_rank first order by dbms_aw.eval_number(ep) desc) rnstart,
   substr(max(ep) keep (dense_rank first order by dbms_aw.eval_number(ep) desc),3) expression from (
select rn-4 rnstart, '1'||sys_connect_by_path(num,'*') ep from sp where level=5 start with rn<=996 and num >0 connect by level<=5 and rn=prior rn+1 and num>0)

lastwinner

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, 5) num from s connect by rownum<=length(x)-4)
select max(rn) keep (dense_rank first order by p desc ) rnstart,
max(p) mp from( select rn, substr(num,1,1)*substr(num,2,1)*substr(num,3,1)*substr(num,4,1)*substr(num,5,1) p from  sp
where instr(num, '0')=0)

还是这样快，94ms
用connect by灵活是灵活点，但是太慢了