求斐波那契数的非递归实现
- 算法笔记
- 2015-01-01
- 128热度
- 0评论
今天在做MOOC“程序设计入门—Python”的习题,原题如下:
题目内容:
一个斐波那契数列的前10项为:1, 2, 3, 5, 8, 13, 21, 34, 55, 89,对于一个最大项的值不超过n的斐波那契数列,求值为偶数的项的和。
输入格式:
一个正整数n,如100。
输出格式:
值为偶数的项的和,如 2 + 8 + 34 = 44。
输入样例:
100
输出样例:
44
时间限制:500ms 内存限制:32000kb
一开始,我用递归算法实现,运行时间居然超过了500ms的限制。后来改用循环实现,运行时间的测试结果是17ms!看来递归的效率真的会比循环低很多!
本题源码如下:
#!/usr/bin/env python
# encoding: utf-8
#一个斐波那契数列的前10项为:1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
#对于一个最大项的值不超过n的斐波那契数列,求值为偶数的项的和。
#第n位的斐波那契数
def fib(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
a = 1
b = 2
for i in range(3,n+1):
c = a + b
a = b
b = c
return b
def print_sum():
n = int(raw_input())
sum = 0
i = 1
while True:
temp_num = fib(i)
if temp_num > n:
break
if temp_num % 2 == 0:
sum += temp_num
i += 1
print sum
print_sum()