Python算法学习一：斐波那契数列(兔子问题)_兔子数列python

斐波那契数列算法

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
简单的理解就是从第三项开始每一项都是前两项之和。
f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)

例题：剑指offer斐波那契数列

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

方法一

递归实现

def Fibonacci(self, n):
        #递归实现
        # n=0 f(0)=0
        if n==0:
            return 0
        # n=1 f(1)=1
        if n==1:
            return 1
        #if n>1  f(n)=f(n-1)+f(n-2)
        if n>1:
            num=self.Fibonacci(n-1)+self.Fibonacci(n-2)
            return num
        
        return None
        '''
        这种方法简单易理解，但是不推荐，运行时间较长
        '''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二

循环语句

def Fibonacci(self, n):		
		# n=0 f(0)=0
        if n==0:
            return 0
        # n=1 f(1)=1
        if n==1:
            return 1
        #if n>1  f(n)=f(n-1)+f(n-2)
        a=1
        b=0
        #if n>1  f(n)=f(n-1)+f(n-2)
        #h=a+b
        #当 n=2 h=0+1
        
        for i in range(0,n-1):
            ret=a+b
            b=a 
            a=ret 
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下面为循环过程

每天进步一点点。