青蛙跳台阶问题|经典青蛙跳台阶问题与汉诺塔问题青蛙跳台阶问题|c语言

一只青蛙可以一次跳一个台阶，也可以一次跳两个台阶。
问青蛙跳到第n个台阶有多少种方法。
【青蛙跳台阶问题|经典青蛙跳台阶问题与汉诺塔问题】青蛙跳到第一个台阶的方法有【1】——1种
青蛙跳到第二个台阶的方法有【1，1】【2】——2种
青蛙跳到第三个台阶的方法有【1，1，1】【1，2】【2，1】——3种
青蛙跳到第四个台阶的方法有【1，1，1，1】【1，1，2】【1，2，1】【2，1，1】【2，2】5种
青蛙跳到第五个台阶的方法有【1，1，1，1，1】【1，1，1，2】【1，1，2，1】【1，2，1，1】【2，1，1，1】【2，2，1】【1，2，1】【2，1，2】——8种
.......
{(1),1,2,3,5,8,13,21,34,55........n}
联想斐波那契数列
不难得出青蛙跳到第n个台阶的方法就是斐波那契数列的第n+1项值
那我们写一个斐波那契数列的代码

#include int Fib(int n)//采用递归的方式查找斐波那契数列的第n项 { int ret = 0; if(n<=2) return 1; if(n>2) ret = Fib(n-1) + Fib(n-2); return ret; } int main() { int n = 0; int ret = 0; scanf("%d",&n); ret = Fib(n); printf("青蛙的方法有 %d种",ret); return 0; }

请分别查找第5项，第9项，第50项.

结果是：第5项，第9项都能成功查找。但是第50项却崩溃了。
不妨在n==3处设置每当n==3，记录一次
试试以下代码

#include int count = 0; //这里用count计算一下次数 int Fib(int n) { if(n==3) count++; int ret = 0; if(n<=2) return 1; if(n>2) ret = Fib(n-1) + Fib(n-2); return ret; } int main() { int n = 0; int ret = 0; scanf("%d",&n); ret = Fib(n); printf("青蛙的方法有 %d种\n",ret); printf("n==3一共计算了%d次\n",count); //并将其打印出来 return 0; }

当我们找n=40时可见n==3重复了390w次
当我们用递归的时候，n项需要找n-1，n-2.
n-1需要找n-2，n-3.n-2需要找n-3，n-4
则n项将n==3重复了n^(n-2)次
如果我们采用递归的方法查询则效率过低。
这时候可以采用循环递推

#include int Fib(int n) { int a = 1; int b = 1; int c = 1; //当n取1，2时不符合我们的循环判断，c取1正好作为n=1,n=2的return值 int i = 0; for (i=n; i>2; i--) { c = a + b; a = b; b = c; } return c; }int main() { int n = 0; int ret = 0; scanf("%d",&n); ret = Fib(n); printf("%d\n",ret); return 0; }

青蛙种类数列与斐波那契数列的差别就是后者首位多一项1，所以青蛙n项种数为斐波那契数列的n项加1.