资讯专栏INFORMATION COLUMN

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

villainhr / 3279人阅读

摘要:由此可知在前柱是中转柱在之后也有两种情况只有上有圆盘。并且我们的游戏目标从一开始的把上所有圆盘移到柱变成了把上所有圆盘移到柱上而在这时中转柱是柱。现在将步骤分为三个小步骤将上个圆盘全部移到柱上中转柱柱。

一.汉诺塔问题

  汉诺塔是一种古印度游戏,该游戏的实质就是在一块木板上有三根固定的柱子

而在左边的柱子上有着n个大小不同的圆盘,我们需要做就是把左边所有的盘子全部移到右边的柱子上。操作规则:1.圆盘在柱子上必须按照从大到小(大圆盘在下)依次排列。2.每次只能移动圆柱最上面的圆盘。

问题分析:先假设三根柱子分别为“A”"B""C",A柱有着所有的初始盘,我们的目的就是把A柱上的所有盘子全部移到C柱上。

n=1时,直接把圆盘从A柱移动到C柱就可。

n=2时,A-->B,A-->C,B-->C。(在这操作中B为中转柱)

n=3时,A-->C,A-->B,C-->B,①A-->C,B-->A,B-->C,A-->C。对n=3这种情况进行分析:在①之前圆盘所在圆柱的情况有两种:

1.是所有圆盘在A,B,C三个圆柱中都有一个圆盘。

2.是A,C上有圆盘而B上没有圆盘。

由此可知在①前B柱是中转柱;在①之后也有两种情况:

1.只有B,C上有圆盘。

2.A,B,C上都有一个圆盘。

并且我们的游戏目标从一开始的把A上所有圆盘移到C柱(A-->C),变成了把B上所有圆盘移到C柱上(B-->C),而在这时中转柱是A柱。

......

直到A上有n个圆盘时,现在对n这种情况进行分析:想要把n个圆盘从A柱移到C柱上有三大步骤:

①将A上n-1个圆柱全部移到C柱上(中转柱B柱)。

②将A上的一个圆盘移到C柱上。

③将B上n-1个圆盘全部移到C柱上(中转柱A柱)。

在这要穿插一下递归的主要思想就是大事化小。现在将①步骤分为三个小步骤:

①将A上n-2个圆盘全部移到C柱上(中转柱B柱)。

②将A上第n-1个圆盘移到B柱上。

③将C上n-2个圆盘移到A柱上(中转柱A柱)。

然后将第二个①化为更小的三个步骤......就这样一步步大事化小。

代码实现:

#includevoid hanoi(int n, char post_1, char post_2, char post_3){    if (n == 1)    {        printf("%c --> %c/n", post_1, post_3);    }    else    {        hanoi(n - 1, post_1, post_3, post_2);        printf("%c --> %c/n", post_1, post_3);        hanoi(n - 1, post_2, post_1, post_3);    }}int main(){    int n = 0;    char a = "A", b = "B", c = "C";    scanf("%d", &n);    hanoi(n, a, b, c);    return 0;}

 二.青蛙跳台阶问题

  一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级台阶有多少种跳法?(实质就是斐波那契数列的变种)

问题分析:

我们不妨列举一下n比较少的情况时的跳法:

①n=1时,1种跳法。          ②n=2时,有2种跳法。

③n=3时,有3种跳法。      ④n=4时,有5种跳法。

⑤n=5时,有8种跳法。

......

很明显,同过观察上面列举的情况可以发现:

n=3时所有的跳法等于n=1时和n=2时的所有跳法之和;

n=4时的所有跳法等于n=2和n=3时的所有跳法之和;

......

以此类推可以得出f(n)=f(n-1)+f(n-2) (n>2)。(f(n)为跳法数量)

 

代码实现:

#includeint frogjump(int n){	if (n == 1)	{		return 1;	}	else if (n == 2)	{		return 2;	}	else	{		return frogjump(n - 1) + frogjump(n - 2);	}}int main(){	int n = 0;	scanf("%d", &n);	printf("%d", frogjump(n));	return 0;}

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

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

相关文章

  • 看动画轻松理解「递归「动态规划」

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

    cnio 评论0 收藏0
  • 数据结构算法之汉诺问题(Java递归

    摘要:汉诺塔问题有三根柱子,源杆,暂存杆,目的杆上有层盘子,由小到大向下排列,现需要将杆的盘子移到杆中要求大的盘在下面,小的盘在上面一次只能移动一个盘子个人思路先分析问题,用数学的归纳法当只有一个盘时,直接移动当有两个盘时,先将小的移到暂存杆,再 汉诺塔问题: 有三根柱子,源杆A,暂存杆temp,目的杆C A上有n层盘子,由小到大向下排列,现需要将A杆的盘子移到C杆中 ...

    yuxue 评论0 收藏0
  • 一个小青蛙,可以一次两节楼梯,也可以一次一节楼梯,请问他如果要101节楼梯,一共有几种法方案

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

    fsmStudy 评论0 收藏0
  • 经典算法:汉诺

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

    Lin_R 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<