汉诺塔问题学习报告

汉诺塔问题学习报告

(如解析和参考有错误或可以精进之处,欢迎批评指正。)

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。这需要多少次移动呢?
(来源 百度百科)

这就是最基本的汉诺塔问题。

一.基本汉诺塔的最少移动步数求解
一个未移动过的汉诺塔模型。例题1:现在有一个N层的汉诺塔,要解决这个汉诺塔问题,至少要移动多少步? (难度1)

汉诺塔的特点就在于小的只能放在大的上面,这也是解题的关键。
设a[N]表示解决N层汉诺塔的最少步数,每一层表示为a,b,c,…。
显然a[1]=1。
解决2层的时候,先把a放在B柱以腾出C柱,然后把b放在C柱,再把a放到C柱。因此a[2]=3。
那么怎么求解a[3]呢?我们依照a[2]的思路来考虑:为了完成任务,我们需要把c放到C柱,在此之前a、b应该已经放在B柱(否则不可能使c被拿出来),然后再把a、b叠在C柱。移动a、b的过程中完全可以忽略c的影响,因此解法就变为:先使a、b组成的2层汉诺塔ab叠在B柱,再把c放在C柱,最后把ab放在C柱。因此a[3]=a[2]+1+a[2]=2 * a[2]+1。
综上所述,对于一个N层的汉诺塔,先在B柱完成一个(N-1)层的汉诺塔,然后把n放在C柱,最后在B柱完成一个(N-1)层的汉诺塔,a[N]=2 * a[N-1]+1。(核心结论1)
这样一来,基本汉诺塔求解的递推式已经得出,剩下的就不是难事了。
核心代码:

int a[101],n;
scanf("%d",&n);
a[0] = 0;
for(i = 1;i <= n;i++){
	a[i] = 2 * a[i - 1] + 1;
}
printf("%d",a[n]);

(注意:递推法不要忘记给起始条件)

除此之外,根据算出的结果,还可以发现a[N]=2^N-1(使用的时候可能需要配合快速幂)。这样就得出了一种汉诺塔步数问题的结果式。

因此我们可以知道,要想毁灭世界(我相信他们做这个的目的不是为了毁灭世界而只是为了忽悠人),需要操作汉诺塔2^64-1次。假设这群僧侣能做到每时每刻都有人在操作它,而且手速快到2秒中就能操作一次、耐心到即使一直在操作也不会搞错,也需要上万亿年。这是什么概念,假设僧侣从这一刻开始操作,那么即使到了太阳毁灭的那一天(这应该才是真的世界末日),他们也才刚操作完5%。

和基本的汉诺塔直接相关的还有双塔问题(无非就是原式的基础上全部乘2)。但是值得思考的是下面这个问题:

思考题:小明同学已经学会了汉诺塔怎样操作最快,现在他买了两套汉诺塔,一套为白色,一套为黑色。他把这两套汉诺塔各取出N层大小完全相同的部分,如下图所示摆放。若同样大小的层可以互相堆叠,且堆叠时不必考虑颜色差别,该汉诺塔最快需要多少步才能完成,此时颜色是否与原来的分布完全一致?(难度2)
思考题
很显然,颜色与原来的分布是不一致的,因为如果不考虑颜色,完全可以直接把不同色的同样大小的两层看作一层,就是双塔问题;但是如果考虑颜色,且希望在整个操作过程中都严格要求同色不能叠加,其实就是一个2N层的单塔;如果过程中不作要求,最下方的一层也肯定要分成黑白两色操作。篇幅有限,具体的最少步数在此就不作说明了。

二.汉诺塔操作的模拟

汉诺塔模拟的难度是大幅高于求解的难度的,为了模拟这一过程,既需要我们明白汉诺塔问题求解的根本方法,也需要我们熟练地掌握递归(显然后者更难一些)。

例题2:现在有一个N层的汉诺塔,单数层为白色,双数层为黑色。现在要将这个汉诺塔移动到B柱上,且操作过程中不允许相同颜色的层叠在一起。试模拟这个汉诺塔的操作过程,并在最后输出总操作步数。(难度3)
例题2
首先需要说明的是,这题的颜色纯粹是一个干扰项,因为即使没有这个限制在操作的时候也是一样的(原因下面会解释到)。
根据我们得出的核心结论,解决各种汉诺塔问题的关键就在于第N层这个分界点。 同样来思考这个模拟,我们肯定要保证最终n从A移动到B,而为此,我们需要在此之前把所有n上面的这(N-1)个层全部移到C柱去,但是为了把n-1移到C柱去,还得保证n-2要移到B柱去……如上,一个前半部分的递归方案就基本成型了。后半部分同理,(N-1)个层全部都在C柱,为了使n-1到B柱,又需要使n-2到A柱……这个过程在上半部分回溯的时候就可以得到解决。
核心代码如下:

int count;
void Move(int n, char a, char b){
    count++;
    printf("%d %c %c\n",n,a,b);
}
void Hanoi(int n, char a,char b,char c){//注解
    if(n == 1) Move(n,a,c);
    else{
    	Hanoi(n - 1,a,c,b);
    	Move(n,a,c);
		Hanoi(n - 1,b,a,c);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    Hanoi(n,'A','B','C');
    printf("%d",count); 
    return 0;
}

(注:a相当于起点,b相当于终点,c相当于中转)

解决了这一问题,再来看下面这个问题:

例题3:(P1242 新汉诺塔)(难度5)
例题3
此题又是一个模拟,这题由于不像例题2初始和结果那么有规律,所以有很多东西需要我们运用刚才的经验。
根据上一道题的经验(又或者说是没有根据),我们最终的目的是把每一层放到他该去的地方,而且在此之前要腾出给他的空间。因此我们应该从大到小循环进入递归,直到每一层都归位为止。
同时我们要注意到这道题的无规律性,所有盘在移动过程当中的操作确确实实需要我们手动模拟,因此要即时地改变每一个盘的所在位置。
核心代码如下:

struct yjx{
	int from,to;
}a[101];//记每一层所在位置为from,目的地为to
int n,sum;
void hanoi(int x,int y){//把x移动到y位置去
	if(a[x].from == y) return;//已到达的不必再排
	else{
		int i;
		for(i = x - 1;i >= 1;i--) hanoi(i,6 - (a[x].from + y));//注解1
		printf("move %d from %c to %c\n",x,a[x].from - 1 + 'A',y - 1 + 'A');//注解2
		a[x].from = y;
		sum++;
	}
}
int main(){
	......//输入部分略过
	for(i = n;i >= 1;i--) hanoi(i,a[i].to);
	printf("%d",sum);
	return 0;
}//此题很容易混淆x和i、a[x].from和x,要多加注意

(注1:这里的6-(a[x].from + y)其实求的是某个盘的当前位置和目的地以外的那个柱,因为三个柱的和是6)
(注2:这里的一番操作是要把1、2、3转化为A、B、C)

就在我们愉快地AC(对多数人来说应该也是AK)比赛之后,把这道题交回到洛谷上冲业绩的时候,我们却发现这只能得到90分,打开最后一个点,给出了一个看起来相当人畜无害的输入文件:
在这里插入图片描述
这个的结果显然应该是五步,但是程序结果如下:
在这里插入图片描述
为什么?
(注意:以下完全属于本人分析,因此可能存在大量极其复杂反人类的内容,难以接受不建议阅读)
根据我们的程序,我们总是在为更大的让出位置,只有完全腾出位置才会继续向更小的考虑,程序当中就是先把1、2两层堆到了B柱,完全腾出C柱后才继续向A柱操作。但事实上这没必要,其实最快的方案应该是3给12腾出A柱,让1、2先在A柱操作完,然后把3移到C柱。
分析一下可以知道,之所以最快的方案比我们的代码还快,是因为我们的代码当中总是移动小的,使大的先到目的地以防止讨论大小;但这恰恰意味着,大的限制了小的到达目的地,使得小的总要先全部移到非目的地的柱才能进行下去。
在此之前,我们试验了一下,对于我们90分的代码,如果把输入数据中3的初始位置就设成B柱,结果是4步,也就是最少步数。因此我们不必推翻过去的代码,只要适当的插入操作,使得这个特殊的操作强行先于接下来的部分就可以了。
首先我们明确,如果这个盘本身可以以原方式操作,那么就不必再进行特殊操作(毕竟特殊操作是插入的,错误的插入会导致强行多了一步完全没用的操作)。因此就需要严密的讨论。
这里我们不妨举出反例:什么时候我们不能无视大小直接移动这个盘?
首先既然我们要求可以无视大小,那么就得保证它是最上面的一个 (强行操作也是要符合基本法的) 。因此如果它不是,就不能特殊操作。
其次,我们腾出空间是因为后面的盘可以直接到达目的地,如果压根没有哪一个盘到达它所在的位置,就不必腾出这个空间,不能特殊操作。
另外,由于我们要把这个盘放到一个中转柱,如果这个盘比中转柱上的任意一个盘大,那就不能特殊操作;如果下面确实有比它大的,如果这些盘已经到了目的地,我们的特殊操作就没有影响,可以操作;如果没有到的话,以后还是要移走让下面的大盘去目的地,也没有影响,也可以操作。
考虑到这三点,就已经算是比较全面的了。综合一下,可以得出以下的结论:
要想进行这个特殊操作,要保证我们要移动的盘所在的柱没有任何的盘挡在上面,而且我们要移到的中转柱上原来的盘都比它大(全称);除此之外,要保证盘所在的位置是还未到达的至少一个盘的目的地(存在)。
因此特判如下:

void hanoi(int x,int y){
	if(a[x].from == y) return;
	else{
		int i;
		lipu = 0,telipu = 1;
		for(i = n;i >= 1;i--){
			if(a[i].from == 6 - (a[x].from + y) && i != x && a[i].from != a[i].to || a[i].from == a[x].from && i < x || a[i].to == 6 - (a[x].from + y) && a[x].to != a[x].from){
				lipu = 1;//前两条
				break;
			}
		}
		if(lipu == 0){
			for(i = n;i >= 1;i--){
				if(a[x].from == a[i].to && x != i && a[i].from != a[i].to){
					telipu = 0;//第三条
					break;
				}
			}
		}
		......//特判条件:lipu和telipu都为0

这个时候我们就已经战胜了洛谷并拿到了AC。

只是我们还是要思考一下:
为了使得总移动数尽可能少,要使得1到n-1这一堆的移动次数尽可能的少。因此如果有条件可以先移动大盘到目的地,这样有可能使n-1堆少移动一次,节省很多操作;但是如果操作大盘的过程中n-1层反复操作多组,操作就会变多。这一过程很难特判,因此我们尝试分类比较,先按照从大到小的基本思想操作,再按照优先移大的思想操作,比较一下究竟哪一种操作少,然后单独输出这一种的操作过程就可以了。
核心代码如下:

struct yjx{
	int from,to;
}a[3][101];
int n,sum,ans[3];
bool go;
void hanoi(int w,int x,int y){//注解1
	if(a[w][x].from == y) return;
	else{
		int i;
		for(i = x - 1;i >= 1;i--){
			if(a[w][i].from != 6 - (a[w][x].from + y)) hanoi(w,i,6 - (a[w][x].from + y));
		}
		if(go == 1) printf("move %d from %c to %c\n",x,a[w][x].from - 1 + 'A',y - 1 + 'A');
		a[w][x].from = y;
		sum++;
	}
}
int main(){
	for(i = n;i >= 1;i--) hanoi(1,i,a[1][i].to);
	ans[1] = sum;
	sum = 0;
	for(i = n;i >= 1;i--){
		if(a[2][i].from != a[2][i].to){
			hanoi(2,i,6 - (a[2][i].from + a[2][i].to));
			break;//只需要操作一次
		}
	}
	for(i = n;i >= 1;i--) hanoi(2,i,a[2][i].to);
	ans[2] = sum;
	go = 1;
	if(ans[1] <= ans[2]){
		for(i = n;i >= 1;i--) hanoi(0,i,a[0][i].to);
	}
	if(ans[1] > ans[2]){
		for(i = n;i >= 1;i--){
			if(a[0][i].from != a[0][i].to){
				hanoi(0,i,6 - (a[0][i].from + a[0][i].to));
				break;
			}
		}
		for(i = n;i >= 1;i--) hanoi(0,i,a[0][i].to);
	}
	printf("%d",min(ans[1],ans[2]));
	return 0;
}

(注1:这里多了一个w,是用来记录代表的是方法1,方法2还是答案。因为我们要操作三次,每次都是从初始状态开始操作,因此需要一个二维数组,省去初始化的麻烦)
这道题给了我们一个启发:
一个汉诺塔问题有时可以拆分成多个塔的操作,为了使一个汉诺塔整体操作步数尽可能少,要使其层数最多的那一部分操作次数尽可能少。(核心结论2)

得到了又一个利器,来看本篇最后一道题:
例题4(奇怪的汉诺塔):
小华现在有一个奇怪的汉诺塔,这个汉诺塔有4个柱子。现在小华有一个N层的汉诺塔,试计算出解决这个汉诺塔问题需要的最少步数。
(难度3)
这道题相比刚才那些费脑筋的递归还是要简单一些的。现在我们面对的是一个四柱问题,但是如果我在某一柱上放下M个,剩下的(N-M)个就构成了一个三柱问题。记res[i]为四柱的最少步数,res1[i]为三柱的最少步数(这一数组应该已经提前准备好值),有递推式为:
res[i]=res[j]+res1[i-j]
这样问题就得到解决了。

总而言之,汉诺塔问题是一个前后规律性强而又能千变万化的题型,对我们的递归和递推以至于数学逻辑能力都是不小的考验,要善于化总体为部分、化复杂为简单。
Thank you for reading!