汉诺塔的详细分析步骤及可视化程序_为什么汉诺塔n-1可以看做一个整体

 三个柱子：  A， B， C
 盘子数：    n
 
 1. 通过整体思想，把n-1看为一个整体，目的显而易见
 	把  n-1    	 从   A   移到    B
 	把  最大的  	 从   A   移到    C
	把  n-1      从   B   移到    C
 
 2. 其中比较费解的就是：
        n-1如何从A移到B的
        n-1又是如何从B移到C的。
 
 3. 解释n-1如何从A移动B
 把  n-2     从   A   移到   C
 把  最大的   从   A   移到   B
 把  n-2     从   C   移到   B
 
 4. 解释n-1如何从B移动C
 把  n-2     从   C   移到  A
 把  最大的   从   C   移到  B
 把  n-2     从   A   移到  B
 
 1的步骤可以看作是 从A移到C
 3的步骤可以看作是 从B移到A
 4的步骤可以看作是 从C移到B
 
 根据这些我们可以建立通用的函数：
 move(int nNumb, string strFrom, string strTo);
 参数:    nNumb       移动个数
         strFrom     从哪移动
         strTo       移到哪去
 
 
 问题就可以概括为：
                                         { move(n-2, "A", "C")
                   { move(n-1, "A", "B") { move(1,   "A", "B")
                   {                     { move(n-2, "C", "B")
 move(n, "A", "C") { move(1,   "A", "C")                            ...
                   {                     { move(n-2, "B", "A")
                   { move(n-1, "B", "C") { move(1,   "B", "C")
                                         { move(n-2, "A", "C")
 
 
 由上又可以看出部分结构的组成，通过这部分结构，可以看出这就是一个递归体：
 
                     { move(n-1, Begin, Other)
 move(n, Begin, End) { move(1,   Begin, End  )
                     { move(n-1, Other, End  )
 
 那么递归的终止条件在哪呢？我们按照这个步骤推演到最后，结构类似如下：
 
                     { move(1, Begin, Other)
 move(2, Begin, End) { move(1, Begin, End  )
                     { move(1, Other, End  )
 
 显而易见的，move(1, ..., ...);没有再执行下去的必要。 所以这也就成为了递归的终止条件。
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

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <tchar.h>

using std::max_element;
using std::cout;
using std::endl;
using std::vector;
using std::string;

static int nStep = 0;

struct HanNuoTa
{
	string strName;			// 塔名
	vector<int> vecData;	// 塔内数据
};

HanNuoTa GetTaByName(const string & strName, const HanNuoTa& A, const HanNuoTa& B, const HanNuoTa& C)
{
	if (strName.compare(A.strName) == 0)
	{
		return A;
	}
	else if (strName.compare(B.strName) == 0)
	{
		return B;
	}
	else if (strName.compare(C.strName) == 0)
	{
		return C;
	}
}

void PrintData(const HanNuoTa& A, const HanNuoTa& B, const HanNuoTa& C)
{
	int nNumb[] = { A.vecData.size(), B.vecData.size(), C.vecData.size() };
	int nMax = *max_element(nNumb, nNumb + 3);

	if (nStep == 0)
	{
		cout << "开始：" << endl;
	}
	else
	{
		cout << "第" << nStep << "步" << endl;
	}
	
	cout << "A" << "\tB" << "\tC" << endl;
	nStep++;

	HanNuoTa ATemp = GetTaByName("A", A, B, C);
	HanNuoTa BTemp = GetTaByName("B", A, B, C);
	HanNuoTa CTemp = GetTaByName("C", A, B, C);

	for (int i = 0; i < nMax; i++)
	{
		cout << (ATemp.vecData.size() > i ? ATemp.vecData.at(i) : 0) << "\t";
		cout << (BTemp.vecData.size() > i ? BTemp.vecData.at(i) : 0) << "\t";
		cout << (CTemp.vecData.size() > i ? CTemp.vecData.at(i) : 0) << endl;
	}

	cout << endl;
}

void Move(const int nNumb, HanNuoTa& stuFrom, HanNuoTa& stuTo)
{
	stuTo.vecData.insert(stuTo.vecData.begin(), stuFrom.vecData.begin(), stuFrom.vecData.begin() + nNumb);
	stuFrom.vecData.erase(stuFrom.vecData.begin(), stuFrom.vecData.begin() + nNumb);
}

//**************************************************
//	@参数：nNumb	移动数量
//		   A		开始移动的塔
//		   B		途径的塔
//		   C		结束的塔
//**************************************************
void HanNuo(const int nNumb, HanNuoTa& A, HanNuoTa& B, HanNuoTa& C)
{
	if (nNumb == 1)
	{
		Move(nNumb, A, C);
		PrintData(A, B, C);
	}
	else
	{
		HanNuo(nNumb - 1, A, C, B);
		HanNuo(1, A, B, C);
		HanNuo(nNumb - 1, B, A, C);
	}
}

int main(int argc, const char* argv[])
{
	HanNuoTa A, B, C;
	A.strName = "A";
	A.vecData = { 1, 2, 3 };

	B.strName = "B";
	C.strName = "C";

	PrintData(A, B, C);
	HanNuo(A.vecData.size(), A, B, 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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

测试结果：