青蛙为什么要跳台阶，C语言趣解青蛙跳台阶问题
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？
解题思路
1.当n=1的时，很明显青蛙只有一种跳法。
2.当n=2时，青蛙有两种选择，一是每次跳1级台阶，跳两次，二是直接跳两级台阶，一步到位。所以，一共有两种跳法。
3.当n>2时，我们不妨把上n级台阶的跳法记为一个函数f(n)，青蛙在第一次跳的时候有两个选择，即跳一级台阶或跳两级台阶。当青蛙选择第一次跳一级台阶时，跳完后还剩n-1级台阶，在此情况下，跳法的数目为f(n-1)；当青蛙选择第一次跳两级台阶时，跳完后还剩n-2级台阶，在此情况下，跳法数目为f(n-2)。所以，我们可以推出青蛙跳n级台阶的跳法总数为f(n)=f(n-1)+f(n-2)。
到这里我们就能使用求斐波拉契数列的方法来求青蛙跳n级台阶的跳法。
若把条件修改成一次可以跳一级，也可以跳2级…也可以跳上n级呢？
解题思路
尽管条件改成每次跳的台阶级数不受限，但是换汤不换药，思考的方法是一样的。
1.当n=1或n=2时，青蛙跳台阶跳法次数和没修改条件时是一样的，n=1有一种跳法，n=2有两种跳法。
2.当n>2时，同理我们将青蛙跳n级台阶时的跳法记成函数f(n)。但是青蛙在第一次的选择不仅仅是跳1级和跳2级，它还可以选择跳3,4,5,…,n级。所以青蛙跳一次后还会剩n-1，n-2，n-3，…，2, 1, 0级台阶。
此时，f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(2)+f(1)+1
同理，f(n-1)=f(n-2)+f(n-3)+f(n-4)+…+f(2)+f(1)+1
合并上面两个式子得，f(n)=2*f(n-1)
3.根据2的推论我们还可以进一步推导：
根据上面所推导出的结论，就能破解这个问题，写出代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//青蛙每次跳台阶数为1或2
// f(n)=f(n-1)+f(n-2)
//f(1)=1 f(2)=2
int frog_step1(int x);//递归
int frog_step2(int x);//非递归
//青蛙每次跳台阶数为任意值
//f(n-1)=f(n-2)+f(n-3)+...+f(1)
//f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)=2*f(n-1)
int rfrog_step1(int x);//递归
int rfrog_step2(int x);//非递归
int main()
{
int n = 0;
int cnt1 = 0;
int cnt2 = 0;
int cnt3 = 0;
int cnt4 = 0;
scanf("%d", &n);
cnt1 = frog_step1(n);
cnt2 = frog_step2(n);
cnt3 = rfrog_step1(n);
cnt4 = rfrog_step2(n);
printf("青蛙跳%d级台阶一共有%d种跳法。\n", n, cnt1);
printf("青蛙跳%d级台阶一共有%d种跳法。\n", n, cnt2);
printf("青蛙跳%d级台阶一共有%d种跳法。\n", n, cnt3);
printf("青蛙跳%d级台阶一共有%d种跳法。\n", n, cnt4);
return 0;
}
//青蛙每次跳台阶数为1或2
// f(n)=f(n-1)+f(n-2)
//f(1)=1 f(2)=2
int frog_step1(int x)//递归
{
if (x > 2)
return frog_step1(x - 1) + frog_step1(x - 2);
else if (x == 2)
return 2;
else if (x == 1)
return 1;
else
return 0;
}
int frog_step2(int x)//非递归
{
int a = 1;
int b = 2;
int ret = 1;
if (x == 1 || x == 2 )
ret = x;
while (x > 2)
{
ret = a + b;
a = b;
b = ret;
x--;
}
if (x > 0)
return ret;
else
return 0;
}
//青蛙每次跳台阶数为任意值
//f(n-1)=f(n-2)+f(n-3)+...+f(1)
//f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)=2*f(n-1)
int rfrog_step1(int x)//递归
{
if (x > 1)
return 2 * rfrog_step1(x - 1);
else if (x == 1)
return 1;
else
return 0;
}
int rfrog_step2(int x)//非递归
{
int a = 1;
int ret = 1;
while (x > 1)
{
ret = 2 * a;
a = ret;
x--;
}
if (x > 0)
return ret;
else
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）