对汉诺塔递归算法的简单理解

用户11305962

发布于 2024-10-09 15:25:05

960

发布于 2024-10-09 15:25:05

文章被收录于专栏：学习

一.历史背景:汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

二.递归算法：这里n，表示总共有几个盘子，a表示当前的塔，b表示中转塔，c表示目标塔,（注意：他们递归时，中转塔会，当前的塔，目标塔会改变）这里用一个静态变量sum，来记住盘子移动的次数。我画了一个图来帮助大家理解。

这里首先分为两种情况：1. 只有一个盘子直接把盘子从A移动到C。2.有很多盘子时（n个），移动盘子的递归思想可以大概直接抽象为：把(n-1)个盘子看作一个整体,借助C塔 从A-->B（具体移动过程中靠函数递归来实现）再把最底部那个盘子，借助B塔从 A-->C。最后把(n-1)个盘子，借助A塔从B-->C

三.具体代码如下：

public class Hanoi {
    public static int sum = 0;
    public static void hanoi(int n, String a, String b, String c) {
        /** n表示总共有几个盘子
         *  a表示当前的塔，b表示中转塔，c表示目标塔,（注意：他们递归时会改变）
         */
        if (n == 1) {
            System.out.println(a + "-->" + c);//每次移动到C塔,SUM来计数
            sum++;
        } else {
            hanoi(n-1, a, c, b );
            System.out.println(a + "-->" + c);
            sum++;
            hanoi(n-1, b, a, c);
        }
    }
    public static void main(String[] args) {
        hanoi(5, "Current", "transfer", "goal");
        System.out.println(sum);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除

变量