Table of Contents
Straight Forward
| 32 | 52 | 41 | 53 | 38 |
| 45228 | 142857 | 7652413 | 4075 | 932718654 |
| 50 | 56 | 46 | 43 | 47 |
| 997651 | 972 | 5777 | 16695334890 | 134043 |
| 49 | 55 | 44 | 97 | |
| 296962999629 | 249 | 5482660 | 8739992577 |
Answer
Source:project-euler
Project Euler Problem 33
Table of Contents
Problem
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
Solution
很简单,解空间很小,可直接Brute Force.
但我们可以进一步缩小解空间.其可能的四种形式:
- \begin{eqnarray*} \frac{10a+b}{10c+b} = \frac{a}{c} \end{eqnarray*}
- \begin{eqnarray*} \frac{10a+b}{10b+c} = \frac{a}{c} \end{eqnarray*}
- \begin{eqnarray*} \frac{10b+a}{10c+b} = \frac{a}{c} \end{eqnarray*}
- \begin{eqnarray*} \frac{10b+a}{10b+c} = \frac{a}{c} \end{eqnarray*}
对于1,4 化简得出a=c,与条件矛盾
对于3,可利用a,b,c <=9 及a<b可得到矛盾
对此只有2才是可能的形式
Answer
100
Source:project-euler
Project Euler Problem 39
Table of Contents
Problem
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?
Solution
简单,Brute Force.
Answer
840
Source:project-euler
Project Euler Problem 45
Table of Contents
Problem
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, … Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, … Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, … It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.
Solution
简单,一元二次方程组.
Answer
1533776805
Source:project-euler
Project Euler Problem 42
Table of Contents
Problem
The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
Solution
太简单
Answer
162
Source:project-euler
Project Euler Problem 31
Table of Contents
Problem
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
Solution
Brute Force
可以用穷举法:
200a+100b+50c+20d+10e+5f+2g+h = 200
穷尽a,b,c,d,e,f,g,h所有的可能.a:0~1, b:0~2…., 不过知道a = 1时, b:0, 可缩小a,b,c….大小范围, 见 C++Brute1, 类似的见C++Brute2
Recursion
很直接的方法:
- 用一个200的coin, 没用其它的
- 用零个200的coin, 由最大coin为100的来换零钱200
- 用两个100的coin, 没用其它的
- 用一个100的coin, 由最大coin为50的来换零钱100
- 用零个100的coin, 由最大coin为50的来换零钱200
…..
这里大家应该能看出规律, 用公式表示:
\begin{eqnarray*} f(t, c) = 1 & & if & c =1 &or& t=0 & \newline f(t,c) = \sum_{i=0}^{\left \lfloor \frac{t}{c} \right \rfloor}f(t-ic, s(c)) & & if & c > 1 & and & t>0 & \end{eqnarray*} 其中t是要换的钱, c是当前最大的coin,s(c)是下一个比c小的coin
见 C++Formula, 稍有不同的解法见 C++Formula1
DP
见分析
Answer
73682
Source:C++Formula, C++Formula1, C++Brute1, C++Brute2, dp
Project Euler Problem 26
Table of Contents
Problem
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.
Solution
Brute Force,将小数部分保存vector中, 然后从头遍历寻找是否有相同的 pattern, 重复找到三次即认可.
更优的做法需要数学知识1
Answer
Project Euler Problem 40
Table of Contents
1 Problem
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021…
It can be seen that the \(12^{th}\) digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
\begin{eqnarray*} d_{1} × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000} \end{eqnarray*}
2 Solution
二分法,我们无法直接得知第ith的digit,但是容易知道number n所在的位置.要找ith的digit,其必夹在1~i number之间的某个位置.如：
找1000th的digit
- 其必夹在1~1000 number之间,易知 (1 + 1000) / 2 = 500 的最后一位0在序列中的位置为1392th(number 11的最后一位1的位置为13),比1000th大,则必在1~499间
- 如此往复,我们可以找到最接近的number 370,其最后一位0为1002th,则1000th为digit 3
依此法可以找到任意ith的digit
3 Answer
210
Source:C++
Project Euler Problem 37
Table of Contents
1 Problem
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
2 Solution
brute force
3 Answer
748317
Source:C++
丰乳肥臀
以前从来没有听说过莫言,直到他得奖了,然后我在图书馆找书时,就顺手借了本丰乳肥臀。
我承认我很少看”正经”的小说,觉得无趣,抑或是因为无法沉下心来.
这本书讲述了从抗日到改革开放的上官家庭的命运。
上官鲁氏当真是十分的了不得,丈夫无能,饱受婆家欺凌,受人凌辱,她没有死去,她又十分的睿智,早已看出上官家女人的悲惨的命运.
我变了，也没变。这十几年里，上官家的人，像韭菜一样，一茬茬的死，一茬茬的发，有生就有死，死容易，活难，越难越要活。越不怕死越要挣扎着活。我要看到我的后代儿孙浮上水来那一天，你们都要给我争气！
可惜,她的宝贝,混血儿上官金童却纯粹是个毫无出息的人,虽然一表人才,却是个一辈子吊在女人乳头上的窝囊废.窝囊归窝囊,却也是好人一个.
最讨厌的是六亲不认的上官盼弟与其女鲁胜利,都只为自己的前途,最终也没有个好下场.
八姐上官玉女最是让人怜惜
上官玉女二十多岁时，心理状态还像个小姑娘，胆怯的小姑娘，畏缩的小姑娘。她终生 都像蛹一样缩在茧里，生怕给家里人增添麻烦。