Python模拟汉诺塔问题移动盘子的过程

据说古代有一个梵塔，塔内有三个底座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，在移动盘子的过程中可以利用B座，但任何时刻3个座上的盘子都必须始终保持大盘在下、小盘在上的顺序。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C即可。和尚想知道这项任务的详细移动步骤和顺序。这实际上是一个非常巨大的工程，是一个不可能完成的任务。根据数学知识我们可以知道，移动n个盘子需要2^n-1步，64个盘子需要18446744073709551615步。如果每步需要一秒钟的话，那么就需要584942417355.072年。

def hannuo(num, src, dst, temp=None):

    '''把num个盘子从src移动到dst，可以借助临时柱子temp'''

    #声明用来记录移动次数的变量为全局变量

    global times

    #只剩最后或只有一个盘子需要移动，这也是函数递归调用的结束条件

    if num == 1:

        print('The {0} Times move:{1}==>{2}'.format(times, src, dst))

        times += 1

    else:

        #递归调用函数自身

        #先把除最后一个盘子之外的所有盘子移动到临时柱子上

        hannuo(num-1, src, temp, dst)

        #把最后一个盘子直接移动到目标柱子上

        hannuo(1, src, dst)

        #把除最后一个盘子之外的其他盘子从临时柱子上移动到目标柱子上

        hannuo(num-1, temp, dst, src)

#用来记录移动次数的变量

times = 1

#A表示最初放置盘子的柱子，C是目标柱子，B是临时柱子

hannuo(4, 'A', 'C', 'B')

运行结果为：

The 1 Times move:A==>B

The 2 Times move:A==>C

The 3 Times move:B==>C

The 4 Times move:A==>B

The 5 Times move:C==>A

The 6 Times move:C==>B

The 7 Times move:A==>B

The 8 Times move:A==>C

The 9 Times move:B==>C

The 10 Times move:B==>A

The 11 Times move:C==>A

The 12 Times move:B==>C

The 13 Times move:A==>B

The 14 Times move:A==>C

The 15 Times move:B==>C