C语言实现汉诺塔问题

2019年12月02日 561点热度 6人点赞 0条评论

问题描述:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

下面我们来用递归的思想考虑一下,递归首先要考虑最后一次运算,假设要移四个圆盘从A到C上,(下面为了方便我们用一个“|”表示“借助”,用->表示移动,例如“A|B->C 4”表示A借助B移动四个圆盘到C先不考虑它如何移动只表示借助B能够将4个圆盘移动到C ):

要实现A|B->C 4;

需A|C->B 3再 A->C 1 再B|A->C 3;①

①中要实现A|C->B 3

需A|B->C 2 再A->B 1再 C|A->B 2;②

①中要实现B|A->C 3

需B|C->A 2 再B->C 1 再A|B->C 2;③

.

.

.

一个大问题变成三个相同的小问题,其中一个可以直接得出结果不可再分,另外两个分别又可以分出三个小问题  直到最后都变成不可再分的基本问题,这种就可以通过递归的方式实现.

所以我们得到了递归终止条件,就是移动圆片的个数为1。下面就是它的C语言实现


#include<stdio.h>
#pragma warning(disable : 4996)
int move(int number, char fromPole, char thoughPole, char toPole);
int main()
{
	int disk;
	printf("输入移动的圆盘数量:\n");
	scanf("%d", &disk);
	printf("%d",move(disk, 'a', 'b', 'c'));
}
int move(int number, char fromPole, char thoughPole, char toPole)
{
	static int i=0;
	if (number <= 1)
	{
		printf("%c->%c\n",fromPole,toPole);
		i++;
		return i;
	}
	else
	{
		move(number-1,fromPole,toPole,thoughPole);
		move(1, fromPole, thoughPole,toPole);
		move(number - 1, thoughPole, fromPole,toPole);
	}
}

Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论