设计并实现一个游戏:汉诺塔。
完成这个实验,涉及C++面向对象编程以及基本的数据结构知识(如栈和队列)但具此次实现并没有使用STL库。
1. 汉诺塔问题
汉诺塔是一个著名的数学问题。它由三根杆子和若干不同大小的盘子组成。开始时,所有的盘子都在第一根杆子上,并按照从上到下大小升序排列(也就是说,最小的在最上面)。这个问题的目标是将所有盘子移到另一根杆子上,并遵守以下简单的规则:
解决这个问题的经典方法是递归。该算法可以描述为以下伪代码:
function hanoi(n, A, B, C) { // move n disks from rod A to rod B, use rod C as a buffer
hanoi(n - 1, A, C, B);
move(n, A, B); // move the nth disk from rod A to rod B
haoni(n - 1, C, B, A);
}
2. 实验描述
在本实验中,杆子的数量总是等于3,盘子的数量可以是1~5。其中,第1根杆子为初始杆,第2根为目标杆。
本实验的任务包括以下内容:
- 完成一个交互式的汉诺塔游戏程序,根据用户输入的指令移动相应的盘子,并在用户胜利时打印提示;
- 通过命令行界面,将汉诺塔游戏的状态绘制出来,包括3根杆子和若干盘子;
- 根据汉诺塔问题的递归算法,提供一个自动求解程序,能够从任一状态出发,通过若干步移动达到目标状态。
具体而言,程序的流程如下:
打印汉诺塔状态的要求:我们用 |
表示杆子, -
表示底座,一排 *
表示盘子。每个盘子从小到大分别用3、5、7、9、11个 *
表示(最多5个盘子)。 无论盘子数量多少,输出的整个画布的大小固定为11×41。
例如,一共5个盘子,均按照从小到大放在杆1上,此时输出的结果应该如下:
| | |
*** | |
| | |
***** | |
| | |
******* | |
| | |
********* | |
| | |
*********** | |
输入输出
这里给出两个样例,分别使用自动模式和手动模式。这里行首的 >
<
代表是程序的输入还是输出。
样例1:
< How many disks do you want? (1 ~ 5)
> 2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< *** | |
< | | |
< ***** | |
< -----|--------------|--------------|-----
< Move a disk. Format: x y
> 0 0
< Auto moving:1->3
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< ***** | ***
< -----|--------------|--------------|-----
< Auto moving:1->2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | ***** ***
< -----|--------------|--------------|-----
< Auto moving:3->2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | *** |
< | | |
< | ***** |
< -----|--------------|--------------|-----
< Congratulations! You win!
< How many disks do you want? (1 ~ 5)
> Q
样例2:
< How many disks do you want? (1 ~ 5)
> 2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< *** | |
< | | |
< ***** | |
< -----|--------------|--------------|-----
< Move a disk. Format: x y
> 1 2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< ***** *** |
< -----|--------------|--------------|-----
< Move a disk. Format: x y
> 2 3
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< ***** | ***
< -----|--------------|--------------|-----
< Move a disk. Format: x y
> 1 2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | ***** ***
< -----|--------------|--------------|-----
< Move a disk. Format: x y
> 3 2
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | | |
< | *** |
< | | |
< | ***** |
< -----|--------------|--------------|-----
< Congratulations! You win!
< How many disks do you want? (1 ~ 5)
> Q
Original: https://www.cnblogs.com/world-explorer/p/16147254.html
Author: O_fly_O
Title: 汉诺塔
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/607257/
转载文章受原作者版权保护。转载请注明原作者出处!