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

tree_new_bee · 发表于 2010-12-14 14:49

Q11: What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?

找二维表格中一条线上4个数的最大积。做过n皇后的问题后，这种问题不值一提。

因为给定的一堆数字没什么规律，也就没太多可优化之处，最多不过碰到0，多跳过几个数不测试，  不过因为0不太多，这节省不了太多工作量。

如果用过程语言，也许可以跳过更多的数：
保持一个目前找到的最大数
如果当前的数太小，以至于乘以三个任意的数都不会超过目前的最大数，就在4个方向上都跳过3个数字。不过总之没什么大意思。

with tstr as (select
'08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 ' ||
'49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 ' ||
'81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 ' ||
'52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 ' ||
'22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 ' ||
'24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 ' ||
'32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 ' ||
'67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 ' ||
'24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 ' ||
'21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 ' ||
'78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 ' ||
'16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 ' ||
'86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 ' ||
'19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 ' ||
'04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 ' ||
'88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 ' ||
'04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 ' ||
'20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 ' ||
'20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 ' ||
'01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 ' str from dual)
,ta as (select rownum n, str from tstr connect by rownum<=length(str)/3)
,tb as (select n, 'h' type,
substr(str,n*3-2, 2) n1,substr(str,(n+1)*3-2, 2) n2,substr(str,(n+2)*3-2, 2) n3,substr(str,(n+3)*3-2, 2) n4,
substr(str,n*3-2, 2)* substr(str,(n+1)*3-2, 2)* substr(str,(n+2)*3-2, 2)* substr(str,(n+3)*3-2, 2) prod
from ta where mod(n,20) >0 and  mod(n,20)<18
union
select n, 'v' type,
substr(str,n*3-2, 2) n1,substr(str,n*3-2+60, 2) n2,substr(str,n*3-2+120, 2) n3,substr(str,n*3-2+180, 2) n4,
substr(str,n*3-2, 2)* substr(str,n*3-2+60, 2)* substr(str,n*3-2+120, 2)* substr(str,n*3-2+180, 2) prod
from ta where n/20<17
union
select n, 'd' type,
substr(str,n*3-2, 2) n1,substr(str,(n+1)*3-2+60, 2) n2,substr(str,(n+2)*3-2+120, 2) n3,substr(str,(n+3)*3-2+180, 2) n4,
substr(str,n*3-2, 2)* substr(str,(n+1)*3-2+60, 2)* substr(str,(n+2)*3-2+120, 2)* substr(str,(n+3)*3-2+180, 2) prod
from ta where  mod(n,20) >0 and  mod(n,20)<18 and n/20<17
union
select n, 'd2' type,
substr(str,n*3-2, 2) n1,substr(str,(n+1)*3-2-60, 2) n2,substr(str,(n+2)*3-2-120, 2) n3,substr(str,(n+3)*3-2-180, 2) n4,
substr(str,n*3-2, 2)* substr(str,(n+1)*3-2-60, 2)* substr(str,(n+2)*3-2-120, 2)* substr(str,(n+3)*3-2-180, 2) prod
from ta where  mod(n,20) >0 and  mod(n,20)<18 and n/20>2
)
--select * from tb order by type,n
select max(prod) from tb

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:19 编辑 ]

tree_new_bee · 发表于 2010-12-14 15:06

Q12:What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3

+ 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

   1: 1
   3: 1,3
   6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

这个题有点意思，值得花大篇幅讨论一下。

先来个最普通的SQL:

with targ as (select 5000 arg from dual)
,t1 as (select rownum*(rownum+1)/2 n, rownum m from targ connect by rownum<=arg)
,t2 as (select rownum d from targ connect by rownum*rownum<=arg*(arg+1)/2)
,t3 as (select m,n,count(*)*2 cnt from  t1, t2 where n>d*d and mod(n, d) = 0  group by m,n )
select m,n,cnt+decode(sqrt(n)-floor(sqrt(n)),0,1,0) from t3 outer where cnt> (select max(cnt) from t3 where n<outer.n )

参数无法预先知道，只能逐步策。
参数5000以内，就要29秒。5000以内的最大数是：2162160，因子数是320
每5000递增测试，需要策到15000。 15000 的话，要253秒。
最终结果出现在第12375个数： 76576500，因子数是576

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:19 编辑 ]

tree_new_bee · 发表于 2010-12-14 15:15

用递归with语句，并不比普通SQL好，时间更长，要400多秒！

with targ as (select 15000 arg from dual)
,t as (select rownum n from targ connect by rownum*rownum<arg*(arg+1))
,tri (r, t, f) as(
select 1, 1, 1 from dual
union all
select
r+1,
t+r+1,
(select count(*) from t where n<sqrt(t+r+1) and mod(t+r+1,n)=0)
from tri,targ where f<250 and r<arg
)
select * from tri,targ where f = (select max(f) from tri) or r = arg

tree_new_bee · 发表于 2010-12-14 15:20

看来对这种大量的循环，还得靠过程语言。毕竟SQL语句中对循环的控制不可能那么精细。

declare
i number;tri number;
factors number;
begin
  i:= 2;  tri:=3;
  while 1=1 loop
      factors:=2;
      for j in 2.. sqrt(tri) loop
         if mod(tri,j) = 0 then factors:=factors+2; end if;
      end loop;
      if sqrt(tri) = floor(sqrt(tri)) then factors := factors+1; end if;
      if factors> 500 then
         dbms_output.put_line('number '|| tri || ' has factors: '|| factors);
         exit;
      end if;
      i:= i+1; tri := tri + i;
  end loop;
end;

这个需要41秒。

tree_new_bee · 发表于 2010-12-14 21:13

做完以后看问题的pdf, 关于数的因数有以下公式：

D(N) 为N的因数个数。
设N分解成质因数为：p1^a1 * p2^a2 *... pn^an
则： D(N) = (a1+1)*(a2+1) + ... (an+1)
如： 28的质因数为 2个2，1个7 即 2^2*7
则D(28) = (2+1)*(1+1) = 6

按此思路，可以优化如下：

declare
i number; j number;
tri number; tmptri number;
k number;
factors number;
cnt number;
prod number;
begin
  i:= 2;  tri:=3;
  while 1=1 loop
      factors:=2;

      cnt := 1;
      prod := 1;
      tmptri := tri;
      j := 2;
      while j<=tmptri loop
         while mod(tmptri,j) = 0 loop
            tmptri := tmptri/j;
            cnt:=cnt+1;
         end loop;
         prod := prod * cnt;
         cnt:=1;
         j:=j+1;
      end loop;

      if prod> 500 then
         dbms_output.put_line('No: ' || i || ' number '|| tri || ' has factors: '|| prod);
         exit;
      end if;
      i:= i+1; tri := tri + i;
  end loop;
end;

优化后只要29秒。

改善不很明显，是因为Oracle的mod操作太慢，通过profiler可以看到，几乎所有时间都消耗在mod操作上了。
换成别的语言，比如java, 性能会提升不少。

ludal · 发表于 2010-12-14 23:07

哇~~看得我脑袋好涨~~~
神马浮云··

质数OO写的我看过，高人

newkid · 发表于 2010-12-14 23:33

这个三角数问题我们也讨论过，没找到什么特别好的方法。如果是前面的分解结果能被后面使用就好了。

tree_new_bee · 发表于 2010-12-14 23:51

原帖由 newkid 于 2010-12-14 23:33 发表
这个三角数问题我们也讨论过，没找到什么特别好的方法。如果是前面的分解结果能被后面使用就好了。

恩。
我有个思路，但不彻底， newkid可以帮我考虑考虑:

先不考虑三角数，只考虑按顺序会创因数数目新高的数字。
根据上面的D(N) =(a1+1)*(a2+1)*..*(an+1) 的公式，
也许能手工或快速的得到最先突破500因数的数字。

在这个数字之上去搜寻那些是三角数，应该就很快了。

可以归结为这样一个纯数学问题：
如何在让2^a1 * 3^a2 *5^a3... pn^an 最小的情况下，
让 (a1+1)*(a2+1) + ... (an+1) 最大化。

解决这种问题，已经超出我的数学知识范围了。

为了纯粹通过感觉去归纳一下，列出这些创新高的数字，和他们的前半部分的因数
4 3             1,2
6 4             1,2
12 6             1,2,3
24 8             1,2,3,4
36 9             1,2,3,4,6
48 10          1,2,3,4,6
60 12          1,2,3,4,6,5
120 16          1,2,3,4,6,5,8,10
180 18          1,2,3,4,6,5,8,10,9
240 20          1,2,3,4,6,5,8,10,12,20
360 24
720 30
840 32
1260 36
1680 40
2520 48

我琢磨了好久，也没琢磨出来每次增加的因子是按什么规律来的。
原则肯定是让 (a1+1)*(a2+1)*..*(an+1)最大化，但怎么做这个最大化，没头绪。

[ 本帖最后由 tree_new_bee 于 2010-12-15 00:00 编辑 ]

newkid · 发表于 2010-12-15 00:14

我也想过从质数表中取因子组合，但超过500的a1...an的组合也不计其数，n是不固定的。判断三角数倒是很快。

tree_new_bee · 发表于 2010-12-15 01:18

原帖由 newkid 于 2010-12-15 00:14 发表
我也想过从质数表中取因子组合，但超过500的a1...an的组合也不计其数，n是不固定的。判断三角数倒是很快。

通过Excel, 我现在可以部分做到人肉搜寻了：

建立表格如下
p an (an+1) p^an
2 1 2 2
3 1 2 3
5 1 2 5
7 1 2 7
11 1 2 11
13 1 2 13
17 1 2 17
19 1 2 19
23 1 2 23
27 0 1 1
D(N): 512 N: 223092870

其中DN和N后面的两列分别是上面的列的连乘。
step1: 先从上至下为每个an赋值1(这样能让D(N)增加的最快)，一直加到23， D(N)超过了500，那么23以后的质数肯定不再需要。
step2: 观察右下角的N。通过减少一个最下面的an为0，然后为最上面的an加适当的值使得D(N)仍然在500-550之间，如果调整后N的值减小，则调整有效，否则调整取消。

调整后的结果为：
p an (an+1) p^an
2 7 8 128
3 3 4 27
5 1 2 5
7 1 2 7
11 1 2 11
13 1 2 13
17 0 1 1
19 0 1 1
23 0 1 1
27 0 1 1
D(N): 512 N: 17297280

手工调整，也可以用excel的规划求解来做，设定条件d(N) in 500-550, an可变，让N最小，规划求解的结果：

p an (an+1) p^an
2 6.996451456 7.996451456 127.6855499
3 2.994375695 3.994375695 26.83368322
5 0.991760549 1.991760549 4.934133264
7 0.990037991 1.990037991 6.865610575
11 0.987724068 1.987724068 10.68091896
13 0.986868841 1.986868841 12.5694416
17 0 1 1
19 0 1 1
23 0 1 1
27 0 1 1
D(N): 500 N: 15582483.84

与手工做的求解基本一致。

这样，可以还是沿用原来的算法，但是循环只从17297280开始，对应的三角数的序号为sqrt(2k+1/4) - 1/2 = 5881
可以节省大概1/3的工作量。