Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

重写出上面的Q31后， 下面的Q77应该就容易做了。

Q77. What is the first value which can be written as the sum of primes in over five thousand different ways?

t is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

lastwinner

tree_new_bee 发表于 2012-2-8 16:18
Q76 It is possible to write five as a sum in exactly six different ways:

4 + 1

Q76似乎用抽屉原理＋排列组合就可以搞定

lastwinner

tree_new_bee 发表于 2012-2-10 23:50
重写出上面的Q31后， 下面的Q77应该就容易做了。

Q77. What is the first value which can be written a ...

Q77我猜一下，这个数不超过799

newkid

tree_new_bee 发表于 2012-2-10 23:50
重写出上面的Q31后， 下面的Q77应该就容易做了。

Q77. What is the first value which can be written a ...

对，把COINS表换成素数表就行。

tree_new_bee

newkid 发表于 2012-2-11 03:57
对，把COINS表换成素数表就行。

也不是想象的那么简单，转的时候还是费了不少脑筋。

1. create or replace procedure Q77(arg number default 100) is
   
2. type t_nlist is table of number index by pls_integer;
   
3. type t_nlistlist is table of t_nlist index by pls_integer;
   
4. 
   
5. nlist t_nlistlist;
   
6. primlist t_numlist;
   
7. coins t_numlist := new t_numlist();
   
8. sm number;
   
9. begin
   
10. 
    
11. primlist := pkg_prim2.seive_numlist(arg);
    
12. coins.extend(primlist.count+1);
    
13. coins(1) := 1;
    
14. for i in 1..primlist.count loop
    
15.   coins(i+1) := primlist(i);
    
16. end loop;
    
17. 
    
18. for i in 1..arg loop
    
19.     nlist(1)(i) := 0;
    
20.     nlist(i)(1) := 0;
    
21. end loop;
    
22.   
    
23. for i in 2..arg loop
    
24.   for j in 2..coins.count loop
    
25.       if coins(j)<i then
    
26.         nlist(i)(coins(j)) := nlist(i-coins(j))(coins(j)) + nlist(i)(coins(j-1));
    
27.       elsif coins(j)=i then
    
28.         nlist(i)(coins(j)) := nlist(i)(coins(j-1)) + 1;
    
29.       elsif coins(j)>i then
    
30.         nlist(i)(coins(j)) :=nlist(i)(coins(j-1));
    
31.       end if;
    
32.       
    
33.   end loop;
    
34. 
    
35.   for j in 2..arg loop
    
36.     if not nlist(i).exists(j) then
    
37.       nlist(i)(j) := nlist(i)(j-1);
    
38.     end if;
    
39.   end loop;
    
40.   --dbms_output.put_line('i=' || i || ', p(i)=' || nlist(i)(i));
    
41.   if nlist(i)(i) > 5000 then
    
42.      dbms_output.put_line('result=' || i || ', p(i)=' || nlist(i)(i));
    
43.      return;
    
44.   end if;
    
45. end loop;
    
46. 
    
47. dbms_output.put_line('no result! try big arg.');
    
48. end Q77;
    

复制代码

SQL> exec q77(100)

result=71, p(i)=5007

PL/SQL procedure successfully completed

Executed in 0.094 seconds

SQL>

tree_new_bee

Q78. Find the least value of n for which p(n) is divisible by one million.

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.


看上去与前两题相似， 但因为要算的数很大，有可能要用大数运算。 并且性能也许有问题。

tree_new_bee

基本照抄过来Q76的代码，试了试：

1. create or replace procedure Q78(arg number default 100) is
   
2. type t_nlist is table of number index by pls_integer;
   
3. type t_nlistlist is table of t_nlist index by pls_integer;
   
4. 
   
5. nlist t_nlistlist;
   
6. sm number;
   
7. begin
   
8. for i in 1..arg loop
   
9.     nlist(1)(i) := 1;
   
10.     nlist(i)(1) := 1;
    
11. end loop;
    
12.   
    
13. for i in 2..arg loop
    
14.   for j in 2..arg loop
    
15.       if j<i then
    
16.         nlist(i)(j) := nlist(i-j)(j) + nlist(i)(j-1);
    
17.       elsif j=i then
    
18.         nlist(i)(j) := nlist(i)(j-1) + 1;
    
19.       elsif j>i then
    
20.         nlist(i)(j) :=nlist(i)(j-1);
    
21.       end if;
    
22.   end loop;
    
23. if nlist(i)(i)mod 1e6 = 0 then
    
24.      dbms_output.put_line('result=' || i || ', p(i)=' || nlist(i)(i));
    
25.      return;
    
26.   end if;
    
27. end loop;
    
28. dbms_output.put_line('no result! try big arg.');
    
29. end Q78;
    

复制代码

参数试到2000时，出来了结果：

SQL> exec q78(2000)

result=1759, p(i)=4280750559177948266124532321685590709000000

PL/SQL procedure successfully completed

Executed in 1.232 seconds



但是， 别急。 填进去这个答案，是错的。
为什么呢？ 看看得到的 p(i)=4280750559177948266124532321685590709000000， 6个0前面的位数是38位， 正好是oracle number的精度。
所以这个数能被1000000整除是假的。

并且， 先不说大数问题(有大数包， 大数不是问题),  注意参数为2000已经要1秒多了(在100-200时，速度0.0x秒), 如果结果是上万的， 那么也许就很难出来了。

tree_new_bee

lastwinner 发表于 2012-2-11 00:18
Q77我猜一下，这个数不超过799

对了， 但超出的太多。
不知怎么猜的？

在结果没出来之前， 试着猜猜Q78的答案范围？

tree_new_bee

改成大数运算， 性能骤降许多！

1. create or replace procedure Q78(arg number default 100) is
   
2. type t_nlist is table of varchar2(1000) index by pls_integer;
   
3. type t_nlistlist is table of t_nlist index by pls_integer;
   
4. 
   
5. nlist t_nlistlist;
   
6. begin
   
7. for i in 1..arg loop
   
8.     nlist(1)(i) := '1';
   
9.     nlist(i)(1) := '1';
   
10. end loop;
    
11.   
    
12. for i in 2..arg loop
    
13.   for j in 2..arg loop
    
14.       if j<i then
    
15.         nlist(i)(j) := pkg_bignum.bigplus(nlist(i-j)(j) , nlist(i)(j-1));
    
16.       elsif j=i then
    
17.         nlist(i)(j) := pkg_bignum.bigplus(nlist(i)(j-1) , 1);
    
18.       elsif j>i then
    
19.         nlist(i)(j) :=nlist(i)(j-1);
    
20.       end if;
    
21.   end loop;
    
22. if substr(nlist(i)(i), -6) = '000000' then
    
23.      dbms_output.put_line('result=' || i || ', p(i)=' || nlist(i)(i));
    
24.      return;
    
25.   end if;
    
26. end loop;
    
27. dbms_output.put_line('no result! try big arg.');
    
28. end Q78;
    

复制代码

SQL> exec q78(1000)

no result! try big arg.

PL/SQL procedure successfully completed

Executed in 1.467 seconds

SQL> exec q78(2000)

no result! try big arg.

PL/SQL procedure successfully completed

Executed in 82.774 seconds

SQL>


2000比1000慢许多， 是因为在大数包中，对于小与1e35的数是直接用数学计算去算的，到了1000以后， 大部分的计算都真正采用字符进行大数运算， 要慢的多。

看来这个算法的路走到尽头了， 要重新寻找新的思路。

lastwinner

tree_new_bee 发表于 2012-2-11 21:48
对了， 但超出的太多。
不知怎么猜的？

10有5种不同的素数和的写法，而且对于一个偶数，最长的写法总是一串2的和
如果满足条件的数是1000，那么最长的写法就是500个2，而加数最少可以是两个质数
加数个数从2到500，变化太多了，保守算也至少有(500-2+1)/2=254种那么多……（猜的时候就想到这么多，然后一想，若为1000，太多了，减少到800也肯定能让结果超过5000，于是就猜了个799）

————————————以下是回应你的问题时写的—————————————————
如果满足条件的数是1000，那么最长的写法就是500个2，而3个2可以拆为两个3，因此2和3的组合写法，可以有大约(500-2)/3=166那么多种，不去细算，1000以内的素数至少有100个，而任意一个质数，都可以表示为一个或两个2与若干3的和（用这个方式可以保证构造出的加数组合不重复）
5=2+3，于是166种2和3的组合，可以转化为166种一个5与2和3的组合
7=2+2+3，于是166种2和3的组合，可以转化为165种一个7与2和3的组合
……
如此下去，到第100个质数的时候，只替换出一个非2和3的质数，可能的质数组合将达到10000左右，远远超出了5000
昨天如果想到这么远，那么我连799都不会猜了。本来想赌300的，不过没细算就没猜，呵呵