Python算法题

bobpxp

　　projecteuler上面的题，试着用python写了下


　　
问题1：列出所有是3或者是5的倍数且小于10的自然数，结果是3、5、6、9，这些值的结果之和为23，求小于1000且是3或者是5的倍数的值的和？一行代码解决





方法一：//java程序员的思维




def getSum(num1,num2,maxValue):
values = []
for i in range(max):
if i%num1==0 or i%num2==0:
values.append(i)
return reduce(lambda x,y:x+y,list)
 

方法二：//很pythonic的写法


print sum([x for x in range( 1000) if x% 3== 0 or x% 5== 0])
 

方法三：//匿名函数写法


print sum(filter( lambda x: x% 3== 0 or x% 5== 0,range( 1000)))





问题2：对于Fibonacci函数，新的项是前两项之和，如：1,1,2,3,5,8,13...找出所有偶数值项且Fibonacci序列的最大项不超过4000000.




方法一：'''回调函数,把全部小于4000000数装入list中，然后遍历选择满足条件的值'''

def fibon(maxItem):
if maxItem<=1:
return 1
else:
return fibon(maxItem- 1)+fibon( maxItem- 2)
if __name__ == "__main__":
i=1
l = []
val = fibon(i)
while 4000000 > val:
l.append(val)
i+=1
val = fibon(i)
print sum([x for x in l if x %2==0])
 

此方法不仅代码繁杂，而且执行速度也很慢




方法二：

def fibon2():
a=b=1
sum =0
while b < 4000000:
b = a+b
a = b-a
if a%2==0:
sum +=a
print sum








方法三：

def fibon3():
lastValue =2
lastSecondValue=1
newValue=0
sum = 2
while newValue<4000000:
newValue = lastValue+lastSecondValue
if newValue % 2 ==0:
sum += newValue
lastSecondValue = lastValue
lastValue = newValue
print sum
 





补：不用递归，求指定项的值

def fibon4(index):
last= lastSecond =  newValue = 1
for i in range(2 ,index):
newValue = lastSecond+last
lastSecond = last
last = newValue
return newValue