VC++汉诺塔讲解、辅导汉诺塔VC++
- 首页 >> C/C++编程基于 Windows 编程的汉诺塔游戏动画演示
1 概述
1.1 起源
汉诺塔是由法国数学家爱德华·卢卡斯在 1883 年发明的。汉诺塔 (又称河内塔) 问题是源于印
度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下
往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新
摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一
个圆盘。
1.2 抽象为数学问题
如下图所示，从左到右有 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 n 个圆盘，现
要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘
子不能在小盘子上面，求移动的步骤和移动的次数。
图 1: 汉诺塔
1.3 递归解法
当 n=3 时，如果能把 1 和 2 号两个较小的盘子从 A 柱子通过 C 柱子移到 B 柱子，那么可以
直接将 3 号盘子从 A 柱子移到 C 柱子。剩下的问题就是将剩余的两个盘子从 B 柱子通过 A
1
2 动画演示的实现 2
柱子移动到 C 柱子，这时将问题转换为 n=2 时更小问题。
所以说一共就三步：
• 把 n-1 个盘子 A 柱子通过 C 柱子移动到 B 柱子；
• 把最后一个盘子从 A 柱子移动 C 柱子；
• 然后把 B 柱子的 n-1 个盘子通过 A 柱子移动 C 柱子。
C++ 代码如下：
Listing 1: 汉诺塔递归算法
void MovePlates ( i n t n , Tower& from , Tower& by , Tower& to )
{
i f (n == 1)
{
cout << ”move plate from source tower to d e s t i n a t i o n tower ” << endl ;
return ;
}
MovePlates (n − 1 , from , dst , by ) ;
MovePlates (1 , from , by , to ) ;
MovePlates (n − 1 , by , from , to ) ;
}
2 动画演示的实现
2.1 数据结构
1. 盘子类
如下图所示，容易定义盘子的数据结构如下：
图 2: 盘子示意图
2 动画演示的实现 3
Listing 2: 盘子类
c l a s s Plate {
public :
i n t left_ , right_ , top_ , bottom_ ;
i n t width_ , height_ ;
POINT center_point_ ;
Plate ( )
{
left_ = right_ = top_ = bottom_ = 0 ;
width_ = height_ = 0 ;
center_point_ = { 0 ,0 } ;
}
~ Plate ( ) {}
void set_position (POINT center_point )
{
center_point_ = center_point ;
left_ = center_point_ . x − width_ / 2 ;
right_ = center_point_ . x + width_ / 2 ;
top_ = center_point_ . y − height_ / 2 ;
bottom_ = center_point_ . y + height_ / 2 ;
}
void DrawPlate (HDC hdc )
{
HPEN plate_pen = CreatePen (PS_SOLID, 1 , color_ ) ;
HBRUSH plate_brush = CreateSolidBrush ( color_ ) ;
SelectObject ( hdc , plate_pen ) ;
SelectObject ( hdc , plate_brush ) ;
RoundRect ( hdc , left_ , top_ , right_ , bottom_ , width_ / 3 , height_ ) ;
}
} ;
成员函数 set_position 是通过给定盘子的中心点来构造盘子，而成员函数 DrawPlate 通过调
用设备环境来绘制盘子。
2. 塔类
每一个塔有 n 个盘子、底座和柱子三个部分组成。
Listing 3: 塔类
c l a s s Tower {
public :
std : : vector<Plate> plates_ ;
i n t pole_height_ ;
i n t base_length_ ;
POINT base_center_ ;
POINT pole_top_ ;
POINT base_left_ ;
POINT base_right_ ;
const Plate& operator [ ] ( i n t index ) const
{
return plates_ [ index ] ;
}
2 动画演示的实现 4
图 3: 塔示意图
} ;
3. 汉诺塔类
汉诺塔游戏中，总共有三个塔，由三个 Tower 类型的成员变量 src_tower_、by_tower_ 和
dst_tower_ 表示，HWND 类型变量 hwnd_ 是用于绘制图形的窗口句柄。
Listing 4: 汉诺塔类
c l a s s HanoiTower {
public :
i n t plates_count_ ;
HanoiTower ( void ) : inited_ (FALSE) , plates_count_ (3) {}
~HanoiTower ( void ) {}
void set_inited (BOOL i n i t e d )
{
inited_ = i n i t e d ;
}
BOOL i s I n i t e d ( )
{
return inited_ ;
}
void set_hwnd (HWND hwnd)
{
hwnd_ = hwnd ;
}
2 动画演示的实现 5
void InitHanoi ( i n t plates_count , i n t width , i n t height ) ;
void DrawLine (HDC hdc , POINT start , POINT end ) ;
void DrawHanoi (HDC hdc ) ;
void ClearBackground (HDC hdc , RECT &r e c t ) ;
void MovePlates ( i n t plates_count , Tower& src_tower ,
Tower& by_tower , Tower& dst_tower ) ;
void StartMove ( ) ;
private :
Tower src_tower_ ;
Tower by_tower_ ;
Tower dst_tower_ ;
HWND hwnd_;
BOOL inited_ ;
} ;
2.2 汉诺塔成员函数的实现
1. 初始化汉诺塔
首先需要确定每一个盘子的高度和塔基的宽度。
如图 4 所示，窗口的高度和宽度分别为 height 和 width，假设有 n 个盘子，则盘子的高度显
然为：
plate_height = height/(n + 3)
设定每一个塔间距离为 Margin，则塔基的宽度为
base_width = (width − 4 ∗ M argin)/3
图 4: 汉诺塔示意图
第一个塔的塔基左边点的 X、Y 坐标分别是
base_lef t_x = M argin
base_lef t_y = plate_height ∗ (n + 2)
2 动画演示的实现 6
第一个塔的塔基右边点的 X、Y 坐标分别是
base_right_x = M argin + base_length
base_right_y = plate_height ∗ (n + 2)
第一个塔的塔基中点的 X、Y 坐标分别是
base_center_x = M argin + base_length/2
base_center_y = plate_height ∗ (n + 2)
第一个塔的柱子顶点的 X、Y 坐标分别是
base_top_x = M argin + base_length/2
base_top_y = plate_height
同理，可以计算出另外两个塔的相应参数。
因为初始状态，第二个和第三个塔都是没有盘子的，所以只需要计算第一个塔的盘子参数。
显然，自底向上，每一个盘子的宽度是相比于塔基宽度是逐渐减小的，对于第 i 个盘子，容易
求得缩小的比例为
ratio = 1 − i/(n + 2)
所以第 i 个盘子的宽度和中心点坐标分别是
plate_width = base_length ∗ ratio
plate_center_x = base_center_x
plate_center_y = base_center_y − (i − 1) ∗ plate_height + plate_height/2
有了盘子的中心点，可以通过成员函数 set_position 构建盘子。
相应的代码如下：
Listing 5: InitHanoi 函数
void HanoiTower : : InitHanoi ( i n t plates_count , i n t client_width , i n t client_height )
{
set_inited (TRUE) ;
plates_count_ = plates_count ;
i n t plate_height = client_height / ( plates_count + 3 ) ;
i n t base_length = ( client_width − 4 * MARGIN) / 3 ;
src_tower_ . base_left_={MARGIN, plate_height *( plates_count + 2 ) } ;
src_tower_ . base_right_={MARGIN+base_length , plate_height *( plates_count +2)};
src_tower_ . base_center_={MARGIN+base_length /2 , plate_height *( plates_count +2)};
src_tower_ . pole_top_ = {MARGIN+base_length /2 , plate_height } ; ;
src_tower_ . base_length_ = base_length ;
by_tower_ = src_tower_ ;
by_tower_ . base_left_ . x += MARGIN + base_length ;
by_tower_ . base_right_ . x += MARGIN + base_length ;
by_tower_ . base_center_ . x += MARGIN + base_length ;
by_tower_ . pole_top_ . x = by_tower_ . base_center_ . x ;
dst_tower_ = by_tower_ ;
dst_tower_ . base_left_ . x += MARGIN + base_length ;
dst_tower_ . base_right_ . x += MARGIN + base_length ;
dst_tower_ . base_center_ . x += MARGIN + base_length ;
2 动画演示的实现 7
dst_tower_ . pole_top_ . x = dst_tower_ . base_center_ . x ;
Plate plate ;
double r a t i o = 0 ;
src_tower_ . plates_ . c l e a r ( ) ;
by_tower_ . plates_ . c l e a r ( ) ;
dst_tower_ . plates_ . c l e a r ( ) ;
POINT center_point = { 0 ,0 } ;
std : : vector<int> rand_seq = s h u f f l e ( ) ;
f o r ( i n t i = 1 ; i <= plates_count ; i++)
{
r a t i o = 1 − ( double ) ( i ) / ( plates_count + 2 ) ;
plate . width_ = ( i n t ) ( base_length * r a t i o ) ;
plate . height_ = plate_height ;
center_point = src_tower_ . base_center_ ;
center_point . y −= ( i − 1)* plate_height + plate_height / 2 ;
plate . set_position ( center_point ) ;
src_tower_ . plates_ . push_back ( plate ) ;
}
}
2. 绘制汉诺塔
绘制汉诺塔包括绘制盘子、塔基和柱子，其中塔基和柱子可以用直线代替。DrawLine 成员函
数就是为了绘制线条，可以设置线条颜色和粗细，使得塔基和柱子看起来较为美观。
Listing 6: DrawHanoi 成员函数
void HanoiTower : : DrawLine (HDC hdc , POINT start_point , POINT end_point )
{
HPEN line_pen = CreatePen (PS_SOLID, 15 , RGB(0 , 0 , 0 ) ) ;
SelectObject ( hdc , line_pen ) ;
MoveToEx( hdc , start_point . x , start_point . y , NULL) ;
LineTo ( hdc , end_point . x , end_point . y ) ;
}
Listing 7: DrawHanoi 成员函数
void HanoiTower : : DrawHanoi (HDC hdc )
{
// base l i n e
DrawLine ( hdc , src_tower_ . base_left_ , src_tower_ . base_right_ ) ;
DrawLine ( hdc , by_tower_ . base_left_ , by_tower_ . base_right_ ) ;
DrawLine ( hdc , dst_tower_ . base_left_ , dst_tower_ . base_right_ ) ;
// pole l i n e
DrawLine ( hdc , src_tower_ . base_center_ , src_tower_ . pole_top_ ) ;
DrawLine ( hdc , by_tower_ . base_center_ , by_tower_ . pole_top_ ) ;
DrawLine ( hdc , dst_tower_ . base_center_ , dst_tower_ . pole_top_ ) ;
f o r ( std : : vector<Plate >:: i t e r a t o r i t e r = src_tower_ . plates_ . begin ( ) ;
i t e r != src_tower_ . plates_ . end ( ) ; i t e r ++)
{
i t e r −>DrawPlate ( hdc ) ;
}
2 动画演示的实现 8
f o r ( std : : vector<Plate >:: i t e r a t o r i t e r = by_tower_ . plates_ . begin ( ) ;
i t e r != by_tower_ . plates_ . end ( ) ; i t e r ++)
{
i t e r −>DrawPlate ( hdc ) ;
}
f o r ( std : : vector<Plate >:: i t e r a t o r i t e r = dst_tower_ . plates_ . begin ( ) ;
i t e r != dst_tower_ . plates_ . end ( ) ; i t e r ++)
{
i t e r −>DrawPlate ( hdc ) ;
}
}
3. 移动汉诺塔
移动汉诺塔的方法与 1.3 描述的递归算法一致。当 n=1 时，需要将第一个塔的盘子减少一个，
第三个塔的盘子增加一个。为了实现动画效果，每移动一次，需要发送一个消息给窗口函数，
使得重新绘制汉诺塔。所以需要在头文件中定义一个用户消息 WM_MOVE 为：
#define WM_MOVEON (WM_USER+0x0001)
详细代码如下：
Listing 8: MovePlates 成员函数
void HanoiTower : : MovePlates ( i n t plates_count , Tower& src_tower ,
Tower& by_tower , Tower& dst_tower )
{
i f ( plates_count == 1)
{
Plate plate = src_tower . plates_ . back ( ) ;
src_tower . plates_ . pop_back ( ) ;
POINT dst_point = dst_tower . base_center_ ;
dst_point . y −= dst_tower . plates_ . s i z e ()* plate . height_ ;
dst_point . y −= plate . height_ / 2 ;
plate . set_position ( dst_point ) ;
dst_tower . plates_ . push_back ( plate ) ;
SendMessage (hwnd_, WM_MOVEON, 0 , 0 ) ;
return ;
}
MovePlates ( plates_count − 1 , src_tower , dst_tower , by_tower ) ;
MovePlates (1 , src_tower , by_tower , dst_tower ) ;
MovePlates ( plates_count − 1 , by_tower , src_tower , dst_tower ) ;
}
void HanoiTower : : StartMove ( )
{
MovePlates ( plates_count_ , src_tower_ , by_tower_ , dst_tower_ ) ;
set_inited (FALSE) ;
}
4. 清除背景
每一次绘制之前需要清除前一次绘制的汉诺塔，防止图像叠加。
2 动画演示的实现 9
Listing 9: 清除背景
void HanoiTower : : ClearBackground (HDC hdc , RECT &r e c t )
{
HBRUSH brush = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
F i l l R e c t ( hdc , &rect , brush ) ;
}
2.3 窗口函数的消息处理
1. 设置基本变量
Listing 10: 窗口函数变量
LRESULT CALLBACK WndProc(HWND hWnd, UINT message , WPARAM wParam , LPARAM lParam )
{
s t a t i c i n t x c l i e n t = 0 , y c l i e n t = 0 ; // 绘 制 窗 口 尺 寸
s t a t i c i n t plates_count = 3 ; // 汉 诺 塔 盘 子 数 目
RECT bg_rect = { 0 ,0 ,0 ,0 } ; // 矩 形 区 域 变 量 ， 用 于 设 置 清 除 窗 口 背 景
s t a t i c HanoiTower hanoi ; // 汉诺 塔变 量
hanoi . set_hwnd (hWnd) ; // 设 置 汉 诺 塔 的 窗 口 句 柄 ， 用 于 绘 制 汉 诺 塔
}
2. 获取窗口尺寸。
窗口可能会缩放，可以通过 WM_SIZE 消息获取窗口尺寸，同时当窗口尺寸改变时，应该重
新初始化汉诺塔。
Listing 11: WM_SIZE 消息
case WM_SIZE:
{
x c l i e n t = LOWORD( lParam ) ;
y c l i e n t = HIWORD( lParam ) ;
hanoi . InitHanoi ( plates_count , x c l i e n t , y c l i e n t ) ; // 初 始 化 汉 诺 塔
InvalidateRect (hWnd, NULL, TRUE) ; // 发送WM_PAIT消息 ， 绘制 汉 诺塔
}
break ;
3. 添加鼠标消息
设置左键初始化汉诺塔，右键开始移动汉诺塔。
Listing 12: 鼠标消息
case WM_LBUTTONDOWN:
{
hanoi . InitHanoi ( plates_count , x c l i e n t , y c l i e n t ) ;
InvalidateRect (hWnd, NULL, TRUE) ;
}
break ;
case WM_RBUTTONDOWN:
{
i f ( hanoi . i s I n i t e d ( ) )
2 动画演示的实现 10
{
hanoi . StartMove ( ) ;
}
}
break ;
4. WM_PAIT 消息 WM_PAIT 消息中主要实现清除背景和绘制汉诺塔工作。
Listing 13: WM_PAIT 消息
case WM_PAINT:
{
PAINTSTRUCT ps ;
HDC hdc = BeginPaint (hWnd, &ps ) ;
// TODO: Add any drawing code that uses hdc here . . .
GetClientRect (hWnd, &bg_rect ) ;
hanoi . ClearBackground ( hdc , bg_rect ) ;
hanoi . DrawHanoi ( hdc ) ;
EndPaint (hWnd, &ps ) ;
}
break ;
5. 用户自定义消息这一步是实现汉诺塔动画演示的关键。每当移动一次盘子时，都会发送
WM_MOVE，这时需要绘制当前状态下的汉诺塔。
Listing 14: 用户自定义消息
case WM_MOVEON:
{
HDC hdc = GetDC(hWnd) ;
GetClientRect (hWnd, &bg_rect ) ;
hanoi . ClearBackground ( hdc , bg_rect ) ; // 清除背景
hanoi . DrawHanoi ( hdc ) ; // 绘制 汉诺 塔
ReleaseDC (hWnd, hdc ) ;
Sleep ( 1 0 0 ) ; // 休眠 100ms
}
break ;
2.4 小结
• 通过简单实验掌握从实际问题抽象为数学问题，再通过编程实现的能力。
• 在现有基础之上，通过扩展美化界面效果。比如设置每一个盘子为不同颜色、添加消息
处理可以交互式增加盘子数量等等。通过设置变量来控制休眠时间，因为当盘子数目增
大时，需要移动的次数很多，可以适当减小休眠时间。