Visual C++课程设计报告
汉诺塔可视化小游戏
作者：
电子工程与光电技术学院
探测制导与控制技术
920104330118赵婧萱
一、综述
1.1 汉诺塔问题描述
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假设有三个分别命名为A,B,C的塔座，在塔座A上插有n个直径大小各不相同的圆盘，大的在下，小的在上，且从小到大编号为1,2,3…现要求将塔座A上的n个圆盘移到塔座C上并仍按同样的顺序叠排，圆盘移动时必须遵守以下规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在A,B,C中任一塔上；
（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
1.2 最优题解
汉诺塔问题是一种经典的递归问题，也是学习栈这个数据结构的入门算法题目。
汉诺塔由三根柱子（分别用A、B、C表示）和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上，大的在下面，小的在上面，形成了一个塔状的锥形体。 对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。
可以看到：小盘子在上，所以起步就是操作小盘子，然后才能操作大盘子。
所以需要有这么个函数：起始柱的小盘子移动到中间柱，这时起始柱的大盘子就可以移动到目标柱了，然后，中间柱的小盘子也就可以移动到目标柱了，这样，实现了盘子正确的移动到目标柱。
我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法可以简单分为三个步骤：
（1） 把n-1个盘子由A 移到 B；
（2） 把第n个盘子由 A移到 C；
（3） 把n-1个盘子由B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
（1）中间的一步是把最大的一个盘子由A移到C上去；
（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；
1.3 题解代码
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
| #include <iostream>
using namespace std;
void Move(int n, char A, char B, char C)
{
if (n == 1)
cout << "move " << n << " from " << A << " to " << C << endl;
else
{
Move(n - 1, A, C, B);
cout << "move " << n << " from " << A << " to " << C << endl;
Move(n - 1, B, A, C);
}
}
void Hanoi(int n)
{
if (n <= 0)
return;
Move(n, 'A', 'B', 'C');
}
int main()
{
Hanoi(3);
return 0;
}
|
二、初步设计
（1）内部数组显示（纵向+横向）：要求汉诺塔层数n，起始柱，结束柱由键盘输入，打印出移动的盘子编号以及从哪根柱子移动到哪根柱子的具体步骤，要求记录移动步数，加入延时效果，要求动态显示移动过程中每根柱子现有的盘子以及盘子编号，同时要求显示速度可由键盘输入进行选择，显示竖行。
（2）图形解-自动移动版本：大的在下，小的在上；不同盘子不同颜色；要求加入延时效果。移动时先上移，平移，然后下移；延时。同时显示横向和纵向；显示速度可由键盘输入选择，0为手动；延时。
（3）图形解-游戏版：要求手动输入柱子编号，分别表示此次移动的起始柱和目标柱；对输入的合理性进行判断，如大盘压小盘，需
要提示错误；要求记录步数；待所有盘子移动到结束柱是显示“游戏结束”。要求检查输入数据的合理性（包括要求输入数字而输入字母的非法情况）。
用全局变量，全局数组的方式分别记录三根圆柱中的圆盘数，圆盘编号，总移动步数。
面对相对复杂的程序，我选择将其拆分成若干个小问题去解决，最终整合成最终的程序。同时，在这些小问题中挑选出比较核心的问题，其他小问题都是围绕着它们进行编程，实现。
整个程序最核心的部分是如何利用递归来解决汉诺塔问题。其次是显示内部数组部分，思路是利用“栈”的思想，对栈顶的元素进行判断，移动（通过值的变化）。最后一部分，是伪图形界面下图形的移动和生成。思路是通过对光标位置的设定，用空格再“走”一遍图形“走”过的路。
三、主要功能的实现
3.1 利用最优的搬运方式解决汉诺塔问题—递归算法
分析Hanoi问题，本质上是不停的在做同一个操作，即从起始柱，借助中间柱将盘子转移到结束柱，因此可以设计成函数，不停的调用该函数，设置结束条件，即n=1时，回溯，即输出每一步的搬运过程，即源程序中的Hanoi函数。
1
2
3
4
5
6
7
8
9
10
11
12
| void hanoi(int n, char A, char B, char C, int pace, int leap, int t, int m)
{
if (n == 1)
move(n, A, C, pace, leap, t, m);
else
{
hanoi(n - 1, A, C, B, pace, leap, t, m);
move(n, A, C, pace, leap, t, m);
hanoi(n - 1, B, A, C, pace, leap, t, m);
}
}
|
3.2 每根柱子盘子情况显示—“栈”
将每根柱子看成是一个数组，本质就是打印数组内部的值。盘子的移进移出都是对当下柱子最顶部的盘子有所操作，对数组而言，需要打印的元素个数就是当时柱子上圆盘的个数，操作是对于栈顶元素。
实现方法：
定义二维数组pan[3] [10]，[3]代表三根柱子，[10]代表数组大小。初始化时，起始柱最底部的柱子初始化为n，即pan[begin] [i]=n-i (i=0,1,2…n-1)，这样同时完成了盘子的编号。其余两根柱子（数组）所有元素初始化为-1.通过元素编号来判断有没有盘子。操作过程中，先进先出，通过对栈顶元素值的变化模拟柱子盘子的搬动情况。用top_a,top_b分别表示“出发柱”和“到达柱”的栈顶盘子的位置，即数组中值大于0的元素个数-1.
“到达柱”接收一个盘子后，新的栈顶元素位置为top_b=top_b+1，pan [final] [top_b]=pan [beg] [top_a];
“出发柱”搬出一个盘子后，将原来的栈顶元素的值赋给“到达柱”新的栈顶元素，此时原来的栈顶元素所在的位置没有盘子，即pan[begin] [top_a]=-1,同时，新的栈顶元素位置top_a=top_a-1。
最后输出只需要判断元素的值是否大于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
38
39
40
| void move(int i, char x, char y, int pace, int leap, int t, int m)
{
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
if (t >= 0)
rate(t);
sum++;
if (pace)
{
if (t >= 0)
gotoxy(hout, 0, basic_Y + 8);
if (m)
gotoxy(hout, 0, basic_Y + 19);
cout << "第" << setw(4) << sum << "步 " << '(' << setw(2) << i << "):" << x << "-->" << y;
if (!leap)
cout << endl;
}
else
cout << i << '#' << ':' << x << "-->" << y << endl;
if (leap)
{
int j = 0, k = 0;
while (pan[f(x)][j] != -1 && j < n)
j++;
while (pan[f(y)][k] != -1 && k < n)
k++;
pan[f(y)][k] = pan[f(x)][j - 1];
pan[f(x)][j - 1] = -1;
print_row();
if (t >= 0)
if (m)
{
print_col(basic_Y + 14, basic_Y + 14, basic_Y + 14);
move_pan(i, x, y, j - 1, k - 1, t);
}
else
{
print_col(basic_Y, basic_Y, basic_Y);
}
}
}
|
3.3 图形方式显示时，盘子的移动
for循环，改变图形（对空字符设置颜色，长度）的位置，加入Sleep（）函数实现延时效果，使整个过程更加直观，容易观察。
判断坐标变化时，在图形，也就是盘子左右移动时，每次都需要判断“出发柱”和“到达柱”的相对位置，来确定横坐标i++还是i- -以及空格字符打印的位置（i是打印时光标的位置，在图形的最左端）。为此，我添加了一个整型变量q=（f（x）>f(y)?-1:1）,利用i+=q就可以达到i++/- -要求。（其中f()是自定义的函数将键盘输入的起始柱，目标柱的字符对应到数字，以方便于对应数组的对应）。
而空字符打印位置的确定，q=1时，图形右移，空字符打印在i的位置；q=-1时，图形左移，空字符打印在i+p的位置（p=图形长度-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
| void move_pan(int p, char x, char y, int j, int k, int t)
{
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
for (int s = 15 - j; s > 2; s--)
{
showch(hout, 15 + 30 * f(x) - p, s - 1, ' ', p, p, p * 2 + 1);
if (s < 15 - j)
{
showch(hout, 15 + 30 * f(x), s, ' ', COLOR_HYELLOW, COLOR_HYELLOW, 1);
showch(hout, 15 + 30 * f(x) - p, s, ' ', 0, 7, p);
showch(hout, 15 + 30 * f(x) + 1, s, ' ', 0, 7, p);
}
if (t == 0)
Sleep(50);
else
rate(t);
}
int q = ((f(x) > f(y)) ? (-1) : 1);
for (int i = 15 + 30 * f(x) - p; i != 15 + 30 * f(y) - p; i += q)
{
showch(hout, i + q, 2, ' ', p, p, p * 2 + 1);
if (q == 1)
showch(hout, i, 2, ' ', 0, 7, 1);
else
showch(hout, i + 2 * p, 2, ' ', 0, 7, p * 2 + 1);
if (t == 0)
Sleep(50);
else
rate(t);
}
for (int w = 3; w < 14 - k; w++)
{
showch(hout, 15 + 30 * f(y) - p, w, ' ', p, p, p * 2 + 1);
if (w > 3)
showch(hout, 15 + 30 * f(y), w - 1, ' ', COLOR_HYELLOW, COLOR_HYELLOW, 1);
else
showch(hout, 15 + 30 * f(y), w - 1, ' ', 0, 7, 1);
showch(hout, 15 + 30 * f(y) - p, w - 1, ' ', 0, 7, p);
showch(hout, 15 + 30 * f(y) + 1, w - 1, ' ', 0, 7, p);
if (t == 0)
Sleep(50);
else
rate(t);
}
showch(hout, 0, 28, ' ', 0, 7, 1);
}
|
3.4 宏和头文件
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
| #pragma once
#include <Windows.h>
#define COLOR_BLACK 0
#define COLOR_BLUE 1
#define COLOR_GREEN 2
#define COLOR_CYAN 3
#define COLOR_RED 4
#define COLOR_PINK 5
#define COLOR_YELLOW 6
#define COLOR_WHITE 7
#define COLOR_HBLACK 8
#define COLOR_HBLUE 9
#define COLOR_HGREEN 10
#define COLOR_HCYAN 11
#define COLOR_HRED 12
#define COLOR_HPINK 13
#define COLOR_HYELLOW 14
#define COLOR_HWHITE 15
void setcolor(const HANDLE hout, const int bg_color, const int fg_color);
void gotoxy(const HANDLE hout, const int X, const int Y);
void showch(const HANDLE hout, const int X, const int Y, const char ch, const int bg_color = COLOR_BLACK, const int fg_color = COLOR_WHITE, const int n = 1);
void setconsoleborder(const HANDLE hout, const int cols, const int lines);
|
3.5 辅助函数
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
| #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <Windows.h>
#include "cmd_console_tools.h"
using namespace std;
void setcolor(const HANDLE hout, const int bg_color, const int fg_color)
{
SetConsoleTextAttribute(hout, bg_color * 16 + fg_color);
}
void gotoxy(const HANDLE hout, const int X, const int Y)
{
COORD coord;
coord.X = X;
coord.Y = Y;
SetConsoleCursorPosition(hout, coord);
}
void showch(const HANDLE hout, const int X, const int Y, const char ch, const int bg_color, const int fg_color, const int n)
{
int i;
gotoxy(hout, X, Y);
setcolor(hout, bg_color, fg_color);
for (i = 0; i < n; i++)
putchar(ch);
}
void setconsoleborder(const HANDLE hout, const int cols, const int lines)
{
char cmd[80];
setcolor(hout, COLOR_BLACK, COLOR_WHITE);
system("cls");
sprintf(cmd, "mode con cols=%d lines=%d", cols, lines);
system(cmd);
return;
}
|
四、代码架构
4.0 架构综述
4.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
| int main()
{
int choice = 1;
while (choice != 0)
{
system("cls");
cout << "欢迎来到汉诺塔游戏！" << endl;
cout << "-------------------------------------------------" << endl;
cout << "1.内部数组显示（纵向+横向）" << endl;
cout << "2.图形解-自动移动版本\n3.图形解-游戏版本\n0.退出\n";
cout << "---------------------------------------------------\n[请选择0-3]" << endl;
cin >> choice;
switch (choice)
{
case 0:
break;
case 1:
sum = 0;
show_2(0);
break;
case 2:
sum = 0;
aotu();
break;
case 3:
sum = 0;
game();
break;
}
}
return 0;
}
|
4.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
| void show_2(int m)
{
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
int t;
check();
while (1)
{
cout << "请输入移动速度（0-5），0-按回车单步演示，1-延时最长，5-延时最短：";
cin >> t;
if (cin.fail() || t < 0 || t > 5)
{
cin.clear();
cin.ignore();
continue;
}
break;
}
for (int i = 0; i < 10; i++)
{
pan[f(beg)][i] = n - i;
pan[f(mid)][i] = -1;
pan[f(final)][i] = -1;
}
system("cls");
gotoxy(hout, 0, 0);
cout << "从" << beg << "移动到" << final << ",共" << n << "层，延时设置为" << t << endl;
print_basic(m);
rate(t);
print_col(basic_Y, basic_Y, basic_Y);
hanoi(n, beg, mid, final, 1, 1, t, m);
system("cls");
system("mode con cols=100");
cout << endl;
cout << "按回车键继续...";
while (_getch() != '\r');
}
|
4.3 图形解函数
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
| void aotu()
{
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
check();
int t;
while (1)
{
cout << "请输入移动速度（0-5），0-按回车单步演示，1-延时最长，5-延时最短：";
cin >> t;
if (cin.fail() || t < 0 || t > 5)
{
cin.clear();
cin.ignore();
continue;
}
break;
}
for (int i = 0; i < 10; i++)
{
pan[f(beg)][i] = n - i;
pan[f(mid)][i] = -1;
pan[f(final)][i] = -1;
}
draw_3column();
draw_pan();
gotoxy(hout, 0, 0);
cout << "从" << beg << "移动到" << final << ",共" << n << "层，延时设置为" << t << endl;
print_basic(1);
rate(t);
print_col(basic_Y + 14, basic_Y + 14, basic_Y + 14);
hanoi(n, beg, mid, final, 1, 1, t, 1);
cout << endl;
cout << "，按回车键继续...";
while (_getch() != '\r');
}
|
4.4 游戏函数
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
| void game()
{
rules();
HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
check();
draw_3column();
draw_pan();
for (int i = 0; i < 10; i++)
{
pan[f(beg)][i] = n - i;
pan[f(mid)][i] = -1;
pan[f(final)][i] = -1;
}
print_basic(1);
print_col(basic_Y + 14, basic_Y + 14, basic_Y + 14);
while (1)
{
gotoxy(hout, 0, 29);
cout << "请输入移动的柱号（命令形式：AC A顶端的盘子移到C）：";
cout << " ";
gotoxy(hout, 51, 29);
char c[2];
for (int i = 0; i < 2; i++)
cin >> c[i];
int j = 0, k = 0;
while (pan[f(c[0])][j] != -1 && j < n)
j++;
while (pan[f(c[1])][k] != -1 && k < n)
k++;
if (pan[f(c[0])][j - 1] > pan[f(c[1])][k - 1] && pan[f(c[1])][k - 1] > 0)
{
cout << "大盘压小盘，非法移动！";
Sleep(500);
gotoxy(hout, 0, 30);
cout << " ";
continue;
}
if (c[0] == c[1])
continue;
else
{
int b = pan[f(c[0])][j - 1];
move(b, c[0], c[1], 1, 1, 0, 1);
}
j = 0, k = 0;
while (pan[f(beg)][j] != -1 && j < n)
j++;
while (pan[f(final)][k] != -1 && k < n)
k++;
if (j == 0 && k == n)
{
cout << "游戏结束！" << endl;
break;
}
}
cout << "，按回车键继续...";
while (_getch() != '\r');
}
|
五、调试过程中遇到的问题
4.1 if(q) 和 if(q>0)
在图形左右移动过程中对空格添加的位置判断时，需要判断左移还是右移，左移q=-1,右移是q=1，分别对应不同的空格输出的位置。而我误以为if(q)的意思是q大于零时，而实际上，if(q)是当q不等于0时。这是一个认识性错误，也是最难找到的错误。耗时近三小时。
4.2 柱子底座有缺口
第八小题要求同时显示图形，竖式，横式。调试过程中发现搬运一开始，第一第二个底座就会出现一个缺口，大约一个字符宽度，而且正好就在竖式上方！对竖式的位置进行下移以后，显示正确！事实上，在竖式输出时程序的思路是，数组元素大于0输出元素的值，否则，输出空格！所以，虽然显示时没有，但其实还是存在并占据一定空间的。
4.3 圆盘上移“吃”下盘，下移“吐”柱子
顾名思义，就是圆盘上移时，下方的一个盘子会少一块，移到“到达柱”柱顶时，再下移时的同时，柱子会长一个字符的长度。
"吃"下盘，究其原因，其实是被“扫地”的黑前景黑后景空格字符“扫”干净了！圆盘上移的实现方法是：先在正下方打印黑色空字符串把圆盘原来的图形“扫干净”，再在圆盘正上方一个单位用showch函数打非黑色的字符串。而我没有考虑到圆盘刚刚“出发”时，正下方是另一个圆盘，或者是底座。
解决方法:
在上移循环体内加一句判断语句
if 纵坐标 < 圆盘初始坐标 then 做“扫地”操作
“吐”柱子，其实是多填补了一小段柱子。圆盘下移的实现方式是：先在正下方打印非黑色字符串的图形，再把原来字符串所在的位置用黑色字符串“扫干净”，此时，那一段范围内的柱子也被扫掉了，于是，再补一小段柱子。而当圆盘正好在柱子顶端时，下移后原来坐在的位置本就没有柱子，我却补了一段。
解决方法：
在下移循环体内也加一句判断
if 纵坐标 > 柱子顶部所在纵坐标 做“扫地”操作，同时填补柱子
五、心得体会
（1）反复出现的常量，宏定义在源程序开头，提高程序可维护性。
（2）定义函数或者变量时，名字尽量取得有意义。防止函数，变量较多时，不停的翻源程序看对应的功能。
（3）当程序规模比较大的时候，上下滚动查看函数很不方便。可以使用编程界面左侧 的“减号”把一些程序“叠”起来，如 ；
这样可以加快查找函数的速度，同时不至于满屏幕的代码看的眼花缭乱。
（4）在程序测试阶段，程序规模较大时，测试时修改的地方较多。为了防止把程序改“坏”之后回不到原来“好”的时候，可以在每次成功一小步后，把源代码复制到另外一个工程文件中，保存起来。
（5）遇到想不通的思路，流程时，充分利用纸笔来助我理通思路。
