[Project Euler前50题总结]交稿！！（8.14）

jimogsh · 发表于 2010-1-27 10:06:12

本帖最后由 jimogsh 于 2010-8-14 21:41 编辑

RT，我想利用这段时间总结性地写一下本版对欧拉计划讨论的结果，把其中简单易于理解的代码集中起来，一是我自己再学习一遍，总结出来也方便以后给新手学习。
下面的附件是刚开始写了的三道题目，主要请大家看看这个stylesheet如何改进一下？我还不太会用M@写文档，自己设计了个简单的模板，但并不算好。
如果各位谁有这方面的经验或者教材还请不吝赐教。

附件为PDF格式，效果与M@的NB文件效果有些区别。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

前十题基本写完了，原文件附上，主要目的还是希望大家能指教一下模板的制作、设置步骤。
当然代码、表述方面如果有误或者能做更好的改进也欢迎指出。
在选择代码方面，我除了自己想出来的代码外，基本都是选自本论坛的代码，尽量选取简明易懂的方法。

——————————————————————————————————
更新至前20题，其中第11题我还没弄明白引用的代码。
有更简洁、易懂的解法欢迎大家指出。

------------------------------4.4更新--------------------------------
附件更新到前30题。
对于1~20题主要在参看大家反馈的基础上进行了小幅修改，可略去不看。
21~30题是新增加的内容。其中22题答案貌似在PE网站没有通过，也许哪里有错误，还没发现。27题我还不会做……希望继续得到大家的指点。
谢谢。
--------------------------4.23--------------------------------------
更新到40题。
仍然有未完成的题目，在标题前标了***符号，以容易分辨。
代码为综合本版的讨论和PE网站论坛上找到的部分代码。有少部分我还没有仔细理会，只帖了上去。会在未来继续完善。
现在的想法是先把50道题写完，然后把代码进一步优化以及文字表述上的改进。
感谢大家支持。
--------------现在流行分隔线-------------------
就这样交稿吗？……也许就这样了吧，因为以后要忙的事情太多了，我似乎没有更多的时间来关注这个小文章的继续写作了，而实际上我写这个东东已经用了超过半年的时间。而且现在传上来的也应该叫个“初稿”，因为还有很多BUG存在，还有几道题没有解决或者没有找到比较好的方法。具体地说，没有解决的题目有：第27、32、42、43、50等，没有找到比较好的解法的有：17、23题，另外22题FM给出的方法解出的答案在PE网站上似乎没有通过，原因我还不清楚。
改进之处：

完成了最后十题（除去不会做的……）
删掉了前面部分的大量废话

好吧，就是如此吧。我由于要复习考研，一定时间里不敢保证继续修改这篇文章直到它多么完美，如果哪位网友有兴趣欢迎继续改进这篇小文档。
感谢大家的支持。最新全文附上。

liweicai990 · 发表于 2010-1-27 12:52:03

支持ＬＺ　

方便我这新手学习。

FreddyMusic · 发表于 2010-1-31 11:35:21

Mathematica stylesheet is very easy for master.

Select a Wolfram Research defined stylesheet and use Alt +1 ~9 to set up different cell.

Meanwhile see my format it is a relative good format.

http://bbs.simwe.com/thread-863985-1-1.html

It's good to restart Euler Project in a serious attitude.

jimogsh · 发表于 2010-1-31 14:37:49

本帖最后由 jimogsh 于 2010-1-31 14:50 编辑

4# FreddyMusic 这个我还是明白的，不过对于系统内置的那些Style有些是可以运行的（如Input,Code)，有些是不能运行的(如Text)，还有不同的style之间的从属关系等，这些属性是怎么设置的？那个StyleSheet Inspector里面的功能太少了。

这些对于我要写的这篇小文章自然是不必要懂的，不过我想通过这次了解一下这方面的内容。

FreddyMusic · 发表于 2010-1-31 17:43:49

Try
Alt +1
Alt +2
.....
Alt +9
As I have said.

TBE_Legend · 发表于 2010-1-31 19:15:18

Try
Alt +1
Alt +2
.....
Alt +9
As I said.
FreddyMusic 发表于 2010-1-31 17:43

ggggwhw · 发表于 2010-2-1 12:09:49

本帖最后由 ggggwhw 于 2010-2-1 12:17 编辑

下面是jimogsh 认为很简单的问题,但是很不幸:结果正确,方法却是有问题的.:

No 3:Find the largest prime factor of a composite number.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
对600851475143分解质因数，求出最大因子。
这个对于Mathematica来说根本不是什么问题
FactorInteger[600851475143] // Max
6857

复制代码

下面是我用8来验证的过程:

In[63]:= FactorInteger[8]
FactorInteger[8] // Max
Out[63]= {{2, 3}}
Out[64]= 3

复制代码

很明显上面的结果是错误的,所以不要认为一种方法对于某一具体情况可能算出了正确的结果就认为该方法是正确的.
虽然我下面给的方法不一定是最简单的写法,但是它是一种正确的写法:

In[66]:= Cases[FactorInteger[600851475143], {p_, _} -> p] // Max
Out[66]= 6857

复制代码

In[67]:= Cases[FactorInteger[8], {p_, _} -> p] // Max
Out[67]= 2

复制代码

ggggwhw · 发表于 2010-2-1 14:06:13

001.计算小于1000的自然数中,3或5的倍数之和.
如果我们列举出所有小于10的的自然数中3或5的倍数,我们可以得到3,5,6,9.它们之和是23.
计算小于1000的自然数中,3或5的倍数之和.
a = 3;
b = 5;
n = 1000;
sum = 0;
c = a*b;
For[i = a, i < n, i += a, sum += i];
For[i = b, i < n, i += b, sum += i];
For[i = c, i < n, i += c, sum -= i];
sum
Out[94]= 233168
In[85]:= Total@Union[Range[3, 999, 3], Range[5, 999, 5]]
Out[85]= 233168
\[FilledLeftTriangle]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]|\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[FilledRightTriangle]
002.计算斐波那契数列中不超过4000000的所有偶数之和.
斐波拉契数列的前10项为:1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
斐波拉契数列第n项的内置函数为 Fibonacci[n] .
计算斐波那契数列中不超过4 000 000的所有偶数之和.
In[271]:= n = 4000000;
a = 1;
b = 2;
sum = 0;
For[a = 1; b = 2, b < n, b += c,
If[EvenQ[b], sum += b];
c = a;
a = b;
]
sum
Out[276]= 4613732
In[45]:= max = Floor@n /. FindRoot[Fibonacci[n] == 4000000, {n, 1}];
Sum[Fibonacci[i], {i, 3, max, 3}]
Out[46]= 4613732
\[FilledLeftTriangle]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]|\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[FilledRightTriangle]
003.对600851475143分解质因数,求出最大因子.
156的质因数有2, 3, 13.
获取方法: Cases[FactorInteger[156], {p_, q_} -> p] .
对600851475143分解质因数,求出最大因子.
n = 600851475143;
a = Floor[Sqrt[n]];
b = n;
For[i = 2, i <= a, i++,
If[Divisible[n, i],
b = i;
n = n/i;
a = Floor[Sqrt[n]];
i = i - 1;
]
]
n
Out[374]= 6857
In[283]:= Cases[FactorInteger[600851475143], {p_, _} -> p] // Last
Out[283]= 6857
\[FilledLeftTriangle]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]|\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[ThickSpace]\[FilledRightTriangle]

复制代码

我觉得像这种写法更合适一些:

其中前一种解法是通过自己对数学知识的理解和掌握,训练脑力解决问题的方法.运用最基本的循环和判断函数来完成较困难的题目,又容易将该程序直接改造成其它语言来实现,相对来说对计算机的配置要求不是很高,但是在Mathematica 下运行的速度可能会慢一些.但是还是能出结果的.

后一种解法是充分利用Mathematica 的内置函数,再考虑算法的效率来解决问题.

当然我的写法中存在的一些问题也很明显,就是对于变量的定义很随意,毕竟Mathematica 只是我的爱好,我并不想用它来开发什么.只是为了锻炼一下自己的数学能力而已,所以我更喜欢前一种解法.

ggggwhw · 发表于 2010-2-1 14:10:31

发现原文复制上来后改变了只好上传原文件了.

jimogsh · 发表于 2010-2-1 16:34:40

本帖最后由 jimogsh 于 2010-2-1 16:46 编辑

8# ggggwhw
这个代码我后来已经修改过了，这个上传的文件主要是请大家看一下样式的，所以就没有及时在这里也作修改。

FactorInteger[600851475143] /. {x_, y_} -> x // Max

复制代码

jimogsh · 发表于 2010-2-4 16:44:48

前十题写完了，顶楼的附件已经更新，欢迎大家提出意见和建议。

ggggwhw · 发表于 2010-2-4 18:30:02

№1.貌似Fred给出的才是最简单的
我将代码稍微改动了一下,以适应不同初值情况.

In[217]:= qujian = {1, 999};
a = 3;
b = 5;
arr = {a, LCM[a, b], b}
Sum[
min = qujian[[1]] - Mod[qujian[[1]] - 1, arr[[i]]] - 1 + arr[[i]];
max = qujian[[2]] - Mod[qujian[[2]] - 1, arr[[i]]] - 1 + arr[[i]];
(-1)^(i + 1) (min + max) ((max - min)/arr[[i]] + 1)/2,
{i, 1, 3}]
Out[220]= {3, 15, 5}
Out[221]= 233163

复制代码

你将区间改到{1,9999999999}就会看到这种做法的优越性了,消耗的内存小.你给的两种代码是无法完成的.

ggggwhw · 发表于 2010-2-4 18:55:32

№2.
貌似我的方法是最好的方法,下面是三种方法的比较:

In[473]:= n = 4*10^4;
Print["waynebuaa的代码虽然健壮,但是结果有时会出错,比如:"]
Timing@Total@Fibonacci[Range[3, Round@Log[GoldenRatio, n Sqrt[5.]], 3]]
Print["网友changqing的代码效率有时会高,但是随着n大到4*10^8,就算不出结果了："]
Timing@Sum[
Fibonacci[i], {i, 3, Floor@j /. FindRoot[Fibonacci[j] == n, {j, 1}],
3}]
Print["我的代码,虽然只是For循环这样的初级代码,但是速度绝不逊色,结果也不出错,值得推荐"]
Timing[a = 1;
b = 2;
sum = 0;
For[a = 1; b = 2, b < n, b += c,
If[EvenQ[b], sum += b];
c = a;
a = b;
];
sum
]
During evaluation of In[473]:= waynebuaa的代码虽然健壮,但是结果有时会出错,比如:
Out[475]= {0., 60696}
During evaluation of In[473]:= 网友changqing的代码效率有时会高,但是随着n大到4*10^8,就算不出结果了：
Out[477]= {0., 14328}
During evaluation of In[473]:= 我的代码,虽然只是For循环这样的初级代码,但是速度绝不逊色,结果也不出错,值得推荐
Out[479]= {0., 14328}

复制代码

In[480]:= n = 4*10^8;
Print["waynebuaa的代码虽然健壮,但是结果有时会出错,比如:"]
Timing@Total@Fibonacci[Range[3, Round@Log[GoldenRatio, n Sqrt[5.]], 3]]
Print["网友changqing的代码效率有时会高,但是随着n大到4*10^8,就算不出结果了："]
Timing@Sum[
Fibonacci[i], {i, 3, Floor@j /. FindRoot[Fibonacci[j] == n, {j, 1}],
3}]
Print["我的代码,虽然只是For循环这样的初级代码,但是速度绝不逊色,结果也不出错,值得推荐"]
Timing[a = 1;
b = 2;
sum = 0;
For[a = 1; b = 2, b < n, b += c,
If[EvenQ[b], sum += b];
c = a;
a = b;
];
sum
]
During evaluation of In[480]:= waynebuaa的代码虽然健壮,但是结果有时会出错,比如:
Out[482]= {0., 350704366}
During evaluation of In[480]:= 网友changqing的代码效率有时会高,但是随着n大到4*10^8,就算不出结果了：
During evaluation of In[480]:= FindRoot::lstol: The line search decreased the step size to within tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the merit function. You may need more than MachinePrecision digits of working precision to meet these tolerances. >>
Out[484]= {0., 0}
During evaluation of In[480]:= 我的代码,虽然只是For循环这样的初级代码,但是速度绝不逊色,结果也不出错,值得推荐
Out[486]= {0., 350704366}

复制代码

ggggwhw · 发表于 2010-2-4 19:00:28

№3.
本着能不用max就不用,能不用变量就不用的原则,我推荐下面的写法,当然没有任何实质性的改动,我曾经测试过,max在Mathematica 中好像花的时间可以忽略的:

FactorInteger[600851475143][[-1]] /. {x_, _} -> x

复制代码

jimogsh · 发表于 2010-2-4 20:40:55

本帖最后由 jimogsh 于 2010-2-4 20:43 编辑

№2.
貌似我的方法是最好的方法,下面是三种方法的比较:In[473]:= n = 4*10^4;
Print["waynebuaa的代码虽然健壮,但是结果有时会出错,比如:"]
Timing@Total@Fibonacci[Range[3, Round@Log[GoldenRatio, n Sqrt[5.]] ...
ggggwhw 发表于 2010-2-4 18:55

这个排版太差了吧，还得找很久才能找到您自己的方法。
在第二题的讨论中也没有看见您的帖子，所以没有引用这个方法。

第一题虚心接受您的观点。
第三题您说“Max能不用就不用”，我没听说过这样的说法，也不懂得其中的奥妙，您能解释下吗？

ggggwhw · 发表于 2010-2-4 20:57:12

№6.
我觉得将标题改成计算前100个自然数的立方和与100个自然数的平方和的差值是不是更顺口一些,不过你的翻译还是没有问题的,两种说法计算的结果是相同的,
类似于№1的解法.№6用下面的解法最合适了:

(*\!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(n\)]
\*SuperscriptBox[\(i\), \(3\)]\)=1/4 n^2 (1+n)^2;
\!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(n\)]
\*SuperscriptBox[\(i\), \(2\)]\)=1/6 n (1+n) (1+2 n);
1/4 n^2 (1+n)^2-1/6 n (1+n) (1+2 n)=1/12 (-1+n) n (1+n) (2+3 n)
于是相当于计算 1/12 (-1+n) n (1+n) (2+3 n)/.n->100*)
1/12 (-1 + n) n (1 + n) (2 + 3 n) /. n -> 100

复制代码

下面就是我的№2的方法,我在一个代码中用了三种方法让你比较结果的:

n = 4*10^6;
Timing[a = 1;
b = 2;
sum = 0;
For[a = 1; b = 2, b < n, b += c, If[EvenQ[b], sum += b];
c = a;
a = b;];
sum]

复制代码

ggggwhw · 发表于 2010-2-4 21:29:33

№8.
Fred的代码效率更高吗?我测试了一下,并不是你说的那样

n = 731671765313306249192251196744265747423553491949349698352031277450\
6326239578318016984801869478851843858615607891129494954595017379583319\
5285320880551112540698747158523863050715693290963295227443043557668966\
4895044524452316173185640309871112172238311362229893423380308135336276\
6142828064444866452387493035890729629049156044077239071381051585930796\
0866701724271218839987979087922749219016997208880937766572733300105336\
7881220235421809751254540594752243525849077116705560136048395864467063\
2441572215539753697817977846174064955149290862569321978468622482839722\
4137565705605749026140797296865241453510047482166370484403199890008895\
2434506585412275886668811642717147992444292823086346567481391912316282\
4586178664583591245665294765456828489128831426076900422421902267105562\
6321111109370544217506941658960408071984038509624554443629812309878799\
2724428490918884580156166097919133875499200524063689912560717606058861\
1646710940507754100225698315520005593572972571636269561882670428252483\
600823257530420752963450;
Print["我的代码:"];
Timing[arr = IntegerDigits[n];
len = Length[arr] - 4;
brr = Max[Table[Product[arr[[i]], {i, j, j + 4}], {j, 1, len}]]]
Print["Fred的代码:"];
Timing[Max@Apply[Times, Partition[IntegerDigits[n], 5, 1], 2]]

复制代码

其实我觉得Fred的代码总是内存大户.我不喜欢写这样的代码,因为我的机子经常会停止运转的.从上面的代码你或许看不出两个的运行速度的差别,那么下面我稍作修改,
将一千位数字n换成一百万位数n后,发现我的代码历时1.781秒算出结果,Fred的代码历时2.062秒算出结果,
将一千位数字n换成一千万位数n后,发现我的代码历时17.657秒算出结果,Fred的代码显示内存不够.
下面略作修改后的测试代码:

arr = Table[Random[Integer, 9], {i, 1, 10^6}]
Print["我的代码:"];
Timing[
len = Length[arr] - 4;
brr = Max[Table[Product[arr[[i]], {i, j, j + 4}], {j, 1, len}]]]
Print["Fred的代码:"];
Timing[Max@Apply[Times, Partition[arr, 5, 1], 2]]

复制代码

ggggwhw · 发表于 2010-2-4 21:47:59

№10.

Print["我的代码"]
Timing[
max = PrimePi[2*10^6];
Total@Prime[Range[max]]
]
Print["你给的代码"]
Timing[Total@Select[Range[2 10^6], PrimeQ]]

复制代码

下面是运行结果:

During evaluation of In[39]:= 我的代码
Out[40]= {0.703, 142913828922}
During evaluation of In[39]:= 你给的代码
Out[42]= {3., 142913828922}

复制代码

ggggwhw · 发表于 2010-2-4 22:10:40

今天或明天应该会离开论坛一段时间了,所以今天在论坛里找一些问题在离开的日子里想想,就看了看以前的欧拉习题,英文的看着费力,就将主要精力放在了你的问题和代码里,提的一些意见有些吹毛求疵,但是目的只是追求完美而已,我衷心地支持你的工作.
强烈支持中文版本的总结,至少应该是有汉英混编的总结.

FreddyMusic · 发表于 2010-2-5 13:15:13

J,

动作再快一点，这前50题大伙都做过了。
挑最好的代码，分析要深入、有智慧。

账号		自动登录	找回密码
密码			注册

账号		自动登录	找回密码
密码			立即注册

[欧拉习题] [Project Euler前50题总结]交稿！！（8.14）

本帖子中包含更多资源

评分

相关帖子

本帖子中包含更多资源

RE: 破土动工：ProjEuler前50题的M@解法

本帖子中包含更多资源