普通汉诺塔问题
1. 问题描述
有三个柱子A、B、C，A柱子上有n个圆盘，圆盘的大小不等，大圆盘的在下，小圆盘的在上。
将A柱子上的圆盘全部移动到C柱子上。每次只能移动一个圆盘，而且在移动的过程中，三个柱子上的圆盘始终保持大圆盘在下，小圆盘在上。
2. 问题输入
A柱子上的圆盘数量，当输入为0时，程序结束。
3. 程序输出
圆盘移动的过程和圆盘移动的总次数。
4. 递推公式
由于圆盘需要通过B柱，从A柱转移到C柱，因此可以设H(n)表示n个圆盘从A柱到C的移动次数。
则首先领前n-1个圆盘由A柱移动到B柱，有移动次数H(n-1)，然后将最大的圆盘从A柱移动到C柱需要移动1次，
然后问题就转化为了将 n-1 个圆盘从B柱通过A柱移动到C柱，有移动次数H(n-1)。
因此我们可以得到递推公式：
H(1) = 1;H(n) = H(n - 1) + 1 + H(n - 1) = 2 * H(n - 1) + 1;
5. 问题代码（cpp版本）
/***
* Author : DL1024
* Date : 2022-11-11
* ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void move(int number, char x, char y){
cout << number << " 号圆盘从 " << x << " 移动到 " << y << endl;
}
int Hanio(int n, char A, char B, char C){
ll cnt1 = 0, cnt2 = 0;
if (n == 1){
move(1, A, C);
return 1;
} else{
cnt1 = Hanio(n - 1, A, C, B); // n-1个从A移动到B柱
move(n, A, C); // 把n号盘从A移动到C
cnt2 = Hanio(n - 1, B, A, C); // n-1个从B移动到C
return cnt1 + 1 + cnt2;
}
}
int main( ){
cout << "汉诺塔问题解决方案：\n";
ll cnt = 0;
int n = 0;
do{
cout << "请输入A柱子上面的圆盘数量n:";
if (cin >> n){
if (n == 0) break;
cnt = Hanio(n, 'A', 'B', 'C');
cout << n << "个圆盘从A移动到C的总次数为" << cnt << endl;
} else break;
} while (1);
return 0;
}
汉诺塔问题变形
1. 问题描述
有三个柱子A、B、C，A柱子上有n个圆盘，圆盘的大小不等，大圆盘的在下，小圆盘的在上。
将A柱子上的圆盘全部移动到C柱子上。每次只能移动一个圆盘，而且在移动的过程中，三个柱子上的圆盘始终保持大圆盘在下，小圆盘在上。
另外，不允许直接从A柱子移动到C柱子或直接从C柱子移动到A柱子，即每次移动一定是移动到中间柱子B或者从中间柱子B移走。
例如，当A柱子上只有一个圆盘时，首先将这个圆盘从A柱子移动到中间柱子B，再从中间柱子B移动到C柱子，总共移动次数是2。
2. 问题输入
A柱子上的圆盘数量，当输入为0时，程序结束。
3. 程序输出
圆盘移动的过程和圆盘移动的总次数。
4. 递推公式
由于圆盘必须需要通过B柱，从A柱转移到C柱或者从C柱转移到A柱，因此可以设H(n)表示n个圆盘从A柱到C的移动次数。
则首先领前n-1个圆盘由A柱移动到C柱，有移动次数H(n-1)，然后将最大的圆盘从A柱移动到B柱需要移动1次，接下来将n-1个圆盘由C柱通过B柱再移动到A柱，有移动次数H(n-1)，然后再将最大的圆盘从B柱移动到C柱需要1次，然后问题就转化为了将 n-1 个圆盘从A柱通过B柱移动到C柱，即有移动次数H(n-1)。
因此我们可以得到递推公式：
H(1) = 1;H(n) = H(n - 1) + 1 + H(n - 1) + 1 + H(n - 1)= 3 * H(n - 1) + 2;
5. 问题代码（cpp版本）
/***
* Author : DL1024
* Date : 2022-11-11
* ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void move(int number, char x, char y){
if (x == 'B' || y == 'B'){
cout << number << " 号圆盘从 " << x << " 移动到 " << y << endl;
} else{
// x经过B到y
cout << number << " 号圆盘从 " << x << " 移动到 " << "B" << endl;
cout << number << " 号圆盘从 " << "B" << " 移动到 " << y << endl;
}
}
int Hanio(int n, char A, char B, char C){
ll cnt1 = 0, cnt2 = 0, cnt3 = 0;
if (n == 1){
move(1, A, C); // 只有一个圆盘的时候，先移动到B盘，再移动到C盘，2次
return 2;
} else{
cnt1 = Hanio(n - 1, A, B, C); // n-1个从A移动经过B到C
move(n, A, B); // n号盘从A移动到B
cnt2 = Hanio(n - 1, C, B, A); // n-1个从C移动经过B到A
move(n, B, C); // n号盘从B移动到C
cnt3 = Hanio(n - 1, A, B, C); // n-1个盘从A移动经过B到C
return cnt1 + 1 + cnt2 + 1 + cnt3;
}
}
int main( ){
cout << "汉诺塔问题解决方案：\n";
ll cnt = 0;
int n = 0;
do{
cout << "请输入A柱子上面的圆盘数量n:";
if (cin >> n){
if (n == 0) break;
cnt = Hanio(n, 'A', 'B', 'C');
cout << n << "个圆盘从A移动到C的总次数为" << cnt << endl;
} else break;
} while (1);
return 0;
}