本文共 2558 字，大约阅读时间需要 8 分钟。

青蛙跳台阶问题是一道很经典的问题：

（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。 （2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？ （3）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级（青蛙一次最多跳的台阶数由用户指定），此时该青蛙跳上一个n级的台阶总共有多少种跳法？

首先先研究一下第一个问题：

一共1个台阶   f(1) = 1   只有一种跳法

一共2个台阶   f(2) = 2    有两种跳法 一共3个台阶   f(3) = 3 = f(3-1)+f(3-2)  其中f(3-1)表示第一次跳1个台阶的跳法；f(3-2)表示第一次跳2个台阶的跳法 一共4个台阶   f(4) = 5 = f(4-1)+f(4-2)  其中f(4-1)表示第一次跳1个台阶的跳法；f(4-2)表示第一次跳2个台阶的跳法 …… 实际上这就是一个递归问题，有没有发现，这就是一个类似于斐波那契数列的问题

代码如下：

#include 
   
        int jump_floor(int n)    {        if (1 == n)        {            return 1;        }        else if (2 == n)        {            return 2;        }        else        {            return jump_floor(n - 1) + jump_floor(n - 2);        }    }    int main()    {        int n = 0;        scanf("%d", &n);        int ret = jump_floor(n);        printf("%d\n", ret);        return 0;    }
   

对于第二个问题，实际上是第一个问题的延伸：

一共1个台阶   f(1) = 1   只有一种跳法

一共2个台阶   f(2) = f(2-1)+f(2-2)    其中f(2-1)表示第一次跳1个台阶的跳法；f(2-2)表示第一次跳2个台阶的跳法 一共3个台阶  f(3) = 3 = f(3-1)+f(3-2)+f(3-3)  其中f(3-1)表示第一次跳1个台阶的跳法；f(3-2)表示第一次跳2个台阶的跳法;f(3-3)表示第一次跳3个台阶的跳法 一共4个台阶   f(4) = 5 = f(4-1)+f(4-2)  其中f(4-1)表示第一次跳1个台阶的跳法；f(4-2)表示第一次跳2个台阶的跳法；f(4-3)表示第一次跳3个台阶的跳法;f(4-4)表示第一次跳4个台阶的跳法 …… 由上述，设定f(0) = 1

代码如下：

#include 
   
        int jump_floor(int n)    {        int sum = 0;        if (n <= 1)        {            return 1;        }        else        {            for (int i = 1; i <= n; i++)            {                sum += jump_floor(n - i);            }            return sum;        }    }    int main()    {        int n = 0;        scanf("%d", &n);        int ret = jump_floor(n);        printf("%d\n", ret);        return 0;    }
   

但上述方法并没有运用公式：

我们知道： f(n)=f(n-1)+f(n-2)+f(n-2)+…+f(n-(n-1))+f(n-n) 也就可以表示为：

f(n)=f(0)+f(1)+f(2)+…+f(n-2)+f(n-1)

而：

f(n-1)=f(0)+f(1)+f(2)+…+f(n-2)

可以得出：f(n)=f(n-1)+f(n-1)=2*f(n-1)

代码如下：

递归：

#include 
   
        int jump_floor(int n)    {        if (n < 2)        {            return 1;        }        else        {            return 2 * jump_floor(n - 1);        }    }    int main()    {        int n = 0;        scanf("%d", &n);        int ret = jump_floor(n);        printf("%d\n", ret);        system("pause");        return 0;    }
   

非递归：

#include 
   
        int jump_floor(int n)    {        return (int)pow(2, n - 1);    }    int main()    {        int n = 0;        scanf("%d", &n);        int ret = jump_floor(n);        printf("%d\n", ret);        system("pause");        return 0;    }
   

对于第三个问题：

只要理解了第二个问题的第一种方法（不用公式）就更简单了，只需要将for循环的次数改为青蛙一次可以跳的最大台阶数就可以了