[数据结构与算法]2021-09-26

算法每日一练

06 青蛙跳（斐波那契数列）

那么这个问题简化到了青蛙跳台阶，一次只能跳一阶，或跳两阶，问n阶台阶，可以有多少种跳法。我们正序推理，那么可以借助一个二叉树，分支到n的一个分支即为一种跳法。正序推理易于理解，但是实现不能适合通用情况（不信可以去试试），hhh。
那么我们逆着想一想哈，f(n)为n阶的跳法，f（n-1）到f（n）这种跳法数等于f(n-1)本身，同理，f（n-2）到f（n）这种跳法数等于f（n-1）本身，所以f（n）=f(n-1)+f（n-2）
所以逆着推理，到f（2）=2，f（1）=1；那么就能求出f（n）。把n取0,1，2,3，4，…n
我们会得到这样一串数列0、1、1、2、3、5、8、13、21、34、……。这就是菲波那切数列。link
阅读百科之后， 你会发现这还跟黄金分割，杨辉三角有关系，数学真是太神奇了！！！！

// #include <iostream>
using namespace std;
	int n;
int fun(int n){
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        else
            return fun(n-2)+fun(n-1);
    }
int main(){
    cin>>n;
    int res=0;
    res=fun(n);
    cout<<res;
	return 0;
}