汉诺塔的几种变格

Algorithm

木制汉诺塔
这个木制汉诺塔真好看，这张图虽然没什么用，还是放在这儿了。

汉诺塔的几种变格。
Image Loading

汉诺塔(基本)

假设有n个圆盘，3根柱子abc，需要把n个盘子(从下往上按照大小顺序放置)从a柱移到c柱，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

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
#include <iostream>
using namespace std;

void move(int num, char frompeg, char topeg)
{
	cout << "Move disk " << num << " from peg " << frompeg << " to peg " << topeg << endl;
}

void towers(int num, char frompeg, char topeg, char auxpeg)
{
	if (num < 1)
		return;
	towers(num - 1, frompeg, auxpeg, topeg);
	move(num, frompeg, topeg);
	towers(num - 1, auxpeg, topeg, frompeg);
}

int main()
{
	int num;

	cout << "Enter the number of disks : ";
	cin >> num;
	cout << "The sequence of moves involved in the Tower of Hanoi are :" << endl;
	towers(num, 'A', 'C', 'B');
	system("Pause");
}

汉诺塔(必须通过中间的柱子)

假设有n个圆盘，3根柱子abc，需要把n个盘子(从下往上按照大小顺序放置)从a柱移到c柱，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。不允许直接从最左/右边移到最右/左边，每次移动一定是移入中间或是移出中间。

1
2


汉诺塔(必须通过中间的柱子，允许最大的放在最上面)

假设有n个圆盘，3根柱子abc，需要把n个盘子(从下往上按照大小顺序放置)从a柱移到c柱，在小圆盘上不能放大圆盘，但允许最大的盘子放在最上边。在三根柱子之间一次只能移动一个圆盘。不允许直接从最左/右边移到最右/左边，每次移动一定是移入中间或是移出中间。

1
2


汉诺塔(加一根柱子)

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <unordered_map>
using namespace std;

void move(int num, char frompeg, char topeg)
{
	cout << "Move disk " << num << " from peg " << frompeg << " to peg " << topeg << endl;
}

unordered_map<int, int> calculate_towers_split_values(int num)
{
	unordered_map<int, int> move_four;	// numbers of move when using four peg
	unordered_map<int, int> move_three;	// numbers of move when using three peg
	unordered_map<int, int> split_values;	// j using four peg, i-j using three peg
	// calculate moves when using three peg
	move_three[1] = 1;
	for (int i = 2; i <= num; ++i)
	{
		move_three[i] = 2 * move_three[i - 1] + 1;	
	}
	// known four peg moves
	move_four[1] = 1; move_four[2] = 3;
	split_values[1] = split_values[2] = 0;
	// start moving
	for (int i = 3; i <= num; ++i)
	{
		int min_move(move_three[i]);
		int moves(move_three[i]);
		int j_value(0);
		for (int j = 1; j < i; ++j)
		{
			// move j to the fourth peg, i-j to the third peg, move j back to the third peg
			moves = 2 * move_four[j] + move_three[i - j];
			if (min_move > moves)
			{
				min_move = moves;
				j_value = j;
			}
		}
		move_four[i] = min_move;
		split_values[i] = j_value;
	}
	// move_four[num] is the required minimum number
	return split_values;
}

void towers_three(int num, char frompeg, char topeg, char auxpeg)
{
	if (num < 1)
		return;
	towers_three(num - 1, frompeg, auxpeg, topeg);
	move(num, frompeg, topeg);
	towers_three(num - 1, auxpeg, topeg, frompeg);
}

void towers(int num, char frompeg, char topeg, char auxpeg, char aux2peg, const unordered_map<int, int>& split_values)
{
	if (num < 1)
		return;
	int split_value(split_values.at(num));
	towers(split_value, frompeg, aux2peg, auxpeg, topeg, split_values);
	towers_three(num - split_value, frompeg, topeg, auxpeg);
	towers(split_value, aux2peg, topeg, frompeg, auxpeg, split_values);
}

int main()
{
	int num;

	cout << "Enter the number of disks : ";
	cin >> num;
	cout << "The sequence of moves involved in the Tower of Hanoi are :" << endl;
	unordered_map<int, int>split_values(calculate_towers_split_values(num));
	towers(num, 'A', 'C', 'B', 'D', split_values);
	system("Pause");
}

Ref:
[1] http://blog.csdn.net/xujinsmile/article/details/8091738
[2] http://proprogramming.org/solution-for-tower-of-hanoi-c/