include-yy :: projecteuler

euler_portrait.png

What is Project Euler

"Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics."

https://projecteuler.net/

简单来说,欧拉计划提供了一系列和数学相关性较大的编程问题,用户可以注册账户并向网站直接提交答案而不是代码,它和一般的在平台运行代码并检测运行时间和空间有所不同。这意味着我们在解决问题时无需时刻考虑时间或空间开销,不过一般情况下程序的运行时间应该小于一分钟。我们甚至无需编写代码而是搜索学习题目背后的数学知识来通过纸笔解决。

欧拉计划始于 2001 年的 10月,由 Colin Hughes 发起,在我完成第一题时离项目的启动已经过去了 18 年。现在差不多四五年过去了,我也断断续续地完成了前一百题和一些难度较低的其他题目,也许是时候做个总结了。在 About 页面中,欧拉计划对前一百题的答案或题解发表并没有什么限制,所以我也没什么道德上的心理负担(笑):

There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, that will rarely be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

However, the rule about sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems. Problems 1 to 100 provide a wealth of helpful introductory teaching material and if you are able to respect our requirements, then we give permission for those problems and their solutions to be discussed elsewhere.

I learned so much solving problem XXX, so is it okay to publish my solution elsewhere?

这一系列的文章并不是简单地给出欧拉计划一到一百题的答案或可运行的代码,而是试图解释清楚每一题的思路,并不断迭代直到给出我认为足够好的代码。同时,我也会摘录一些有价值的讨论或题解来帮助更加全面地认识问题。如果你是第一次做这些题目,我建议首先尝试自己解决问题;如果花了几小时或几天仍然无法找出解决方法,希望这些题解能对你有所帮助。

以下题解使用的编程语言是 Emacs Lisp,一种 Lisp 方言。如果你觉得这些代码不是那么容易读懂,可以去搜索其他使用大众语言编写的题解。

GOOK LUCK AND HAVE FUN!!!

Problems 1~100 solved by myself

Problem Description TAG TIME
1 求为 3 或 5 的倍数的和  
2 求一定范围内偶 fib 数之和  
3 求某数的最大质因数  
4 求两三位数相乘能得到的最大回文数  
5 求能被 1 到 20 整除的最小整数  
6 前 100 个自然数平方和与和平方之差  
7 第 10001 个质数是什么 #prime#
8 在一个数字串中找到连续 13 个数字的最大乘积  
9 求满足 a+b+c<1000 的毕达哥拉斯三元组  
10 求小于两百万的素数的和 #prime#
11 求数字方阵中四个相邻数的最大乘积  
12 求约数数量超过 500 的第一个三角形数  
13 求 100 个 50 位数字之和的前十位数字  
14 求小于一百万数中最长的 Collatz 序列  
15 求从边长为 n 的网格左上角移动到右下角的路径总数  
16 求 21000 的各位数字和  
17 获取 1 到 1000 的数字英文表达  
18 从数字塔顶端到底端的最大路径和 #dp#
19 二十世纪有多少个月的第一天是周日  
20 求 100! 的各位数字和  
21 求 10000 以内的亲和数之和  
22 获取文件中的名字的加权和  
23 求不能被表示成两个盈数之和的正整数之和  
24 求 0-9 这十个数字从小到大排列的第 100 万个  
25 求斐波那契数列中第一个超过 1000 位的项序号  
26 求 1000 以内单位分数的最长循环节  
27 求使 n2 + an + b 生成最长连续素数的 ab 取值 #prime#
28 求螺旋数阵对角线和  
29 求不同 ab 得到 ab 结果去重后的个数  
30 求使得各位数字五次幂之和等于原数字的数字之和  
31 根据小面值硬币的不同组合构造一定的数额 #dp#
32 求使三个数刚好含有 1~9 9 个数字的 a*b=c  
33 求形如 49/98=4/8 的所有两位数真分数  
34 找出各位数字阶乘和等于其本身的数  
35 求一百万以下的轮换素数 #prime#
36 求一百万以下同时为二/十进制回文数的数之和  
37 求所有“可截素数”之和 #prime#
38 求倍数关系的数字相连仅含 1~9 的最大九位数  
39 求能构成最多直角三角形的小于 1000 的总长  
40 求钱珀瑙恩数在所有指定位置的数字之积  
41    
42    
43    
44    
45    
46    
47    
48    
49    
50    

Summary

这里是对前一百题中的一些我比较感兴趣的知识点的总结,相同的知识可能出现在多个题目中,因此这样的总结还是有一定价值的。