python解决project euler题目的乐趣
寒假期间学习了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, 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()
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 http://projecteuler.net/images/symbol_lt.gif 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.
http://projecteuler.net/images/symbol_radic.gif 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次
returncal_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
程序采用了递归，但是考虑到从上往下计算将会节省很多时间，故而用迭代进行计算。原以为迭代和递归是矛盾的，不能同时使用的，但是我先计算出的成果，从是能够运用到下一步的计算当中。这令我非常有成就感。下面是运行的例子：
http://bibodeng.web-149.com/content/plugins/kl_album/upload/201303/3e434d96aefab6aa95f7e7edf8a865152013032110412618163.png
链接 projectEuler
页:
[1]