2021-11-04

2021-11-04

hanoi塔问题C++实现

 

 

如图，在A，B，C三根柱子中，A柱子有n个盘子（由上至下从小到大）串在上面，如何在满足以下的规则下将所有盘子移动到C柱子上。用C++语言表达移动的方法。

规则：1.每次只能移动一个盘子。

           2.叠放的过程中只能是小一点的盘子叠放在大一点的盘子上。

思路：

我们不难发现，此过程中我们的目的就是使A上的n个盘子从A移动至C点，那么我们如何达成这个目的？

在这个问题中我们要想将n个盘子移动至C柱可以分解为以下步骤：

步骤一：先将A柱上的n个盘子上面的n-1个盘子移动至B柱（此过程肯定会借助C柱）（调用某函数），然后再将A上的盘子移动至C柱

 步骤二：B柱上的n-1个盘子上的n-2个柱子移动至A柱（此过程肯定会借助C柱）（与步骤一中调用的函数相同，不过实参改变罢了），再将B柱上的一个盘子移动至C柱上。

 步骤三及以后的步骤都是不断地重复的使用的两种步骤将问题缩小规模罢了，直至问题规模缩小到可以解决，那么最小的问题解决了，就可以逆推回去把第二个至第三至n个问题解决了。

那么问题就会从n个盘子的问题变成n-1个盘子移动最后递减至1个盘子移动，来解决问题了。

所以可以使用递归的方法。

不如假设有这么一种的函数 hanoi（在此递归条件下，我们不必完全他的具体什么样，只知道它可以完成某个问题）我们只要调用它就可以使其完成由x柱借助y到达z柱。

然后就可以用此函数去将问题规模缩减至可解，然后反推出最后结果。

那么就可以写出程序了：

同理，换一种路径（同种思路）也可以写成这样（不过这样写的话，运算更复杂）

 在这个问题中我们可以一直调用同一个函数来不断地重复来达成目的，所以我们考虑递归的方法，并递归至可以n=1的时候，来反退回去。