问题描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

分析

n - 台阶数

sum - 跳发

可参考斐波那数

递归实现

//1 2 3 5 8 13 21 34 55 89 ……
//递归实现
int D_Frog_jump(int n)
{

    if (n <3)
        return n;
    else
        return D_Frog_jump(n - 1) + D_Frog_jump(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;
    printf("请输入青蛙要跳的台阶数：");
    scanf("%d", &n);
    ret = D_Frog_jump(n);
    //ret = FD_Frog_jump(n);
    printf("%d\n", ret);
    return 0;
}

非递归实现

//非递归实现
int FD_Frog_jump(int n)
{
    int res = 2;
    int pre_res = 1;
    int next_older_res = 0;
    while (n > 2)
    {
        next_older_res = pre_res;
        pre_res = res;
        res = pre_res + next_older_res;
        n--;
    }
    return res;
}