首先考虑最简单的情景
青蛙一次可跳一个或两个台阶 台阶总数用N表示
当N=1时,
此时只有一种跳法,只能跳一个台阶
当N=2时,
此时有两种跳法,一次跳两个台阶或者跳两次一个台阶
当N=3时,
1.先跳一个台阶,接下来就是N=2的跳法;
2.先跳两个台阶,接下来就是N=1的跳法。
跳法总数:(N=1)+(N=2)
当N=4时,
1.先跳一个台阶,接着就是N=3的跳法;
2.先跳两个台阶,接着就是N=2的跳法
跳法总数:(N=3)+(N=2)
…
…
…
以此类推
当N=n时,
1.先跳一个台阶,接着就是N=n-1的跳法;
2.先跳两个台阶,接着就是N=n-2的跳法
跳法总数:(N=n-1)+(N=n-2)
#include<stdio.h> int my_jumpsteps(int n) { //先进行台阶数的判断 if (1 == n) { return 1; } if (2 == n) { return 2; } if (n > 2) { //进行递归 return my_jumpsteps(n - 1) + my_jumpsteps(n - 2); } } int main() { //台阶总数 int n = 0; scanf("%d", &n); //调用函数 int ret = my_jumpsteps(n); printf("%d\n", ret); return 0; }
情景变得复杂一些时,青蛙一次可跳三个台阶时
当N=1时,
此时只有一种跳法,只能跳一个台阶
当N=2时,
此时有两种跳法,一次跳两个台阶或者跳两次一个台阶。
跳法总数:2
当N=3时,
1.先跳一个台阶,接下来就是N=2的跳法;
2.先跳两个台阶,接下来就是N=1的跳法;
3.可一次跳三个台阶
跳法总数:(N=2)+(N=1) + 1=4
当N=4时,
1.先跳一个台阶,接着就是N=3的跳法;
2.先跳两个台阶,接着就是N=2的跳法;
3.先跳三个台阶,接着就是N=1的跳法;
跳法总数:(N=3)+(N=2)+(N=1)
当N=5时
1.先跳一个台阶,接着就是N=4的跳法;
2.先跳两个台阶,接着就是N=3的跳法;
3.先跳三个台阶,接着就是N=2的跳法;
跳法总数:(N=4)+(N=3)+(N=2);
…
…
…
以此类推
当N=n时
1.先跳一个台阶,接着就是N=n-1的跳法;
2.先跳两个台阶,接着就是N=n-2的跳法;
3.先跳三个台阶,接着就是N=n-3的跳法;
跳法总数:(N=n-1)+(N=n-2)+(N=n-3)
#include<stdio.h> int my_jumpsteps(int n) { //先进行台阶数的判断 if (1 == n) { return 1; } if (2 == n) { return 2; } if (3 == n) { return 4; } if (n > 3) { //进行递归 return my_jumpsteps(n - 1) + my_jumpsteps(n - 2) + my_jumpsteps(n - 3); } } int main() { //台阶总数 int n = 0; scanf("%d", &n); //调用函数 int ret = my_jumpsteps(n); printf("%d\n", ret); return 0; }
情景更加复杂时
青蛙一次可跳m个台阶
当N=1时,
此时只有一种跳法,只能跳一个台阶
当N=2时,
此时有两种跳法,一次跳两个台阶或者跳两次一个台阶。
跳法总数:2
当N=3时,
1.先跳一个台阶,接下来就是N=2的跳法;
2.先跳两个台阶,接下来就是N=1的跳法;
3.可一次跳三个台阶
跳法总数:(N=2)+(N=1) + 1=4
当N=4时,
1.先跳一个台阶,接着就是N=3的跳法;
2.先跳两个台阶,接着就是N=2的跳法;
3.先跳三个台阶,接着就是N=1的跳法;
4.可一次跳四个台阶
跳法总数:(N=3)+(N=2)+(N=1)+1
…
…
…
当N=m+1时
跳法总数:(N=m)+(N=m-1)…+(N=1)
…
…
…
当N=n时
跳法总数:(N=n-1)+(N=n-2)+…+(N=n-m)
#include<stdio.h> int my_jumpsteps(int n) { //先进行台阶数的判断 if (1 == n) { return 1; } if (2 == n) { return 2; } ....... if (n > k) { //进行递归 return my_jumpsteps(n - 1) + my_jumpsteps(n - 2) + my_jumpsteps(n - 3) + .... + my_jumpsteps(n - k); } } int main() { //台阶总数 int n = 0; scanf("%d", &n); //调用函数 int ret = my_jumpsteps(n); printf("%d\n", ret); return 0; }