【一起来刷Python题】——14.解决“汉诺塔”问题

【一起来刷Python题】——14.解决“汉诺塔”问题

⭐刷Python算法题第14天，终于对未来有了认识——全栈工程师，可能是一个不错的选择，但是需要不少的努力…⭐

问题描述：寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚把这64个盘子全部移动到第三根柱子上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一次。

程序代码：

def move(n, a, buffer, c):
    if n == 1:
        print(a, "->", c)
        return
    move(n-1, a, c, buffer)
    move(1, a, buffer, c)
    move(n-1, buffer, a, c)
move(64, 'a', 'b', 'c')

程序分析：

n ：代表a柱子上的盘子个数；a ：就是a柱；buffer ：就是b柱，命名为buffer便于理解，顾名思义，就是一个从a移动到c的缓冲区；c ：就是c柱，也就是目标柱子。

 1）小和尚A1在移动时，找来小和尚A2来帮忙，希望A2有如下 *** 作：①A2把前63个盘子移动到第二根柱子上；②A1自己把第64个盘子移动到第三根柱子上；③A2把前63个盘子移动到第三根柱子上。
2）小和尚A2找到小和尚A3帮忙，希望A3有如下 *** 作：①A3把前62个盘子移动到第三根柱子上；②A2自己把第63个盘子移动到第二根柱子上；③A3把前62个盘子移动到第二根柱子上。
3）小和尚A3又找到小和尚A4帮忙，依次递推，直到小和尚A63将任务交给了小和尚A64。
4）此时此刻，只需各自完成各自的工作即可。而且，如果被要求帮忙的人不完成，则需要帮忙的人，无法完成，则必须从A64开始。
我们以三个盘子分析：
第一个小和尚命令：
Ⅰ.第2个小和尚先把第一根柱子上前2个盘子移动到第二根柱子，借助第三根；
Ⅱ.第1个小和尚自己把第一根柱子最后的盘子移动到第三根柱子；
Ⅲ.第2个小和尚把前2个盘子从第二根柱子移动到第三根柱子。
非常显然，第Ⅱ步很容易实现。
其中第Ⅰ步，第2个小和尚有2个盘子，他就命令：
①第3个小和尚把第一根柱子第1个盘子移动到第三根柱子，借助第二根；
②第2个小和尚自己把第一根柱子第2个盘子移动到第二根柱子上；
③第3个小和尚把第1个盘子从第三根柱子移动到第二根柱子。
同样，第②步很容易实现，但第3个小和尚只需要移动1个盘子，所以无须再下派任务(注意：这就是停止递归的条件，也叫边界值)。
第Ⅲ步可以分解为，第2个小和尚还有2个盘子，于是命令：
①第3个小和尚把第二根柱子上的第1个盘子移动到第一根柱子；
②第2个小和尚把第2个盘子从第二根柱子移动到第三根柱子；
③第3个小和尚把第一根柱子上的盘子移动到第三根柱子。
        分析组合起来就是：1->3,1->2,3->2,借助第三根柱子将第一根柱子的前两个盘子移动到第二根柱子；1->3是留给自己的活；2->1，2->3，1->3是借助别人帮忙。从第一根柱子移动到第三根柱子需要7步来完成。
        如果是4个盘子，则第一个小和尚的命令第Ⅰ步和第Ⅲ步各有3个盘子，所以需要7步，共14步，再加上第一个小和尚的第Ⅱ步，所以4个盘子总共需要移动7+1+7=15步；同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步…由此可以知道，移动n个盘子需要(-1)步。