Python解决斐波那契数列问题

• 题目
• 思路1
• 代码1
• 思路2
• 代码2

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，即当n=1或2时，fib(1)=fib(2)=1，当n>2时，fib(n)=fib(n-1)+fib(n-2)。

示例1
输入：4
返回值：3

示例2
输入：2
返回值：1

首先提到斐波那契数列我就想到了迭代问题，然后我就想用迭代解决这个问题了。只要注意好迭代时的界线问题就好。

def Fibonacci(n: int) -> int:
    if (n<=0):
        return 0
    elif (n<=2):
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)

但是迭代就面临了一个尴尬的问题，数小的话可以算，但是假如数是39的话，会运行超时。如果能解决运行超时的问题的话，这将会是一个不错的解题思路。

既然我们学不明白的迭代不行，我就想的是用基础的循环来做。循环一般不会出现严重的超时问题，所以代码如下。

def Fibonacci(n: int) -> int:
    pre=0
    prepre=1
    if (n<=0):
        return 0
    for i in range(0,n):
        prepre,pre=pre,prepre+pre
    return pre

做到这我只能说python很神奇，好好学吧！