python解决project euler题目的乐趣

52037317

　　寒假期间学习了python，现在基本上就能上手使用它来解决project euler里面的题目了，用python真的是没得说的，一个字“赞”。在C++中需要用一大堆代码实现的算法，在python中，只需要那么短短几行。而且还有惊艳的运行速度。借用《可爱的python》里面的一句话：“人生苦短，我用python”。
　　【project euler 055】
　　求经过一系列规则不能得到回文数的数的个数。题目在此：
　　If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
　　Not all numbers produce palindromes so quickly. For example,
　　349 + 943 = 1292,
　　
1292 + 2921 = 4213
　　
4213 + 3124 = 7337
　　That is, 349 took three iterations to arrive at a palindrome.
　　Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
　　Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
　　How many Lychrel numbers are there below ten-thousand?
　　NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
　　思路：从1到10000进行逐个扫描，对于每个数进行判断，是否经过上述规则都不能产生回文数。在python中，有很方便的做法判断一个数是否是回文数。只需比较对称的列表位置是否相同 arr == arr[lenth-1-i], i从0开始。当然做完之后发现有牛人用几行代码就把一切搞定了。不信请看：
　　

　　
def Lycheck(n):
　　
for i in range(0,50):
　　
n = n+int(str(n)[::-1])
　　
if str(n)==str(n)[::-1]: return False
　　
return True
　　
len([n for n in range(10000) if Lycheck(n)])
　　

　　python给我的一个印象就是列表操作很方便，类型转换超级自由，而且对于大数的运算非常快。这道题目用python解只用了1s。amazing！ 另外一个很特别的是，python支持函数式编程，lambda算子可以创建函数对象，传入某个程式里面，非常了得。本人在DES的程序中，也看到了类似lambda(x,y: x^y)的函数，非常地神奇，能够对map里面的元素都执行这个操作。
　　【project euler 056】
　　A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
　　Considering natural numbers of the form, ab, where a, b 100, what is the maximum digital sum?
　　思路： 很明显，这个位的和要大，显然要够长。既要够长，每位数字的数字也要够长。我脑海里面立马蹦出了99的99次方这样的数字。但是不能想当然，我还是从91开始，计算到100，铁定能够找到那个各位和最大的数。程序如下：
　　

　　
# project euler 56
　　
# !/usr/bin/python
　　
# -*- coding: utf-8 -*-
　　
import sys
　　

　　

　　
def power_digit_sum():
　　
max_digits_sum = 0
　　
for i in range(91,100):
　　
for j in range(91,100):
　　
power_num = pow(i,j)
　　
print power_num
　　
digits_sum = sum_digits(power_num)
　　
print digits_sum
　　
if digits_sum > max_digits_sum:
　　
max_digits_sum = digits_sum
　　
print max_digits_sum
　　

　　

　　
def sum_digits( power_num):
　　
digits_sum = 0
　　
while power_num != 0 :
　　
rear_num = power_num % 10
　　
power_num = power_num / 10
　　
digits_sum += rear_num
　　
return digits_sum
　　
#return sum(map(int, power_num))
　　

　　

　　
power_digit_sum()
　　

　　运行就能够找到答案了。
　　【project euler 057】
　　It is possible to show that the square root of two can be expressed as an infinite continued fraction.

2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

　　By expanding this for the first four iterations, we get:
　　1 + 1/2 = 3/2 = 1.5
　　
1 + 1/(2 + 1/2) = 7/5 = 1.4
　　
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
　　
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
　　The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
　　In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?
　　思路：找规律，发现只要用几个变量就可以完全表示好这个式子的模式，从下往上看，有相当一部分x=（1/（2+1/2）），是由上一步产生的，而每步都是1+1/（2+x)组成的，而x的产生可以是递归的。另外第一次i=0的时候，比较特殊，是1+x的模式。
　　总结规律如下：
　　

　　
# 计算展开式 e
　　
# count 第几次展开, 采用递归法则
　　
def cal_expansion(count,a,b):
　　
c = 1
　　
d = 1
　　
e = 2   # (2 + 1/2) 加号前的2
　　
if count == 0:  # first time is special
　　
c = b + a
　　
d = b
　　
return a,b,c,d   # 递归最底层
　　
elif count > 0:  # the second time is special
　　
a = (b*e) + a
　　
a,b = swap(a,b)
　　
#print count,a,b
　　
count = 0            ​# 因为采用了自上而下，故而不这里的递归需要有所修改，直接奔第0次
　　
return  cal_expansion(count,a,b) #递归调用
　　

　　
# swap function
　　
def swap(a, b):
　　
b,a = a,b
　　
return a,b
　　

　　

　　
TIMES = 1000
　　
# every time
　　
a,b,c,d = 1,2,1,1
　　
count = 0
　　
strc,strd ="",""
　　
for i in range(0,TIMES):
　　
print i,"(",a,"/",b,")",c,d
　　
a,b,c,d = cal_expansion(i,a,b)   # 重复传递的a/b部分,如1/2， 2/5，5/12等，以及整个式子的结果c/d，如3/2
　　
strc,strd = str(c),str(b)
　　
if len(strc) > len(strd):  #位数比较
　　
count +=1
　　
print count
　　

　　程序采用了递归，但是考虑到从上往下计算将会节省很多时间，故而用迭代进行计算。原以为迭代和递归是矛盾的，不能同时使用的，但是我先计算出的成果，从是能够运用到下一步的计算当中。这令我非常有成就感。下面是运行的例子：

　　链接 projectEuler