2015年1月1日

求斐波那契数的非递归实现

今天在做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()

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*