基于汉诺塔的问题归约图实现

一、求解汉诺塔（Hannoi）问题代码

#include "pch.h"
#include <fstream>
#include <iostream>
using namespace std;

int i = 0;

// 移动步骤
void Move(int n, char x, char y)
{
	i++;
	cout << "第" << i << "步：" << "圆盘" << n << "  " << x << " —> " << y << endl;
}

// 递归求解
void Hannoi(int n, char a, char b, char c)
{
	if (n == 1)
		Move(1, a, c);
	else
	{
		Hannoi(n - 1, a, c, b);
		Move(n, a, c);
		Hannoi(n - 1, b, a, c);
	}
}

int main()
{
	int n;
	cout << "请输入要求解的汉诺塔的层数：";
	cin >> n;
	cout << n << "层汉诺塔圆盘移动步骤:" << endl;
	Hannoi(n, 'a', 'b', 'c');
	cout << "\n输出完毕！" << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

程序中1234分别对应圆盘ABCD，abc对应柱子123

二、汉诺塔问题归约图

1、圆盘的个数为 3

把原始难题归约（简化）为下列3个子难题：
（1）移动圆盘 A 和 B 至柱子 2 的双圆盘难题
（2）移动圆盘 C 至柱子 3 的单圆盘难题
（3）移动圆盘 A 和 B 至柱子 3 的双圆盘难题

注意，归约图中的（x1,x2,x3）表示的是圆盘 A 在柱子 x3 上，圆盘 B 在 x2 上，圆盘 C 在 x1 上。

2、圆盘的个数为 4

把原始难题归约（简化）为下列子难题：

（1）移动圆盘A、B、和C 至柱子 2 的三圆盘难题

① 移动圆盘 A 和 B 至柱子 3 的双圆盘难题
② 移动圆盘 C 至柱子 2 的单圆盘难题
③ 移动圆盘 A 和 B 至柱子 2 的双圆盘难题
1
2
3

（2）移动圆盘 D 至柱子 3 的单圆盘难题

（3）移动圆盘A、B和C 至柱子 3 的三圆盘难题

① 移动圆盘 A 和 B 至柱子 1 的双圆盘难题
② 移动圆盘 C 至柱子 3 的单圆盘难题
③ 移动圆盘 A 和 B 至柱子 3 的双圆盘难题
1
2
3

注意，归约图中的（1231）表示的是圆盘A在柱子1上，圆盘B在柱子3上，圆盘C在柱子2上，圆盘D在柱子1上。

4层汉诺塔归约图

三、4 层汉诺塔问题归约（分）图