递归解决青蛙跳台阶问题(斐波那契数列)
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？
答题思路 如果只有1级台阶，那只有一种跳法 如果有2级台阶，那么就有2种跳法，一种是分2次跳。每次跳1级，另一种就是一次跳2级 如果台阶级数大于2，设为n的话，这时我们把n级台阶时的跳法看成n的函数，记为,第一次跳的时候有2种不同的选择：一是第一次跳一级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为,二是第一次跳二级，此时跳法的数目等于后面剩下的n-2级台阶的跳法数目，即为,因此n级台阶的不同跳法的总数为，就可以看出是斐波那契数列 数学函数表示如下
#include<stdio.h>
int ways(int n)
{
if (n<=1)
{
return 1;
}
else
{
return ways(n-2) + ways(n - 1);
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d
", ways(n));
return 0;
}
若把条件修改成一次可以跳一级，也可以跳2级也可以跳3级…也可以跳上n级呢？
思路 如果台阶级数为n的话，这时我们把n级台阶时的跳法看成n的函数，记为f(n),第一次跳的时候有n种不同的选择：若是第一次跳一级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1),若是第一次跳m(m<n)级，此时跳法的数目等于后面剩下的n-m级台阶的跳法数目，即为f(n-m),若是第一次跳n级，此时跳法的数目等于1.所以 f(n)=f(n-1)+f(n-2)+…f(n-m)+…+f(2)+f(1)+1 因此f(n-1)=f(n-2)+…+f(n-m)+…f(2)+f(1)+1 两式相减得到 f(n)=2*f(n-1) 因此可以得到下面的结果
答案 若把条件修改成一次可以跳一级，也可以跳2级…也可以跳上n级呢，则
