基于Python的汉诺塔算法

时间:2021-08-04 09:54:29

首先贴出Python编写的汉诺塔算法的代码:

def hanoti(n,x1,x2,x3):
    if(n == 1):
        print('move:',x1,'-->',x3)
        return
    hanoti(n-1,x1,x3,x2)
    print('move:',x1,'-->',x3)
    hanoti(n-1,x2,x1,x3)

hanoti(3,'A','B','C')   

汉诺塔问题归根结底就是一个递归问题,递归包括两大要素:递归体、递归结束条件

首先分析汉诺塔算法的思想:

第一步:若想将n个圆盘中最大的圆盘从A塔放到C塔,需要借助B塔放置其余的n-1个圆盘

第二步:再把B塔看做初始条件时的A塔,将B塔上的n-1个圆盘依据规则放置到C塔上,这一步就是实现一个递归

依据代码来分析:

首先定义函数hanoti(n,x1,x2,x3),该函数作用是将n个圆盘从第一个参数(这里为x1)放到第三个参数(这里为x3)上,

if判断是递归结束条件,意思为若只有一个圆盘,只需要将他从第一个参数(这里为x1)放到第三个参数(这里为x3)上即可,

如果不满足递归结束条件,函数继续执行,

hanoti(n-1,x1,x3,x2)语句就是执行第一步的过程,即将除最大圆盘外的n-1个圆盘从第一个参数(这里为x1)放到第三个参数(这里为x2)上,

然后输出表示移动结束的print语句,

这一句结束后,表示x2上现在放置着所有剩余的n-1个圆盘,

再继续递归hanoti(n-1,x2,x1,x3)语句,执行第二步过程,即将剩余的n-1个圆盘按同样的方法从从第一个参数(这里为x2)放到第三个参数(这里为x3)上

如此循环往复,完成汉诺塔问题