经典青蛙跳台阶问题与汉诺塔问题

Scott 发布于2021-10-11 10:58 / 2950人阅读

摘要：问青蛙跳到第个台阶有多少种方法。但是第项却崩溃了。这时候可以采用循环递推当取，时不符合我们的循环判断，取正好作为的值青蛙种类数列与斐波那契数列的差别就是后者首位多一项，所以青蛙项种数为斐波那契数列的项加

一只青蛙可以一次跳一个台阶，也可以一次跳两个台阶。

问青蛙跳到第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.

私有云超融合服务器汉诺塔汉诺塔 python 汉诺塔c语言讲解简单汉诺塔c语言算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122144.html

用C程序解决汉诺塔问题与青蛙跳台阶问题（递归）

摘要：由此可知在前柱是中转柱在之后也有两种情况只有上有圆盘。并且我们的游戏目标从一开始的把上所有圆盘移到柱变成了把上所有圆盘移到柱上而在这时中转柱是柱。现在将步骤分为三个小步骤将上个圆盘全部移到柱上中转柱柱。一.汉诺塔问题汉诺塔是一种古印度游戏，该游戏的实质就是在一块木板上有三根固定的柱子...

villainhr 2021-11-11 16:55 评论0 收藏0
看动画轻松理解「递归」与「动态规划」

摘要：程序员小吴打算使用动画的形式来帮助理解递归，然后通过递归的概念延伸至理解动态规划算法思想。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。难点就在于找出动态规划中的这三个概念。在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。...

cnio 2019-07-30 18:41 评论0 收藏0
经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

Lin_R 2019-07-31 11:17 评论0 收藏0
经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

AWang 2019-08-23 12:40 评论0 收藏0
一个小青蛙,可以一次跳两节楼梯,也可以一次跳一节楼梯,请问他如果要跳101节楼梯,一共有几种跳法方案

摘要：一个小青蛙可以一次跳两节楼梯也可以一次跳一节楼梯请问他如果要跳节楼梯一共有几种跳法方案问题的描述很简单看到这个题目的时候我首先想到的就是举例分析一波比如当的时候有几种方案当的时候有几种方案等等我们首先分析一波当的时候这个时候小青蛙只有一种跳一个小青蛙,可以一次跳两节楼梯,也可以一次跳一节楼梯,请问他如果要跳101节楼梯,一共有几种跳法方案? 问题的描述很简单,看到这个题目的时候,我首...

fsmStudy 2019-08-22 15:20 评论0 收藏0