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

public class Solution {
    public int Fibonacci(int n) {
        //斐波那契 f(n) = f(n-1) + f(n-2)
        if(n==0 || n==1){
            return n;
        }
        int i = 1, f1=0,f2=1,sum=0;
        while(i<n){
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
            i++;
        }
        return sum;
    }
}

Python版

class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:
            return 0
        if n == 1:
            return 1
        a0=0;a1=1
        for i in range(2,n+1):
            sum = a0 + a1
            a0 = a1
            a1 = sum
        return sum