使用递归实现汉诺塔来理解分治算法

分手后的思念是犯贱 2023-06-14 09:30 33阅读 0赞

# 分治算法 #

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治算法一般分为三个步骤：

1.  分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2.  解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3.  合并：将各个子问题的解合并为原问题的解。

分治(Divide-and-Conquer§)算法设计模式如下：

if |P|≤n0
       then return(ADHOC(P))
    //将P分解为较小的子问题 P1 ,P2 ,…,Pk
    for i←1 to k
    do yi ← Divide-and-Conquer(Pi)   递归解决Pi
    T ← MERGE(y1,y2,…,yk)   合并子问题
    return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC§是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

# 汉诺塔 #

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UsDxqgMC-1574121597533)(/Users/hong/Library/Application Support/typora-user-images/image-20191119075456896.png)\]][img-UsDxqgMC-1574121597533_Users_hong_Library_Application Support_typora-user-images_image-20191119075456896.png]

汉诺塔小游戏：按照原先的大小顺序不变，将A塔的所有盘子移动到C塔，并且三个塔之间一次只能移动一个盘子。

我们可以根据分治算法的思想，将这个游戏按下面的思路来完成：

1.  如果是有一个盘， A->C
2.  如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘  
    a .先把 最上面的盘 A->B
    
    b. 把最下边的盘 A->C  
    c. 把B塔的所有盘 从 B->C

def hannota(num, tower_a, tower_b, tower_c):
        """ :param num: 盘子的数量 :param tower_a: 盘子移动前所处的塔 :param tower_b: 需要借助的塔 :param tower_c: 盘子移动的目标塔 :return: """
    
        # 如果只有一个盘子，直接从tower_a移动到tower_c即可
        if num == 1:
            print('盘子%d：%s -> %s' % (num, tower_a, tower_c))
        else:
            # 如果有多个盘子，可以看成两个盘子：最下面的一个盘子、上面的所有盘子
    
            # 第一步：将上面的所有盘子从tower_a移动到tower_b
            hannota(num - 1, tower_a, tower_c, tower_b)
    
            # 第二步：将最下面的盘子从tower_a移动到tower_c
            print('盘子%d：%s -> %s' % (num, tower_a, tower_c))
            
            # 第三步：将上面的所有盘子从tower_b移动到tower_c
            hannota(num - 1, tower_b, tower_a, tower_c)
    
    
    if __name__ == '__main__':
        hannota(5, 'A', 'B', 'C')

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114546699.jpg]

[img-UsDxqgMC-1574121597533_Users_hong_Library_Application Support_typora-user-images_image-20191119075456896.png]: https://img-blog.csdnimg.cn/20191119080029610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ==,size_16,color_FFFFFF,t_70
[20200430114546699.jpg]: https://img-blog.csdnimg.cn/20200430114546699.jpg