亲宝软件园·资讯

展开

C语言汉诺塔

蔡欣致 人气:3

汉诺塔(Hanoi)是什么?

一个简单的汉诺塔就如上图所示,有三个放置点,放置物必须遵循上小下大的规则,依次将1中的放置物全部放置到3中。就比如该图中有4个放置物,若将A上的放置物全部移至C上,具体的步骤是:A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C。

那么,C语言如何实现汉诺塔呢?

第一步要先确定起始位置、中转位置、目的位置,在一开始A是起始位置,B是中转位置,C是目的位置,在后续移动物块的时候会一直改变这三个位置的功能,以达到最终目标。

汉诺塔的基本思路是:

第一阶段:将n-1个物块(也就是除最底部的物块外)经过一系列地堆放(这里就可以使用到递归的方法来实现),最后放置到中转位置上,然后把起始位置剩下的物块放到目的位置上,如下图:

 以上一系列地堆放是指:以A为起始位置,C为中转位置,B为目的位置,也就相当于把C看作是一个中间存放点,来帮助这n-1个物块放到B里面去。

第二阶段:然后会发现,变化后的汉诺塔的形式也和之前是差不多的,如果把B看作是起始位置,A是中转位置,C是目的位置。就可以一直按照上面的那个方法一直递归下去,如下图:

以此类推……最后就能实现把所有的物块全部从A搬到C。

具体代码见下(注意点在代码下面):

//C语言实现汉诺塔
#include <stdio.h>
 
void move(char p1, char p2)
{
	printf("%c->%c  ", p1, p2);
}
 
//n:个数  pos1:起始位置  pos2:中转位置  pos3:目的位置
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
 
int main()
{
	Hanoi(1, 'A', 'B', 'C');
	printf("\n");
	Hanoi(2, 'A', 'B', 'C');
	printf("\n");
	Hanoi(3, 'A', 'B', 'C');
	printf("\n");
	Hanoi(4, 'A', 'B', 'C');
	printf("\n");
	return 0;
}

注意点一:代码中的n值不能太大,因为移动次数是随n的增大呈指数倍增长。

注意点二:n为1的时候已近到达最小单位(也就是最底层),不需要使用递归;n为大于1的值时,需要递归到1才能进行。

注意点三:第一阶段使用递归表示的是把上面n-1层全部移到B中;而第二阶段使用递归表示的是把B中全部移到C中。

总结

这样就可以简单地完成汉诺塔,此代码并不是最优方法,但是理解起来比较容易。递归在实际中运用的不是很多,但是也要看得懂代码和写出类似这种汉诺塔等递归函数的基础代码。

加载全部内容

相关教程
猜你喜欢
用户评论