剑指Offer（Python） 斐波那契数列

推荐在线编程平台

牛客网在线编程

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39

分析

题目要求求出斐波那契数列的第n项，我们需要先弄明白什么是斐波那契数列，然后后就可以轻松的求解了。

概念

斐波那契数列：
指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*），用文字来说，就是斐波那契数列列由
0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。

思路

根据斐波那契数列的概念，我们可以通过递归的方式求得第n项，但是这样计算量会很大，编程平台是不能通过的，提示时间超时。那么我们就优化一下算法，用递推的方式，将前面两个值的数据记录下来，循环添加前面两个数的值就可以了。

代码

# -*- coding:utf-8 -*-
class Solution:

    def Fibonacci(self, n):
        a = 0
        b = 1
        if n == 0:
            return a
        elif n == 1:
            return b
        elif n == 2:
            return 1

        # 循环计算
        for i in range(n - 1):
            # 设置临时变量记录加上之后的值
            c = a + b
            # 更新值
            a = b
            b = c
        return b