【C语言】青蛙跳台阶

跳台阶"/>

【C语言】青蛙跳台阶

目录

问题描述

问题分析 

代码展示

举一反三

初级

 代码展示

中级

问题分析

代码展示

• 问题描述

• 问题分析 

如图所示，可以采用逆向思维，跳上第7层台阶前一跳可以有两种跳法。

可以是从6层台阶跳一阶，还可以从5层台阶跳两阶。

同理，跳上第N层台阶前一跳也有两种跳法。

可以是从N-1层台阶跳一阶，还可以从N-2层台阶跳两阶

反推到第一跳，也是同理，要么跳一阶，要么跳两阶。

跳一阶，只有一种跳法。而跳两阶，有两种跳法。

• 代码展示

int Frog_jump(int x){if (x == 1)return 1;//跳一阶，只有一种跳法。if (x == 2)return 2;//跳两阶，有两种跳法。else{return Frog_jump(x - 1) + Frog_jump(x - 2);//跳上第N级台阶有2种跳法,可以是从N - 1级台阶跳一阶//还可以从N - 2级台阶跳两阶}}int main(){int num = 0;printf("请输入青蛙要跳到几层数：\n");scanf("%d", &num);int count = Frog_jump(num);printf("跳到%d层有%d种跳法！\n", num, count);return 0;
}

• 举一反三

• 初级

 如果青蛙可以一次跳上1级，2级，3级台阶，求跳上N级台阶一共有多少种跳法。

•  代码展示

int Frog_jump(int x){if (x == 1)return 1;//跳一阶，只有一种跳法。if (x == 2)return 2;//跳两阶，有两种跳法。if (x == 3)return 4;//跳三阶，有四种跳法。else{return Frog_jump(x - 1) + Frog_jump(x - 2) + Frog_jump(x - 3);//跳上第N级台阶有.种跳法,可以是从N - 1级台阶跳一阶，//可以从N - 2级台阶跳两阶，还可以从N - 3级台阶跳三阶}}

• 中级

 如果青蛙一次可跳1-N级台阶，即从一次只跳一阶台阶到一次跳完所有台阶，求跳到N层有几种跳法。

这里情况发生了一点点变化，变量不在是一共要跳的层数而是青蛙一次能跳的台阶数。所以我们要稍微改变一下思路

• 问题分析

 如图，跳上5层前一跳可以从4层跳一阶，从3层跳两阶，从2层跳三阶，从1层跳四阶，从0层跳五阶，而跳上4层前一跳又有4种可能。

与前面两种情况不同，由于一次可跳的台阶数是可变的，所以要将从0层到N-1层这N种情况都要考虑进来，因此提前算出跳到0层-N-1层的跳法就不现实了。但我们不难发现其中的规律：

跳一阶到1层，跳零阶到0层这两种情况只有一种跳法，而其他层数都可以基于0层或1层向上跳。

其中 f(n-2)+……+f(1)+f(0)  == f(n-1)所以

• 代码展示

int Frog_jump(int x){if (x == 0 || x == 1)return 1;else{return 2*Frog_jump(x - 1);}}