本文共 1215 字，大约阅读时间需要 4 分钟。

（Python实现）剑指offer—斐波那契数列

题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

这个题目也不难，第一反应应该是使用递归来编写代码，我的第一反应也是，但是看过书后发现，如果使用递归的话，当n 很大时，递归计算的时间复杂度时以n 的指数方式增长的。复杂度过高。 如果使用循环的话，其时间复杂度恒为O(n) 。 循环代码如下：

# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        if n == 0:            return 0        if n == 1:            return 1        Fi_one = 1        Fi_two = 1        for i in range(2, n):            Fi_one, Fi_two = Fi_two, Fi_one+Fi_two        return Fi_two

递归代码如下：

# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        if n == 0:            return 0        if n == 1:            return 1        return self.Fibonacci(n-1) + self.Fibonacci(n-2)

使用递归在牛客上跑测试用例就会提示超时。

该题还可以扩展为青蛙跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

当n>2 时，n 阶台阶的不同跳法为：$f(n)=f(n-1)+f(n-2)$ ，这个函数实际上就是斐波那契数列。上述代码改改如下：

# -*- coding:utf-8 -*-class Solution:    def jumpFloor(self, number):        # -*- coding:utf-8 -*-        if number == 0:            return 0        if number == 1:            return 1        Fi_one = 1        Fi_two = 2        for i in range(2, number):            Fi_one, Fi_two = Fi_two, Fi_one+Fi_two        return Fi_two

转载地址：http://mqmws.baihongyu.com/