前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >汉诺塔问题详解

汉诺塔问题详解

作者头像
RAIN7
发布2021-08-11 16:24:50
5980
发布2021-08-11 16:24:50
举报

1. 汉诺塔来源及应用

   相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。

  游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

在这里插入图片描述
在这里插入图片描述

2. 汉诺塔游戏规则

 有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

(1)每次只能移动一个圆盘; (2)大盘不能叠在小盘上面。

3. 汉诺塔算法分析

算法分析: n为圆盘的数量,A,B,C为所给的柱子 当n=1,只需把盘子移动a–>c即可 move(A,C); 当n>1时,

第一次移动,要把A柱子上的前n-1个移动到B柱子上;(图1) hanoi(n-1,A,C,B);

在这里插入图片描述
在这里插入图片描述

第二次移动,直接把A柱子上的最后一个移动到C柱子上;(图2) move(A,C);

在这里插入图片描述
在这里插入图片描述

第三次移动,把B柱子上的n-1个柱子通过柱子A移动到柱子C上。(图3) hanoi(n-1,B,A,C);

在这里插入图片描述
在这里插入图片描述

算法总述:

在这里插入图片描述
在这里插入图片描述

hanoi函数的实现:

在这里插入图片描述
在这里插入图片描述

move函数的实现//打印移动的轨迹:

代码语言:javascript
复制
void move(char c1, char c2)  //move函数打印出移动的轨迹
{
	printf("%c-->%c\n", c1, c2);	
}

4. c语言代码实现

代码语言:javascript
复制
#include  

//汉诺塔问题

void move(char c1, char c2)  //move函数打印出移动的轨迹
{
	printf("%c-->%c\n", c1, c2);	
}

void hanoi(int n, char x, char y, char z)
{
	if (n == 1)   //递归的截止条件
	    move(x, z);
	else
	{
		hanoi(n - 1, x, z, y);  //将n-1个盘子从x柱借助z柱移动到y柱上去
		move(x, z);   将x柱上剩下的一个盘移动到z柱上
		hanoi(n - 1, y, x, z);  //将n-1个盘从y柱借助x柱移动到z柱上
	}
}

int main()
{
	int n = 0;
	printf("请输入初始的圆盘数:");
	scanf("%d",&n);
	hanoi(n, 'A', 'B','C');
	return 0;
}

谢谢欣赏!!!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-02-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 汉诺塔来源及应用
  • 2. 汉诺塔游戏规则
  • 3. 汉诺塔算法分析
  • 4. c语言代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档