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

lastwinner · 发表于 2012-2-11 22:33

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

78我感觉可以用数学归纳法做出来
如果不行的话可以用我在200楼写的分析思路去试探
不过这个题是算能被100万整除的数字，所以不太好猜，但我建议你在计算次数的时候，超过100万就减去100万，由此避免精度的问题

lastwinner · 发表于 2012-2-11 23:11

tree_new_bee 发表于 2012-2-11 21:40
Q78. Find the least value of n for which p(n) is divisible by one million.

Let p(n) represent the ...

p(1)=1＝1
p(2)=2=1+1
p(3)=3=1+1+1
p(4)=5=1+1+2+1
p(5)=7=1+1+2+2+1
p(6)=10=1+1+2+3+2+1
p(7)=15=1+1+2+3+4+3+1
p(8)=23=1+1+2+3+5+5+6+1

拿p(4)来说，组合显然是{4},{3,1},{2,2},{2,1,1},{1,1,1,1}，总共5组
我们将这个过程做如下约定：先分离出的数总是不小于后续分离出的数，这样就可以保证分离出来的这个组合不会与其他组合重复。
p(5)在例子中已经有说明，比较好理解，那我们来看一下p(7)是怎么得出的
不超过7的正整数显然有7个，我用p(n,m)（m<=n）表示若第一个分离出来的数是m，则这样的组合共有多少
那么p(7)=p(7,7)+p(7,6)+...+p(7,1)
p(7,7)和p(7,6)显然都只可能是1,p(7,1)也只可能是1，并且p(n,1)肯定是1
p(7,5)=p(2)=2
p(7,4)=p(3)=3
p(7,3)=p(4,3)+p(4,2)+p(4,1)=p(1)+p(2)+p(1)=1+2+1=4
p(7,2)=p(5,2)+p(5,1)=p(3,2)+p(3,1)+p(5,1)=1+1+1=3

到此，规律已经找到，剩下的就是不断按此规律计算p(n)，看其是否满足被100万整除。
如果你还没理解，那么你可以试着验证一下p(16)。按我找出的规律：
p(16,8)=p(8)=23，只要前面没算错，那这里这个数一定是正确的
——————————————————————————————
这个题没法猜。我一开始的设想是数字每增加1，就将1套用到前一个n的各种变化上，看能增加出多少变化，不过这个规律没法抓取，因此就没有叙述

tree_new_bee · 发表于 2012-2-11 23:33

lastwinner 发表于 2012-2-11 22:28
10有5种不同的素数和的写法，而且对于一个偶数，最长的写法总是一串2的和
如果满足条件的数是1000，那么 ...

这个思路很不错。
不过，好像你算的时候还漏了一些情况，所以造成你估的数高了许多。

7=2+2+3，于是166种2和3的组合，可以转化为165种一个7与2和3的组合

这里，除了组出7与2和3的组合外，除组成7以外的其它2和3还可以组成5.

数小的时候，这个占的比例不高，但数大的时候，这些数的比重就非常高了。

lastwinner · 发表于 2012-2-12 00:17

tree_new_bee 发表于 2012-2-11 23:33
这个思路很不错。
不过，好像你算的时候还漏了一些情况，所以造成你估的数高了许多。

当时就是拍脑袋拍出来的，真按我后来写的去估，那怎么也会控制在300以内的

后面你指出的和我说的并不矛盾，因为我只是将2和3组成的组合中，去掉若干2和3，换成一个别的质数
也就是说，仅有一个不是2和3的质数，而7和5，就是两个不是2和3的质数了，呵呵

tree_new_bee · 发表于 2012-2-12 14:11

本帖最后由 tree_new_bee 于 2012-2-12 14:12 编辑

lastwinner 发表于 2012-2-11 22:33
78我感觉可以用数学归纳法做出来
如果不行的话可以用我在200楼写的分析思路去试探
不过这个题是算能被1 ...

但我建议你在计算次数的时候，超过100万就减去100万，由此避免精度的问题

这是个好办法，既避免了精度问题，又回避了大数运算。

至于202#的算法，很容易理解。但我感觉到从运算复杂度来说，似乎不比我原来的算法复杂度更低。除了与我一样要保存一个(n,n)的二维数组外，还要涉及到一个从1到n的累加。

我搜了一下网上的相关文章，看到结果应该是5万多。对于上面的算法来说， 5万*5万的数组，不可想象。

lastwinner · 发表于 2012-2-12 16:28

tree_new_bee 发表于 2012-2-12 14:11
这是个好办法，既避免了精度问题，又回避了大数运算。

至于202#的算法，很容易理解。但我感觉到从 ...

p(n,m)最终都可以转换为若干p(o)的和，o为不超过m的正整数
关键是在于这个转换过程的自动处理，我隐隐有感觉是有规律的，但我目前没空去找出这个规律。
我相信当m<=n/2时，应该存在一个公式去表达p(n,m)的值，或者有一个更简便的递归算法去表示p(n,m)的值

tree_new_bee · 发表于 2012-2-12 16:39

没办法，还是要动用google。

其实之前做Q76就搜到wiki上关于partition的一些文章，不过觉得没到动用这些核武器的地步。
现在只好用了。

http://zh.wikipedia.org/wiki/%E4 ... 8%E5%AE%9A%E7%90%86

简单说，就是：
P(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) .....
其中的1,2,5,7,12...是广义五角数，其公式为：
(3nn - n )/2, 其中n取值为 1,-1,2,-2,....

用p(7)做例子，就是： p(7) = p(7-1) + p(7-2) - p(7-5) - p(7-7) = p(6) + p(5) -p(2) - p(0)

用这个方法，只要一维数组就可以了，尽管在循环内部还要有一次循环，但内部循环的复杂度低于O(n)

create or replace procedure Q78D(arg number default 100) is
type tnlist is table of number index by pls_integer;
nlist tnlist;
k integer;
p integer;
n integer;
sg integer;
s number;
begin
nlist(0) := 1;
nlist(1) := 1;
for i in 2..arg loop
k:=0;
p:=0;
s := 0;
while p<i loop
k:=k+1; -- k = 1,2,3,4....
if bitand(k,1) = 0 then -- n = 1,-1, 2, -2 ,.....
n:=-(k/2);
else
n:= (k+1)/2;
end if;
p := (3*n*n - n)/2; --- p = 1,2,5,7,12,15,.......
if p>i then exit;
end if;
--dbms_output.put_line('i=' || i || ' ,k=' ||k || ' ,n=' ||n ||' ,p=' ||p);
if bitand(k,3) in (0,3) then -- 每两项改变一次符号
sg := -1;
else
sg := 1;
end if;
s := s + sg*nlist(i-p);
end loop;
s := mod(s, 1e6);
if s<0 then
s := s + 1e6; --保证s为正的余数
end if;
--dbms_output.put_line('nlist('||i||')=' || nlist(i));
if s = 0 then
dbms_output.put_line('nlist('||i||')=' || s);
return;
end if;
nlist(i) := s;
end loop;
dbms_output.put_line('no result, try big args.' );
end Q78D;

复制代码

这个代码测试上万的参数很轻松。

SQL> exec q78d(20000)

no result, try big args.

PL/SQL procedure successfully completed

Executed in 4.275 seconds

SQL> exec q78d(60000)

nlist(55374)=0

PL/SQL procedure successfully completed

Executed in 20.312 seconds

SQL>

通过观察代码运行的profiler, 可以看到内部循环大概是外部循环的开方次数，所以复杂度大概为O(n*sqrt(n))

tree_new_bee · 发表于 2012-2-12 16:45

因为舍去了超过1e6的数，所以没办法得到最终的划分数，去euler问题论坛中看到，这个数字是个257位的数字！

tree_new_bee · 发表于 2012-2-12 17:38

另开新帖了， http://www.itpub.net/thread-1573075-1-1.html

lastwinner · 发表于 2012-2-13 00:56

tree_new_bee 发表于 2012-2-12 16:39
没办法，还是要动用google。

其实之前做Q76就搜到wiki上关于partition的一些文章，不过觉得没到动用这些 ...

p(8)是22啊，我上面写得不对，按我后面给的数，应该算出来24才是，不过我的p(8,2)算错了，应该是4

你强啊，是怎么找到五边形数定理的？

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

浏览过的版块