初级算入门_斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

代码:

class Solution {
    public int fib(int n) {
        if(n==0||n==1) return n;
        int temp=0,t0=0,t1=1;
        for(int i=2;i<=n;i++){
            temp=t0+t1;
            t0=t1;
            t1=temp;
        }
        return temp;
    }
}

思路:

乍一看题目我是蒙的,但仔细思考规律之后就发现很简单

斐波那契数列是这样的

0 1 2 3 5 8

也就是

0+1=2

1+2=3

2+3=5

3+5=8

生成的数字是前两项之和

那么这样看下去我们很容易发现规律

     t0  t1 
数列 0   1   2   3   5   8  13
下标 0   1   2   3   4   5  6

这样我们只需要改变t0和t1的记录值就可以了t0=t1,t1=temp的值就可以算出生成的新temp了

代码:

class Solution {
    public int fib(int n) {
        if(n==0||n==1){
            return n;
        }else{
            return fib(n-1)+fib(n-2);
        }

    }
}

思路:

用递归的方式解决问题,自己调用自己就可以了……

设n=2就会走else然后fib(1)+fib(0)=2

n=3 fib(2)+fib(1)=3

以此类推……