python解决project eule

 寒假期间学习了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[i] == 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 (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ 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, a^b, 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