C++实现汉诺塔游戏自动完成

一、汉诺塔的规则

游戏由3根柱子和若干大小不一的圆盘组成，初始状态下，所有的圆盘按照大小顺序从大到小堆叠在其中一根柱子上。将所有圆盘从初始柱子移动到目标柱子上即算完成目标。但须遵守以下规则：

1. 每次只能移动1个圆盘.
2. 圆盘可以放置在任何1根柱子上，但不能放在比它小的圆盘上.

比如3个盘子的汉诺塔，1个可能的解法是这样的：

二、数学递归推导式

一个脑筋急转弯：把大象关冰箱要几步？

只要3步！1.把冰箱打开，2.把大象装进去，3.把冰箱关上。看似简单的道理，其实蕴含着数学递归思维在其中。
从a柱向b柱移动n个盘子，同样采用的是递归思维在里面，将其定义f(a,b,n)，则可以有如下推导式：
f(a,b,n) = f(a,c,n-1) + f(a,b,1) + f(c,b,n-1)

解释一下：

f(a,b,n)代表从a柱向b柱移动n个盘子的过程，则先将n-1个盘子从a移到中间柱c上，再将a柱最底下的大盘子移到b柱上，最后将c柱上的n-1个盘子移到b柱上。当然只要n不为1，就一直递归下去，直到最基础的移动1个盘子。
设g(n)代表这个过程的盘子移动次数,则g(n)= 2g(n-1)+1，由此可得g(n)=$2^n$-1。

三、步骤实现

使用SDL库实现了图形显示，若对SDL库不了解的请阅读如下2篇引文(同时也实现了命令行显示，不了解SDL库也不影响理解)：

• 如何在Linux平台使用SDL库进行2D/3D游戏开发
• SDL开发实战（二）：SDL2.0核心API解析

(一)汉诺塔模型

这里涉及的知识点包括：类的定义、SDL_Renderer渲染器也就是画布。

//汉诺塔柱子，简化盘子为正整数
class Stick {public:deque<int> plates; //柱子放置盘子的栈int x, y; //柱子底中心位置int width, height; //柱子宽、高unsigned char r, g, b; //柱子颜色int pside, pheight; //盘子边长、厚度unsigned char pr, pg, pb; //盘子颜色Stick(int x, int y, int width, int height, unsigned char r, unsigned char g, unsigned char b,int pside, int pheight, unsigned char pr, unsigned char pg, unsigned char pb); //构造函数void show(SDL_Renderer*); //在指定渲染器绘制画面
};//整个汉诺塔模型
class Hanoi {private:SDL_Renderer * render; // 内置窗口渲染器指针public:Stick sticks[3]; //3根柱子Hanoi(SDL_Renderer *, int); //构造函数bool movePlate(int a, int b); //将1个盘子从a柱移到b柱void movePlates(int a, int b, int count); //将count个盘子从a柱移到b柱void show(); //在窗口绘制画面
};

(二)递归实现

这里涉及的知识点包括：类外实现、函数递归调用、deque容器，其中movePlate函数是移动1个盘子的基本操作，而movePlates则是移动多个盘子的函数，它通过递归调用逐渐缩小盘子数量，直到最后剩1个盘子后调用基本操作函数。

bool Hanoi::movePlate(int a, int b) {int plateA, plateB; //2根柱子顶端的盘子plateA = this->sticks[a].plates.back();if (!this->sticks[b].plates.empty()) {plateB = this->sticks[b].plates.back();if (plateA > plateB) return false;}//小盘子可以放在大盘子上this->sticks[a].plates.pop_back();this->sticks[b].plates.push_back(plateA);this->show(); //显示return true;
}void Hanoi::movePlates(int a, int b, int count) {if (count == 1) {this->movePlate(a, b);return;}//求出中间柱(0,1,2) -> (1,2,3) ->(0,1,2)int c = ((a+1) ^ (b+1)) - 1;this->movePlates(a, c, count-1); //从a柱移count-1个盘子到c柱this->movePlate(a, b); //从a柱移最后1个盘子到b柱this->movePlates(c, b, count-1); //从c柱移count-1个盘子到b柱
}

(三)显示

分为2个显示模块，1个是Hanoi汉诺塔模型的显示函数，而它继续调用每根柱子的显示函数。

1.命令行显示

void Hanoi::show() {//逐根绘制for (int n = 0; n < 3; n++) {//画柱子和柱子上的盘子cout << "第" << n << "根柱:";  //命令行显示this->sticks[n].show();}cout << endl;// 命令行显示//显示SDL_Delay(1500); //1.5秒刷新
}void Stick::show() {//画盘子for (int i = 0; i < this->plates.size(); i++) {cout << this->plates.at(i) << " "; //命令行显示   }cout << ","; //命令行显示
}

以3层为例，显示结果如下：

第0根柱:3 2 1 ,第1根柱:,第2根柱:,
第0根柱:3 2 ,第1根柱:,第2根柱:1 ,
第0根柱:3 ,第1根柱:2 ,第2根柱:1 ,
第0根柱:3 ,第1根柱:2 1 ,第2根柱:,
第0根柱:,第1根柱:2 1 ,第2根柱:3 ,
第0根柱:1 ,第1根柱:2 ,第2根柱:3 ,
第0根柱:1 ,第1根柱:,第2根柱:3 2 ,
第0根柱:,第1根柱:,第2根柱:3 2 1 ,

2.SDL图形显示

在命令行显示基础上进行扩充：

void Hanoi::show() {//先用白色背景清屏SDL_SetRenderDrawColor(this->render, 255, 255, 255, 255);SDL_RenderClear(this->render);//逐根绘制for (int n = 0; n < 3; n++) {//画柱子和柱子上的盘子cout << "第" << n << "根柱:";  //命令行显示this->sticks[n].show(render);}cout << endl; // 命令行显示//显示SDL_RenderPresent(this->render);SDL_Delay(1500); //1.5秒刷新
}void Stick::show(SDL_Renderer * render) {//画柱子SDL_Rect rect = {x - width/2, y, width, height}; //x, y,宽、高SDL_SetRenderDrawColor(render, r, g, b, 255); //不透明SDL_RenderFillRect(render, &rect);//画盘子for (int i = 0; i < this->plates.size(); i++) {cout << this->plates.at(i) << " "; //命令行显示int px = this->x - this->plates.at(i) * this->pside / 2; //盘子左边沿，盘子单位长为20int py = 600 - (i + 1) * this->pheight; //窗口高600，盘子上边沿，盘子单位厚度为10SDL_Rect rect = {px, py, this->plates.at(i)*this->pside, this->pheight}; //盘子坐标(px, py)、边长、厚//填色SDL_SetRenderDrawColor(render, this->pr, this->pg, this->pb, 255); //盘子为天蓝色，不透明SDL_RenderFillRect(render, &rect);//画黑色边框SDL_SetRenderDrawColor(render, 0, 0, 0, 255); SDL_RenderDrawRect(render, &rect);}cout << ","; //命令行显示
}

四、处理用户输入及SDL环境配置

放置在main函数中，最后显示出来就是文章开头展示的动图了。

    int n; //汉诺塔层数cout << "请输入汉诺塔层数：" << flush;cin >> n;//初始化SDL成视频模式SDL_Init(SDL_INIT_VIDEO);//初始化窗口，标题为汉诺塔，位置(x,y)默认，尺寸800X600，窗口为显示模式SDL_Window *window = SDL_CreateWindow("汉诺塔", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 800, 600, SDL_WINDOW_SHOWN);if (!window) {cout << "窗口生成异常" << endl;return 1;}//初始化窗口渲染器，相当于画布,-1表示默认的渲染设备，使用软件渲染SDL_Renderer *render = SDL_CreateRenderer(window, -1, SDL_RENDERER_SOFTWARE);if (!render) {cout << "渲染器生成异常" << endl;return 1;}//初始化汉诺塔Hanoi hanoi(render, n);hanoi.show(); //修复刚启动黑屏bughanoi.show();hanoi.movePlates(0, 2, n);SDL_DestroyRenderer(render);SDL_DestroyWindow(window);SDL_Quit();

五、总结

本篇文章摘记了使用C++语言实现汉诺塔游戏电脑自动完成的步骤，还没有实现用户交互，无多少可玩性，仅抛砖引玉，希望大家有所收获，如有好的建议欢迎留言，谢谢大家！

六、源码下载

C++语言实现汉诺塔自动完成