“汉诺塔问题变式及解析”

汉诺塔I

汉若塔I（经典汉若塔问题），有三塔，A塔从小到大从上至下放有N个盘子，现在要搬到目标C上，规则：小的必需放在大的上面，每次只能移动一个，求最小步数。

这个问题简单，DP：a[n]=a[n-1]+1+a[n-1]。

先把上面的n-1个放在B上（此时能借助C柱）（ps！这里必须移走n-1个盘子只能剩下1个最大的盘子放在A上，否则如果多余2此后无法移动，因为没有可以借助的柱子，B上的盘子都比A上的小）
把最大的从A放到目标C上（1步）
再把N-1个放回到C上即可（此时能借助A柱）。

[上述方法（先移动n-1个盘子，把n拆成n=1+(n-1)。三个柱子问题只有这种拆分方法）是唯一方法所以能保障步数最小]

所以最后的DP：a[n]=a[n-1]+1+a[n-1]（第一大步和第三大步的移动步数是相同的。算出前几项+寻找递推公式（即找到后项与前项的关系十分重要））是解决汉诺塔问题的关键步骤。

汉诺塔II

考虑汉诺塔问题需要提前掌握经典汉诺塔问题，其中有一个结论：依靠三个柱子A,B,C把n个盘子借助B从A移到C，所需要的步数是2^n -1（2的n次方-1）

汉诺塔问题II题目

汉诺塔问题II与I同样分解为3个步骤来解决：（有A,B,C,D四个柱子供移动）

从A中移动X(1<=X<n)个盘子到C（此时能借助B,D柱），需要的步数为F【x】
从A中移动剩下n-X个盘子到D（此时由于C柱的盘子都比这n-X个小，所以只能借助B盘），需要的步数：2^(n-x)-1（2的n-x次方-1）【这时候是只能借用一个盘子，是经典的汉诺塔问题的结论】
最后把C中的X个盘子移动到D（此时能借助A,B。现在A已经是空柱子了），需要的步数是F【x】

综上需要的总步数是：F[n]=F[X]+2^(n-X)-1+F[X]=2*F[X]+2^(n-X)-1。

但是需要注意，要求是求出最小的步数所以需要遍历X的值找到最小的F[n]存入结果。 实际该问题的答案应该min{2*F[x]+2^(n-x)-1},其中1<=x<n.

#include<iostream>
#include<cmath>
#define N 1000000000000000000
using namespace std;
long long int ans[65];
int main(){
	ans[0]=0;
	ans[1]=1;
	ans[2]=3;
	ans[3]=5;
	
	for(long long int i=4;i<=64;i++){
		long long int min=N;
		for(long long int x=1;x<i;x++){
			if(min>2*ans[x]+pow(2,i-x)-1){
				min=2*ans[x]+pow(2,i-x)-1;
			}
		}
		ans[i]=min;
	}
	int n;
	while(cin>>n){
		cout<<ans[n]<<endl;
	}
	return 0;
}

汉诺塔III

把你想要记录步数的未知量设置为F[X]（这种记录步数的值是通过题目要求的方法计算出来的）,X表示移动盘子的数目。通过寻找递推关系来解决。

汉诺塔问题III题目

汉诺塔问题III步骤如下：（必须是通过中间的杆子相邻移动，并且三个柱子的问题应当把n拆分为n=(n-1)+1这两个部分）

把n-1个盘子从A移动到C（借助一柱子：B），按照题目要求的方法，设这种移动需要F[n-1]步。
把余下的一个大盘子从A移动到B，需要一步（满足相邻移动.反思第一步为什么直接从A到C，而不是A到B。若是移动n-1到B，那么第二步要移动出剩下的那个大盘，没办法借助B（B的盘子都比A小）,但是剩下的那个大盘子不能直接从A到C（不能非相邻移动），因此走投无路。所以必须在第一步直接把n-1个盘子从A移动到C，保证步数最少)。
把C上的n-1个盘子从C移动到A（B中的盘子比C上的所有盘子都大.借助一柱子：B），需要移动F[n-1]步。
把B上的最大盘子从B移动到C，需要一步
最后把A上的n-1个盘子从A移动到C(借助一柱子：B)，需要步数F[n-1]

综上需要的总步数是：F[n]=3*F[n-1]+2.（满足最少步数要求，也是唯一方法）

注意！这里1和3和5中的F[n-1]和题目要求的F[n]都是根据相邻移动的规则，借助中间的柱子从最左移到最右或者最右移到最左这样两侧的相互移动。所以1和3和5中的F[n-1]和题目要求的F[n]是相同规则下的同一标准的变量，满足递推前后先同一规则的要求

#include<iostream>
#include<cmath>
using namespace std;
long long int ans[40];
int main(){
	ans[0]=0;
	ans[1]=2;
	ans[2]=8;
	ans[3]=26;
	for(long long int i=4;i<=35;i++){
		ans[i]=3*ans[i-1]+2;
	}
	int n;
	while(cin>>n){
		cout<<ans[n]<<endl;
	}
	return 0;
}

汉诺塔IV

汉诺塔IV问题与汉诺塔III问题有着绝对的相似性。但是很容易进入误区，这时候又应该强调递归要求前后项的做法有着相同的规则，不可以是不同的规则。

以下给出汉诺塔IV问题的两种解法和思路（注意题目的要求是：只能在移动过程中最大的盘子可以在最上面（只有最大的那个可以），最终的结果还是要从小到大排列）

解法一

把三个柱子标记为A,B,C。最终题目需要解出借助B（中间柱子）将n个盘子从A移动到C的最少步数(最大盘子在顶上+相邻移动)。这样的走法用ans[n]数组表示。单纯的借助B（中间柱子）将n个盘子从A移动到C的最少步数，用AC[n]表示（ans[n]与AC[n]不同，在下面做出解释），这里的AC[n]的值就是汉诺塔问题III的解的值。同理AB[n],BC[n].(这里注意！AC[n]=CA[n]—只是起点终点对调总的原则没有变化，都是借助中间柱子，两侧的相互移动。类似的，BC[n]=BA[n]从中间柱子移动到某侧边柱子并借助另一侧柱子，只是终点不同，形式方法一致。同理理解AB[n]=CB[n]，从侧边柱子移动到中间柱子，借助另一侧柱子)（这些数组都满足相邻移动）
```
 ps.实质上，BC[n]=BA[n]=AB[n]=CB[n]
 这是两大类：中柱到侧柱和侧柱到中柱。
 中柱到侧柱（以BA为例）：BA[n]=BC[n-1]+1+CA[n-1]=BA[n-1]+AC[n-1]+1(AC=CA,BC=BA);
 侧柱到中柱（以AB为例）：AB[n]=AC[n-1]+1+CB[n-1]=AB[n-1]+AC[n-1]+1(CB=AB);
 观察不难发现BA和AB有着同样的递推形式,并且起始条件AB[0]=BA[0]=0一样，所以AB=BA,又AB=CB,BA=BC。所以BC=BA=AB=CB.(可以化简后面的总步数)
```
先将n-1个盘子从A移动到B，步数为：AB[n-1]
再将A中余下的最大盘子，依次从A移动到B，B移动到C（这个是最大盘子可以放在小盘子上面）移动步数：2
再将n-1个盘子从B移动到C，步数为：BC[n-1]

综上需要的总步数为：ans[n]=AB[n-1]+2+BC[n-1]=2xAB[n-1]+2（注意！这里的ans[n]并不等于AC[n]，因为他们的规则不一样。ans[n]在移动的时候满足总步数的公式,它可以存在最大的在顶上的情况。但是AC[n]和AC[n-1]的规则是一样的（才能顺序递推下去），只是从A移动到B借助C，不能存在最大盘子在最顶上的情况。否则递推会有误，例如AC[4]是根据AC[3]递推出来的,AC[3]中如果可以最大盘子在顶上那么这个最大盘子就是3号盘，然后递推AC[4]的时候用到AC[3]的结果，那么这时候最大盘子应该是4号而不是3号，但是AC[3]中有3号（此时已经不是最大盘）盘子在顶上的移动。所以相邻移动+特殊某个盘子的特别变化（例如本题的最大盘子）是不满足递推关系的。因此你也可以看到总步数公式内的并没有ans[n-1]的存在，因为题目的规则不满足递推关系） AC[n]:相邻移动（结论满足汉诺塔III） ans[n]：相邻移动+最大盘子n可以在顶上（最终不可以，过程可n盘在顶）

反观总步数：ans[n]=AB[n-1]+2+BC[n-1]=2xAB[n-1]+2的移动过程。对于n-1个盘子的AB移动，必须满足相邻移动，且其中不包含最大盘n，所以不可以存在n-1盘（非最大盘）置顶的移动。同理BC[n-1]。 这是把非递推形式的规则转化为递推形式的规则的过程。

代码如下：（求ans要求AB，求AB需要AC）

#include<iostream>
#include<cmath>
using namespace std;
long long int ans[25];
long long int ab[25];
long long int ac[25]; 
int main(){
	ans[0]=ab[0]=ac[0]=0;
	for(long long int i=1;i<=20;i++){
		ac[i]=3*ac[i-1]+2;
		ab[i]=ab[i-1]+1+ac[i-1];
		ans[i]=2*ab[i-1]+2;
	}
	int n;
	cin>>n;
	int num;
	while(n--){
		cin>>num;
		cout<<ans[num]<<endl;
	}
	return 0;
}

解法二

解法二是解法一的简化，由解法一可以知道ans[n]=AB[n-1]+2+BC[n-1]。AB[n-1]+BC[n-1]=AC[n-1].所以ans[n]=AC[n-1]+2.

由汉诺塔III可知：AC[n]=3*AC[n-1]+2.最后该题目的结果ans就是AC[n-1]+2(一定要注意解法一中强调的AC和ans是不同的规则，并且一个可以递推一个不可以递推)

注意：求出ans[n]之前的那些移动只能满足相邻移动（不能满足当前k个盘子的最大盘能置顶），所以达到最后一步之前的移动是AC[k]=3*AC[k-1]+2(详见汉诺塔III)。达到最后一步可以先移到n-1到AB,最大盘从A-B-C(2步),最后再把n-1个盘子从B移动到C，也就是AC[n-1]+2

//此处AC用ans来表示，可以把ans[k]看成AC[k]
#include<iostream>
#include<cmath>
using namespace std;
long long int ans[25];
int main(){
	ans[0]=0;
	for(long long int i=1;i<=20;i++){
		ans[i]=3*ans[i-1]+2;
	}
	int n;
	cin>>n;
	int num;
	while(n--){
		cin>>num;
		cout<<ans[num-1]+2<<endl;
	}
	return 0;
}

基于基本汉诺塔问题的4种变式

汉诺塔I

汉诺塔II

汉诺塔III

汉诺塔IV

解法一

解法二

FEATURED TAGS

FRIENDS