青蛙跳台阶问题【详解】 c语言

1.初级版： ??题目：从前有一只青蛙他想跳台阶，有n级台阶，青蛙一次可以跳1级台阶，也可以跳2级台阶；问：该青蛙跳到第n级台阶一共有多少种跳法。

想法1 ??该想法是基于问题的逻辑和递归分支绘制图的比较来确定到底用那种递归（也就是确定在函数内部调用自身的次数），该方法是完全不了解递归的本质而硬想出来的办法。
??我们都知道若一个函数在自身内部只调用自己1次，画成图的形式你会发现其就相当于一场单一的往返，如下图所示。

文章图片

??而若调用次数高于1次，递归绘成的图就会像分叉的树枝那样节节延伸，如下图所示。
文章图片

??而对于这个青蛙跳台阶问题我们发现青蛙每跳1次都会分为两种不一样情况（即：青蛙要么跳1级要么跳2级只选其一），每次都如此，每次都会分成两条支脉（这不就是上面所说的在自身内部多次递归调用自身的情况嘛！），直至青蛙跳到第n级台阶为止，这样我们就知道应该用递归的方法来做。
??按照上面的想法我们应该编写了一个调用自身次数为2次的递归函数，而既然是递归就必须存在限制条件，防止死递归所导致的栈溢出。结合题意，该限制条件应当是：当青蛙跳到以及跳过第n级台阶时停止递归。那该怎么求出青蛙跳到第n级台阶一共有多少种跳法呢？舍弃那些跳过第n级台阶的情况，统计跳到第n级台阶时情况的次数，不就是在统计一共有多少种跳法嘛。如下图所举例：

文章图片

程序如下：

//从0加到n和从n减到0没啥区别 #include int count = 0; //创建全局变量来统计个跳法个数 void frog(int n) { if (n == 0)//当台阶数为0是跳法个数加1 count++; else if (n < 0); else { frog(n - 1); frog(n - 2); }} int main() { int n; printf("请输入台阶个数："); scanf("%d", &n); frog(n); printf("一共有%d种跳法\n", count); return 0; }

文章图片

想法2 【青蛙跳台阶问题【详解】】??递归的本质是把大事化小，把一个复杂的问题层层转化为一个与原问题相似但规模较小的问题来求解。这句话什么意思呢？举个例子来说明一下：求n的阶乘。假如有一个求阶乘的函数f(x)，那要求n！不就是求f(n)嘛，而这里的 f(n) = n * f(n - 1) （注意这里的 f(n - 1) 表示的是求 (n - 1)! ），而要求 f(n - 1) = (n-1) * f(n - 2) ，然后以此类推下去f(n) = n * (n - 1) * (n - 2) * (n - 3) * ……3 * 2 * f(1) 。那你看我们是不是就把较复杂的问题 f(n) 不断的转化成一个相较于上一次转化更为简单的问题，就这样不断的转化直至转化成问题求 f(1) 的值。

文章图片

??而这里的青蛙跳台阶问题，也可以通过这种思路来求解。你想啊该题想要求的是青蛙从 0 ~ n 级台阶所有跳法的个数，那我们就假设有一个函数 g(x) 可以实现该功能，那 g(n) 所表达的意思就是0 ~ n 级台阶所有跳法的个数（也可以说成是 n ~0 级台阶所有跳法的个数）。我们知道该青蛙每一次只能跳1级台阶或2级台阶，那是不是就意味着若该青蛙此时选择跳1级台阶跳法将与选择跳2级台阶时迥然不同，也就是说 g(n) 是不是就等于 g(n - 1) 和 g(n - 2) 两种情况下跳法的和呀。所以就可以这么一直递归下去，这不是就是大事化小的核心思路呀，直至 g(1) = 1 因为一级台阶只有一种跳法（1）; g(2) = 2 二级台阶只有2种跳法（1，1）、（2）; g(3) = 3 三级台阶只有3种情况（1，1，1）、（1，2）、（2，1）。你会惊讶的发现这不就是斐波那契数列嘛，所以青蛙跳平台问题的本质就是斐波那契额数列的运算。

#include //求第n级台阶时青蛙跳法个数 int frog_jump_step(int n) { //特殊情况处理 if (n == 1) { return 1; } if (n == 2) { return 2; } //递归调用 return frog_jump_step(n - 1) + frog_jump_step(n - 2); } int main() { int n = 0; printf("请输入青蛙所要跳的台阶数："); scnaf("%d", &n); int num = frog_jump_step(n); printf("一共有%d种跳法\n", num); return 0; }

文章图片

2.进阶版： ??题目：从前有一只青蛙想跳台阶去等峰，若该青蛙一次可以跳上1级台阶、也可以跳上2级……（n-1）级、n级。那么该青蛙跳上第n级的台阶时总共有多少种跳法。（前提是n个台阶会有一次n阶的跳法）

解题思路若n为1级台阶：f(1) = 1 (只可能有一种跳法)
若n为2级台阶：f(2) = f(2 - 1) + f(2 - 2)（会有两个跳得方式，一次1阶或者一次2阶）
若n为3级台阶：f(3) = f(3 - 1) + f(3 - 2) + f(3 - 3)（会有三种跳得方式，一次1阶、2阶、3阶）
……
……
若n为(n - 1)级台阶：

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

若n为n级台阶：

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

结合f(n-1)和f(n)的情况你会发现f(n) = f(n-1) + f(n-1)，所以可得： f(n) = 2*f(n-1)。

#include int frog_jump_step(int n) { if (n < 0) { printf("n can't be less than 0\n"); } if (n <= 1) { return 1; } return 2 * frog_jump_step(n - 1); } int main() { int n = 0; printf("请输入青蛙该跳的台阶数："); scanf("%d", &n); int num = frog_jump_step(n); printf("一共有种%d种跳法\n", num); return 0; }