Euler Project(欧拉计划)刷题记(Problem 1~50)

Standard

EulerProject官网地址)是一系列问题的集合,涉及数学与计算机方面。有的问题看起来是一个计算机问题,但却可以用数学推导去化简,有的问题化简到最后,也需要用编程技巧写代码来求解它。

EulerProject不限制你所用的语言,你可以使用Mathematica这样的数学工具,也可以使用PythonC++,甚至可能连编程语言都不需要,如果是自己推导算出答案的话。在解决完一道题后,会开放该题的讨论区,在那里你就能看到其他人是怎么解决这道题的。

EulerProject强调的是解决问题的想法,而不是你用什么编程语言。并且上面的题都是围绕一个很有趣的“一分钟法则”来设计的。这个法则是说,有可能你写了一个算法花了很长时间才算出结果,但总存在一个高效的算法能够在一分钟内得出结果,即使在一台性能比较差的计算机上。

然后,我就是开始了在EP上艰难的旅程,我用的是Mathematica语言。

 

如果说把每一道题的解答过程都写出来的话,就会显得很麻烦,而且已经有人做过这种事了。如果不写的话,又没什么好说的,真是太纠结了。干脆就这么水掉吧。

转念一想,很多人可能是第一次听到EulerProject,为了让更多人了解它,我觉得还是有必要举点例子,把一些有代表性的题拿出来说一下的。

 

EP Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

 

题目意思是这样的:如果把10以下的3或5的因子列出来的话,有3,5,6,9,它们的和是23. 现在问1000以下3或5的因子之和是多少。

这道题作为整个EulerProject的第一题,一定程度上能传达出整个系列题目的风格,也侧面反映出能刷它的要求。就这道题而言,一般有两种做法,一种做法是写个算法枚举,另一种是通过数学推导直接求和。两种思路都能解决问题,并且实现起来也不难,就看你喜欢哪一种了。

如果是前者,只要有一点基本的代码功底,写一个这样的程序算一下应该没什么问题,实际上,对编码能力的要求并不是很高。因为它不是POJ,它不考验你算法理论、数据结构学的怎么样,只要求你能够用代码的工具去把问题实现即可。(像Python这种轻巧的脚本式语言就是不错的选择)

如果是后者,只要你能反应过来是“3的倍数+5的倍数-15的倍数”就足够了,容斥原理而已。拥有较强数学思维能力的同学可能会觉得后者更加适合。毕竟闭上眼睛想象,画画草稿纸就能蹦出一个答案,还是很了不起的。

 

EP Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

 

好逗的题目啊,问你第10001个质数是什么?

100内的质数还能背一下,可第10001个质数恐怕没人能直接报出来吧。

我用Mathematica我自豪,下面的代码可以直接得到答案:

Prime[10001]

用Python的话就要长一点了。

 

好像上面的题都有点水了,就没有有点挑战性的题目么?别急,前面题号才是个位数呢。

EP Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

 

这个题有点长,我来翻译一下:

d(n) 表示 n 的所有的真因子(小于 n )之和。

d(a) = b, d(b) = a a ≠ b 时,称 ab 为友好数 (amicable numbers)

例如,220的真因子有1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110,故 d(220)=284 。而284的真因子有1,2,4,71,142,因此,d(284)=220

找出10000以下的所有友好数并求和。

 

这个问题看上去至少不那么显然了。从整体来看,应该是要枚举,但是单从求一个数的真因子之和来看,这妥妥的是个数学问题,是有通项公式可以求的。推一下就出来了。

但如果连真因子也要枚举计算的话,估计离超时也不远了。还记得之前提到的“一分钟法则”吗?无脑枚举当然可以解决问题,但是不能优雅的解决问题,而且枚举也属于是没有办法的办法了。就此题而言,差别不会很大,但是越往后,枚举就越困难,没有经过数学化简的算法很有可能跑一个小时也出不来结果。(本人有亲身经历= =)

所以,学点数学还是很重要的。或者说,要以一种数学的思维去思考问题,题号越往后越能体现出来。(大概要到3位数吧。。反正我现在还没刷到 ╯︵╰)

 

EP Problem 26

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

 

这题我蛮喜欢的,简洁又不失分量。(虽然题目有点长Orz)

题目啰哩啰嗦,说白了就是要找到1000以下的数中,倒数的小数部分的循环节位数最长的那个数。(还是好绕口Orz)

 

我记得我是认真的又推了一遍循环节长度满足的条件的,然后代码就很简单了。看到那个论坛里还有人做小数部分的正则表达式匹配,顿时觉得是。。小题大做了。

当然啦,我是不会在这里推导的,就算推导过程也不麻烦(就是乘上一个数再减 1 神马的)。但是化简后的代码的确跑的飞快,虽然/因为那个代码写的很渣,就不贴出来了。

 

已经举了4个例子了,再举一个我现在还没做出来的题目,然后介绍就接近尾声了。

 

 

EP Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

 

题目的意思是:在1,000,000下,能被最多连续质数之和表出的数是多少?

看样子还是枚举,问题就在于枚举维度的选择了,找对了方向应该不难。

(吐槽:这一题号段好多枚举问题啊,而且一个比一个坑= =)

 

收工睡觉!(~﹃~)~zZ