首页 > Project Euler > Project Euler个人解答(Problem 31~40)

Project Euler个人解答(Problem 31~40)

2013年12月19日 发表评论 阅读评论

pe_banner_light嗯~总算搞完了,其实发现复习以前做过的题也挺有意思的,至少很多题我现在拿来写博客的时候就会静下心来想会不会有更高的方法呢~什么的。。。【其实我才不会告诉你中间有几题我以前的代码找不到了,现在被迫重写。。】

嘛~第四弹,离赶上我自己原有进度还有两弹~而且现在博文这里不写完实在不好意思去EP上刷题。。。

题目这里开始明显和前面有难度上的分界线了,但是虽然这么说,但是这10道题目顶多还是只能称之为值得讨论研究,还不能算难。。只要你多思考一点点,就可以让你的程序结果很快的跑出来,因为这里开始题目暴搜解法已经开始表示吃紧了。。

Problem 31:Coin sums

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?

翻译:
在英国,货币是由英镑£,便士p构成的。一共有八种钱币在流通:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) 和 £2 (200p).

要构造£2可以用如下方法:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

允许使用任意数目的钱币,一共有多少种构造£2的方法?

思路:
动态规划:
每次选择一个钱币,然后计算除去这个钱币后剩下的钱还有多少种构造方法,为了有序,避免重复,可以设定这一次取出的是n便士的钱币后,接下来剩余的钱的构造方式里面不可以包含比n小的钱币。

比如说一开始200便士,我们可以计算递归计算拿走1便士后,剩余199便士有多少构造方式,加上拿走2便士后剩余198便士有多少种构造方式,。。。

其中如果拿了5便士了,剩余的钱的构造方式里面就不可以再用1和2便士了。。

Code:Python

def Sol(money,coinlist):
    if len(coinlist) == 1:
        return 1
    sum = 0;
    for i in range(len(coinlist)):
        if money-coinlist[i] == 0:
            sum += 1
        elif money-coinlist[i] > 0:
            sum += Sol(money-coinlist[i],coinlist[:i+1])
    return sum
print Sol(200,[1,2,5,10,20,50,100,200])

Problem 32:Pandigital products

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

翻译:
如果一个n位数使用了1到n中每个数字且只使用了一次,我们称其为pandigital。例如,15234这个五位数,是1到5pandigital的。

7254是一个不寻常的数,因为:39 × 186 = 7254这个算式的乘数,被乘数和乘积组成了一个1到9的pandigital组合。

找出所有能够组合成1到9pandigital的乘法算式中乘积的和。

提示: 有的乘积数字能够被多个乘法算式得到,所以在计算时要记得只计算它们一次。

思路:
其实可以很容易分析出来,满足题目要求的乘法只有两种情况:

a × bcde = fghi

ab × cde = fghi

所以可以对1~9进行全排列,然后测试这两种情况是否成立即可。

Code:Python

def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;

def cal(ml):
    a = 10*ml[0]+ml[1];
    b = 100*ml[2]+10*ml[3]+ml[4];
    c = 1000*ml[5]+100*ml[6]+10*ml[7]+ml[8];
    return a*b == c

def cal2(ml):
    a = ml[0];
    b = 1000*ml[1]+100*ml[2]+10*ml[3]+ml[4];
    c = 1000*ml[5]+100*ml[6]+10*ml[7]+ml[8];
    return a*b == c

sum = 0;
prolist = [];
for pql in QPL([1,2,3,4,5,6,7,8,9]):
    if cal(pql) == True:
        t = 1000*pql[5]+100*pql[6]+10*pql[7]+pql[8];
        if t not in prolist:
            sum += t;
            prolist.append(t)
    if cal2(pql) == True:
        sum += 1000*pql[5]+100*pql[6]+10*pql[7]+pql[8];
        if t not in prolist:
            sum += t;
            prolist.append(t)
print sum

Problem 33:

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.

翻译:
分数 49/98 是一个奇怪的分数:当一个菜鸟数学家试图对其进行简化时,他可能会错误地可以认为通过将分子和分母上的9同时去除得到 49/98 = 4/8。但他得到的结果却是正确的。

我们将30/50 = 3/5这样的分数作为普通个例。

一共有四个这样的非普通分数,其值小于1,并且包括分子和分母都包括2位数。

如果将这四个分数的乘积约分到最简式,分母是多少?

思路:
暴力解决就行了,排除掉10的倍数的情况还可以防止除零溢出。

Code:Python

result_list = [];
for i in range(11,100):
    for j in range(i+1,100):    
        if mod(i,10)==0 or mod(j,10)==0 :
            continue
        a = i // 10
        b = mod(i,10)
        c = j // 10
        d = mod(j,10)
        if (i/j == a/c and b == d) or\
           (i/j == a/d and b == c) or\
           (i/j == b/c and a == d) or\
           (i/j == b/d and a == c):
            result_list.append([i,j])
print reduce(lambda x,y:x*y,map(lambda x:x[1]/x[0],result_list))

Problem 34:Digit factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

翻译:
145 是一个奇怪的数字, 因为 1! + 4! + 5! = 1 + 24 + 120 = 145.

找出所有等于各位数字阶乘之和的数字之和。

注意: 因为 1! = 1 和 2! = 2 不是和的形式,所以它们不算在内。

思路:
之前也用过类似的方法,说先要找到历遍的上限,n位数最大值为10n-1,而其各个数字阶乘和最大可能为n9!=362880n,所以:
EP-pro34
最高位数为7位。

Code:Mathematica

Select[Range[10, n*9! /. %],Plus @@ (#! & /@ IntegerDigits[#]) == # &]//Total

Problem 35:Circular primes

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

翻译:
我们称197为一个循环质数,因为它的所有轮转形式: 197, 971和719都是质数。

100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.

100万以下有多少个循环质数?

思路:
法一:暴力解决,这个在Mathematica上需要42秒完成。
法二:预先筛选,可以很容易想到,各个位数里面不可能包含偶数,其次,也不可能包含5,所以所有位数只能由1,3,7,9组成。但是记得有两个意外情况哦,就是2和5。这个在Mathematica里面需要7秒。

Code:Mathematica

(*判断是否是循环质数:*)
IsCircularPrimes[t_] := 
  Count[PrimeQ@FromDigits[#] & /@ (RotateLeft[IntegerDigits[t], #] & /@
        Range[0, Length[IntegerDigits[t]] - 1]), False] == 0;
(*法一:*)
Select[Range[1, 1000000], IsCircularPrimes] // Length
(*法二:*)
SieveFun[t_] := Count[IntegerDigits[t], Except[1 | 3 | 7 | 9]] == 0

tSieve = Select[Range[1, 1000000], SieveFun];
Select[tSieve, IsCircularPrimes] // Length + Length[{2,5}]

Problem 36:Double-base palindromes

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

翻译:
十进制数字585 = 10010010012 (二进制),可以看出在十进制和二进制下都是回文(从左向右读和从右向左读都一样)。

求100万以下所有在十进制和二进制下都是回文的数字之和。

(注意在两种进制下的数字都不包括最前面的0)


思路:
法一:暴力解决,这种方法其实也挺快的,Mma里面只要4秒。但是这个毕竟是扫描了100个数啊!!

法二:这是一个做关于回文数的算法题常用的思路;

我们先分析上限100万,他的二进制数是11110100001001000000,这是一个20位的二进制数,也就是说,我们只要扫描1~20位二进制数,从0000000000000000000到1111111111111111111就可以扫描包含完整的全部1~100万了,但是,我们根本不需要在二进制数里面扫描20位,因为题目说了回文数这个东西,所以我们只需要扫描10位就可以了,然后把这个数倒转,连接起来,就保证了二进制数必然是回文数,然后再转去十进制数,判断一下就可以了;【这里需要注意的是注意拼接二进制数的时候有两种方法,ab可以变成abba和aba】

详情请参考代码注释

Code:Mathematica

(*法一*)
Select[Range[1, 1000000], 
       IntegerDigits[#, 2] == Reverse[IntegerDigits[#, 2]] && 
       IntegerDigits[#] == Reverse[IntegerDigits[#]] &
      ]
Total[%]

(*法二*)
(*扫描1~1024的二进制数*)
t = IntegerDigits[#, 2] & /@ Range[1024];
(*判断十进制数是不是回文数*)
IsPalindromes[n_] := IntegerDigits[n] == Reverse[IntegerDigits[n]];
(*筛选ab->abba情况*)
Select[t, IsPalindromes[FromDigits[#~Join~Reverse[#], 2]] && #[[1]] == 1 &];
FromDigits[#~Join~Reverse[#], 2] & /@ %;
r1 = Total[%];
(*筛选ab->aba情况*)
Select[t,IsPalindromes[FromDigits[#[[;; -2]]~Join~Reverse[#], 2]] && #[[1]] == 1 &];
FromDigits[#[[;; -2]]~Join~Reverse[#], 2] & /@ %;
r2 = Total[%];
(*计算总和*)
r1 + r2

Problem 37:Truncatable primes

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.

翻译:
3797这个数很有趣。它本身是质数,而且如果我们从左边不断地裁去数字,得到的仍然都是质数:3797,797,97,7。而且我们还可以从右向左裁剪:3797,379,37,3,得到的仍然都是质数。

找出全部11个这样从左向右和从右向左都可以裁剪的质数。

注意:2,3,5和7不被认为是可裁剪的质数。

思路:
法一:可以暴力解决,但是很慢,Mma里面要55秒;

法二:参考35题,可以发现符合条件的数中间的数必然是1,3,7,9组成,所以可以大幅度减少判断无谓的数的时间,时间缩短至9秒。

法三:我们知道三位数以上的话,所有数肯定是全部由1,3,7,9四种数字组成的,所以我们可以对于三位数以上根据这个条件生成有可能符合条件的数,就是由这些数组成的多位数。而对于两位数,随便怎么搞都行了。

假设我们知道了二位数符合条件的有4个了,那么只要再找出3位数以上的7个就可以了;这个方法只要0.4秒就可以找出来全部了!!

Code:Mathematica

GetTruncate[n_] :=
         (Take[IntegerDigits@n, {#, -1}] & /@ Range[Length@IntegerDigits@n])~Join~
         (Take[IntegerDigits@n, {1, #}] & /@ Range[Length@IntegerDigits@n - 1])

IsTruncatablePrimes[n_] := 
      (Select[FromDigits /@ GetTruncate[n], ! PrimeQ[#] &] // Length) == 0
(*法一*)
Counter = 0;
L = {};
i = 11;
While[Counter < 11,
      If[IsTruncatablePrimes[i], Counter += 1; AppendTo[L, i]];
      i += 1;
      ]
(*法二*)
SieveFun[t_] := Count[IntegerDigits[t][[2 ;; -2]], Except[1 | 3 | 7 | 9]] == 0
Counter = 0;
L = {};
i = 11;
While[Counter < 11,
      If[SieveFun[i] && IsTruncatablePrimes[i], Counter += 1; 
      AppendTo[L, i]];
      i += 1;
     ]
(*法三*)
Counter = 0;
L = {};
i = 3;
While[Counter < 7,
      t = Select[FromDigits /@ Tuples[{1, 3, 7, 9}, i], 
      IsTruncatablePrimes];
      Counter += Length[t];
      AppendTo[L, t];
      i += 1;
      ]

Problem 38:Pandigital multiples

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

翻译:
将192与1,2,3分别相乘得到:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
将这三个乘积连接起来我们得到一个1到9的pandigital数, 192384576。我们称 192384576是192和 (1,2,3)的连接积。

通过将9与1,2,3,4和5相乘也可以得到pandigital数:918273645,这个数是9和(1,2,3,4,5)的连接积。

用一个整数与1,2, ... , n(n大于1)的连接积构造而成的1到9pandigital数中最大的是多少?

思路:
这道题可以做很多人工思考,来缩减范围。

首先,题目已经给出了一个数918273645,我们所要寻找的答案必然大于这个数,所以线索一:答案必然以9开头;

然后因为n大于1,所以我们要找的数必然不可能是五位数,所以,线索二:那个构造数一定最多是四位数;

因为n=1是放在答案的最左边,所以线索三:我们要找的构造数必然以9开头;

二位数以9开头的数只可能构造出8位数(2+3+3)或者11位数(2+3+3+3),所以线索四:二位数不予考虑;

三位数以9开头的数只能够造出7位数(3+4)或者11位数(3+4+4),所以线索五:构造数必然是四位数!!

我们要搜索的构造数范围就是9182(题目给出的那个数是9182开头)到9876;

但是这个范围还是嫌大,可以继续减少,就是构造数的百位一定不可能大于4,因为大于四的话,那么得到的数必然就是9***19***,9就重复了;所以范围就变成9182到9487;

但是还可以继续减少,因为我们知道结果必然是9***1****,所以1绝对不可能出现在构造数里面,所以,范围最后变成9234到9487!!

Code:Mathematica

Select[Range[9234, 9487],Sort@(IntegerDigits[#]~Join~IntegerDigits[2 #]) == Range[1,9] &]
Max[%]

Problem 39:Integer right triangles

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?

翻译:
如果p是一个直角三角形的周长,三角形的三边长{a,b,c}都是整数。对于p = 120一共有三组解:

{20,48,52}, {24,45,51}, {30,40,50}

对于1000以下的p中,哪一个能够产生最多的解?

思路:
这个是之前第九题里面推出来的结论,下面将其一般化:EPP39
所以代码就比较简单了~

Code:Python

maxp = -1;
max_counter = 0;
for p in range(1,1001):
    counter = 0;
    for a in range(1,int(p-p/sqrt(2))):
        b = p/2*(p-2*a)/(p-a);
        if b == int(b):
            counter += 1;
    if max_counter < counter:
        maxp = p;
        max_counter = counter
print maxp

Problem 40:Champernowne's constant

An irrational decimal fraction is created by concatenating the positive integers:

0.12345678910 1112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

翻译:
将正整数连接起来可以得到一个无理小数:

0.12345678910 1112131415161718192021...

可以看出小数部分的第12位是1。

如果用dn表示这个数小数部分的第n位,找出如下表达式的值:

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

思路:
这道题原则上是可以手算的,不过这种手算题没什么技术含量,比较适合高中数学老师拿来虐待学生用。。这里就不算了。。直接Mma了事~

Code:Mathematica

t = ToString@FromDigits@Flatten@IntegerDigits@Range[1, 1000000];
Times @@ ToExpression@(StringTake[t, {#}] & /@ Table[10^i, {i, 0, 6}])

【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

  • 红薯

    pe32:With[{id = IntegerDigits}, Union @@ Table[If[a*b <= 9876 && Union[id , id , id[a b]] == Range , a b, 0], {a, 123, 1987}, {b, 2, 98}] // Tr ] // AbsoluteTimingpe33:Times @@ Cases[Table[{a, b, c}, {a, 9}, {b, 9}, {c, 9}], {a_, b_, c_} /; a < c && (10 a + b)/(10 b + c) == a/c :> a/c, 3] Times @@ (a/c /. Solve[{a < c, (10 a + b)/(10 b + c) == a/c, And @@ Thread[1 <= {a, b, c} <= 9]}, Integers])

    • 红薯

      pe34:Sum[Boole[n == Total[Gamma[IntegerDigits + 1]]] n, {n, 3, 3*^6}] // AbsoluteTimingTable[ With[{A = Flatten@Outer[Plus, ##] & @@ Array[Gamma[Boole[# == 1]~Range~9 + 1] &, n]}, Pick[A, A~BitXor~Range[10^(n - 1), 10^n - 1], 0] ], {n, 3, 7}]~Total~-1 // AbsoluteTiming注意:以上代码在Mathematica9下速度很快(第一个不到1.3s,第二个不到0.5s),但Mathematica8中比较慢,要加速需要改写

      • 红薯

        pe40:Times @@ Flatten[IntegerDigits@Range[10^6]][[10^Range[0, 6]]]

        • 真是又简洁又快!!

          • 红薯

            pe40还可以优化,运行时间0.1sTimes@@(Join@@Table[Flatten@Tuples@Table[Range[Boole[i==1], 9], {i, n}], {n, 6}])[[10^Range[0,6]]] // AbsoluteTiming

            • 请问大大你印象中有哪些Mma的做法会导致程序运行得比较慢的?我现在给我看两份算法其实我也分不清究竟哪一个在Mma里面会比较快。。

      • 大神你为何这么屌?!!法二我读了半天才懂。。。Outer这个用起来很难上手的样子。。。为啥Mma8会慢?

        • 红薯

          Mma8中慢与PackedArray有关,Outer的参数需要Developer`ToPackedArray,还有Mma8不支持Gamma函数的编译,9.0开始支持的

          • 我对Mma运行速度快慢的认知一直停留于这篇文章的水平。。http://blog.wolfram.com/2011/12/07/10-tips-for-writing-fast-mathematica-code/

            • 红薯

              这篇文章不错,不过讲得不够细,经验很重要,Mma用好了完全可以和Matlab、Python拼速度

              • 红薯大大你用Mma多久了?

                • 红薯

                  差不多4年

                  • 给跪了。。。我除去中间有段空白期,大概半年。。。

    • 研读了一下你的代码,突然觉得好像以前觉得PE里面Mma不好解决的问题现在都有点眉目的!!

      • 红薯

        pe31:Length@IntegerPartitions[200, All, {1, 2, 5, 10, 20, 50, 100, 200}]Length@FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100, 200}, 200]Coefficient[ Series[Product[ 1/(1 - x^i), {i, {1, 2, 5, 10, 20, 50, 100, 200}}], {x, 0, 200}], x^200]Sum[1, {a, 200, 0, -200}, {b, a, 0, -100}, {c, b, 0, -50}, {d, c, 0, -20}, {e, d, 0, -10}, {f, e, 0, -5}, {g, f, 0, -2}]pe36:With[{f = # == Reverse[#] &}, Sum[Boole[f@IntegerDigits && f@IntegerDigits[i, 2]] i, {i, 10^6}] ] // AbsoluteTiming

        • 看到31题四种解都那么简洁。。。。直接跪了。。。红薯大大PE的题目是你以前做过的还是现做的?

          • 红薯

            以前做过一些,是跳着做的,也有现做的。31题是以前做过的

    • 多说真是好烦。。。不知道怎么关文本转表情。。。。

  • MZ

    E.P.不是人吗?不过PE

    • 你想表达的意思是。。。

      • MZ

        PE是体育

        • 所以我还是没懂你之前想表达什么。。

          • MZ

            用小写好了,免得——脑或心不在焉的人——搞错

            • 。。。。。。这思路跳跃好大。。

  • cherichy

    pe.33 python:[[10*x+i,10*i+y] for x in range(1,10) for y in range(1,10) for i in range(1,10) if 9*x*y+i*y-10*i*x==0 and 10*x+i!=10*i+y]

  • cherichy

    pe35:MMA 换一个生成列表的办法。。只要0.3s哦test[x_] := And @@ PrimeQ /@ NestList[FromDigits[RotateLeft[IntegerDigits[#]]] &, x, IntegerLength - 1]testlist = FromDigits /@ Tuples[{1, 3, 7, 9}, #] & /@ Range[1, 6] // Flatten;Length@Select[testlist, test] + 2