关于算法-数据结构:一周刷完剑指offer7斐波那契数列

1. 题目形容

大家都晓得斐波那契数列，前两项相加为第三项的值

如：0, 1, 1, 2, 3, 5, 8, 13……

2. 示例

当初要求输出一个整数n，请你输入斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

3. 解题思路

第一种办法：应用递归的模式

第二种办法：应用非递归的模式，不同与python，【a, b = b, a+b】, java须要应用一个两头变量

4. Java实现

应用递归

public class Solution {
    public int Fibonacci(int n) {
        
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        return (Fibonacci(n-2) + Fibonacci(n-1));
 
    }
}

非递归：

public class Solution {
    public int Fibonacci(int n) {
        
        int a = 0, b = 1;
        int temp;
        for (int i = 0; i < n; i++){
            temp = a;
            a = b;
            b = temp + b;
        }
        
        return a;
 
    }
}

5. Python实现

第一种办法：递归

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

二种办法：非递归

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        a, b = 0, 1
        if n == 0:
            return 0
        for i in range(n):
            a, b = b, a+b 
        return a 

如果您感觉本文有用，请点个“在看”