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

newkid

原帖由 zhangweicai74 于 2011-1-14 09:19 发表
最近没见奥数哥光临了。

他说对哥德巴赫猜想有了新思路，在研究呢！（不是瞎说的）

tree_new_bee

原帖由 newkid 于 2011-1-14 10:30 发表

他说对哥德巴赫猜想有了新思路，在研究呢！（不是瞎说的）

民间科学家总是对哥德巴赫猜想和永动机趋之若鹜。

newkid

原帖由 tree_new_bee 于 2011-1-14 10:55 发表


民间科学家总是对哥德巴赫猜想和永动机趋之若鹜。

哈哈，“和尚动得，我动不得？”(阿Q)

我感觉奥数哥应该是官方数学家，祝福他成功！

tree_new_bee

这段时间很忙， 先歇歇回头再继续。

tree_new_bee

tree_new_bee 发表于 2011-1-25 11:47
这段时间很忙， 先歇歇回头再继续。

说歇了歇，一下子就歇了一年。


准备再继续。

tree_new_bee

tree_new_bee 发表于 2011-1-13 22:20
题目看起来很简单， 要是小一点的上界， 怎么都好做。
但1500000实在是个恐怖的数字。

题目看起来很简单， 要是小一点的上界， 怎么都好做。
但1500000实在是个恐怖的数字。

用wiki里这个公式：
    a = m2 − n2,
    b = 2mn,
    c = m2 + n2

其中m,n互质， 可以产生素勾股数
要产生所有勾股数， 只要在上面的基础上乘上自然数k就行。
问题是， 前一步的素勾股数可以很快产生， 所有的素勾股数*k,这一步也很慢。

这里引用错误。  m,n除了互质外，还要保证两个奇偶不同。

按照这个思路，用SQL来写：

1. with targ as (select 150000 arg from dual)
   
2. ,tmn as (select level d from targ connect by level<=sqrt(arg/2))
   
3. , tp as (select tm.d m, tn.d n, least((tm.d*tm.d - tn.d*tn.d),(2*tm.d*tn.d)) a, greatest((tm.d*tm.d - tn.d*tn.d),(2*tm.d*tn.d)) b, (tm.d*tm.d + tn.d*tn.d) c
   
4. ,(tm.d*tm.d *2  + 2*tm.d*tn.d )  p
   
5. from tmn tm, tmn tn, targ
   
6. where tm.d>tn.d
   
7. and (tm.d*tm.d *2  + 2*tm.d*tn.d ) <arg
   
8. and pkg_prim2.gcd(tm.d, tn.d) = 1
   
9. and mod(tm.d+tn.d,2) = 1
   
10. )
    
11. , tmul as (select   a*k a, b*k b, c*k c, p*k p
    
12. from tp, targ ,(select level k from targ connect by level<=arg/12) tk
    
13. where k <= arg/p)
    
14. ,tgroup as (select p, count(*) from tmul group by p having count(*) = 1)
    
15. select count(*) from tgroup
    
16.   
    
17. COUNT(*)
    
18. ----------
    
19.      16414
    

复制代码

只是算到150000，就已经要100多秒了。 受不了。

tree_new_bee

改成pl/sql 来写：

1. create or replace procedure p75C is
   
2.   arg    number := 1500000;
   
3.   type tnumlist is table of number index by BINARY_INTEGER;
   
4.   numlist tnumlist;
   
5. 
   
6.   a   number;
   
7.   b   number;
   
8.   c   number;
   
9.   p   number;
   
10.   p2  number;
    
11.   r  number;
    
12.   cnt number;
    
13. begin
    
14.   for m in 2 .. sqrt(arg / 2) loop
    
15.     for n in 1 .. m - 1 loop
    
16.       if mod(m + n, 2) = 1 and pkg_prim2.gcd(m, n) = 1 then
    
17.         a :=least(m*m - n*n, 2*m*n);
    
18.         b := greatest(m*m - n*n, 2*m*n);
    
19.         c := m * m + n * n;
    
20.         p := a + b + c;
    
21.         if p > arg then
    
22.           exit;
    
23.         end if;
    
24.       
    
25.         for k in 1 .. floor(arg / p) loop
    
26.           p2 := p * k;
    
27.         
    
28.           if numlist.exists(p2) then
    
29.             numlist(p2) := numlist(p2)+1;
    
30.           else
    
31.             numlist(p2) := 1;
    
32.           end if;
    
33.         
    
34.         end loop;
    
35.       
    
36.       end if;
    
37.     end loop;
    
38.   
    
39.   end loop;
    
40. 
    
41.   cnt := 0;
    
42.   r     := numlist.first;
    
43.   while r is not null loop
    
44.     if numlist.exists(r) and numlist(r) = 1 then
    
45.       cnt := cnt + 1;
    
46.     end if;
    
47.     r := numlist.next(r);
    
48.   end loop;
    
49. 
    
50.   dbms_output.put_line('cnt:' || cnt);
    
51. end p75C;

复制代码

这个就快多了。

SQL> exec p75c;

cnt:161667

PL/SQL procedure successfully completed

Executed in 1.482 seconds

tree_new_bee

Q76 How many different ways can one hundred be written as a sum of at least two positive integers?

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

把100拆成两个以上的正整数的和，有多少种拆法？

tree_new_bee

先搞搞思路：

比如先知道3的拆法有： 1+1+1, 2+1两种
那么4的拆法有：
* 3的拆法后面分别加上一个+1， 得到1+1+1+1, 2+1+1
*3的首位加1， 得到 2+1+1, 3+1
* 3的拆法后面不同的数字加1，  得到 2+2 （如果觉得判断不同数字麻烦，也可以对每个数字都加1，  得到 1+2+1, 1+1+2,  2+2）
把上面的结果加到一起去除重复。

〇〇

tree_new_bee 发表于 2012-2-8 16:23
先搞搞思路：

比如先知道3的拆法有： 1+1+1, 2+1两种

移步过来解36X吧。。http://www.itpub.net/thread-1563734-4-3.html