文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言超详细讲解递归算法汉诺塔

2024-04-02 19:55

关注

题目描述

汉诺塔问题起源于一个传说

汉诺塔又被称为河内塔,传说,在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。 不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。 僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

我们现在要研究的就是在不同情况下盘子的移动顺序和移动的次数。

画图分析

由简到繁,我们先从最简单的情况来分析:

~~只有一个盘子的时候:

只有一个盘子我们直接把它从A柱移到C柱就行,此时移动次数是1,移动顺序是 A->C

~~有两个盘子的时候:

有两个盘子的时候我们需要先将较小的盘子移动到B柱,然后将较大的盘子移动C柱,再将B柱上的盘子移动到C柱;此时移动次数是3,移动顺序是 A->B A->C B->C

~~有三个盘子的时候:

有三个盘子的时侯,我们把最小的盘子命名为1,中间的为2,最大的为3,那么移动顺序应该是:1号移到到C柱,2号移动到B柱,1号移动到B柱,3号移动到C柱,1号移动到A柱,2号移动到C柱,1号移动到C柱;一共移动7次,移动顺序是A->C A->B C->B A->C B->A B->C A->C

A->C A->B C->B

A->C B->A

B->C A->C

思路总结

在上面的移动过程中,B柱始终起着中转的作用,我们我们可以理解为:

同时,我们发现一个盘子时需要移动一次,两个盘子时需要移动3次,3个盘子时需要移动7次,所以总结规律:n个盘子需要移动的次数是 2n-1 次。

其次,我们可以把上面的移动过程简化为三个步骤:

比如,上面盘子个数为三的时候,我们可以分解为:第一步:1号移到到C柱,2号移动到B柱,1号移动到B柱;第二步:3号移动到C柱;第三步:1号移动到A柱,2号移动到C柱,1号移动到C柱。

所以,n个盘子的移动顺序为:

1、把n-1个盘子通过C柱移到B柱上。

2. 把A柱上的最后一个盘子移动到C柱上。

3. 把n-1个盘子通过A柱移动到C柱上。

代码实现

#include<stdio.h>

//Move函数,用来移动盘子,pos1表示起始柱,pos2表示目标柱
void Move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);  //把pos1的盘子移动到pos2
}

//Hanoi函数,用来实现汉诺塔,其中n表示盘子的个数,pos1表示起始柱,pos2表示中转柱,pos3表示目标柱
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (1 == n)  //当n==1时,直接把盘子从A柱移动到C柱
	{
		Move(pos1, pos3);  
	}
	else   //当n不等于1时,分三步走
	{
		//第一步:将n-1个盘子通过C柱移动到B柱,此时C柱时中转柱,B柱是目标柱
		Hanoi(n - 1, pos1, pos3, pos2);
		//第二步:把A柱最后一个盘子直接移动到C柱
		Move(pos1, pos3);
		//第三步:将n-1个盘子通过A柱移动到C柱,此时B柱是起始柱,A柱是中转柱,C柱是目标柱
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	//定义一个变量来表示盘子的个数
	int n = 0;   
	//定义三个字符变量来表示三根柱子
	char pos1 = 'A';
	char pos2 = 'B';
	char pos3 = 'C';
	//调用hanoi函数
	Hanoi(1, pos1, pos2, pos3);  //n为1
	printf("\n");
	Hanoi(2, pos1, pos2, pos3);  //n为2
	printf("\n");
	Hanoi(3, pos1, pos2, pos3);  //n为3
	printf("\n");
	Hanoi(4, pos1, pos2, pos3);  //n为4
	printf("\n");
	return 0;
}

总结

知道了汉诺塔的逻辑后,我们重新回到这个问题,我们发现,要把64片金片全部挪完需要挪动 264-1 次,假设这个僧侣一秒钟移动一次,那么一共要挪 (264-1) / 3600 / 24 / 365 = 584,942,417,355(年),那时候地球已经毁灭也不是没有可能,哈哈。

到此这篇关于C语言超详细讲解递归算法汉诺塔的文章就介绍到这了,更多相关C语言汉诺塔内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯