算法（9）汉诺塔图解及其代码实现

大家好，欢迎来到IT知识分享网。

写在前面： 我是「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。技术是开源的、知识是共享的。

这博客是对自己学习的一点点总结及记录，如果您对 Java、算法 感兴趣，可以关注我的动态，我们一起学习。

用知识改变命运，让我们的家人过上更好的生活。

相关文章

点此查看 【算法系列】 博客文章

一、什么是汉诺塔

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

二、汉诺塔移动过程

汉诺塔动画： 演示圆盘移动过程

（此动图来源于网络）

下面分三种情况分别演示每个盘子的移动过程（n 代表圆盘数量）：

1个圆盘的情况：

2个圆盘的情况：

3个圆盘的情况：

三、汉诺塔算法思想

当 n 等于 1 的时候，直接把圆盘从 A 移动到 C；

当 n > 1 的时候：

• 把 A 柱子上面的 (n-1) 个盘子，从 A 移动到 B；

• 把 A 柱子上面的第 n 个盘子由 A 移动到 C；

• 把第一步 B 柱子上的 (n-1) 个盘子由 B 移动到 C

在算法的实现过程中，我们利用递归的思想。来模拟移动过程以及总共移动的次数。

1.示例代码

public class Hanoi { 
   

    /** * 移动的次数 */
    static int m = 0;

    public static void main(String[] args) { 
   
        Scanner input = new Scanner(System.in);
        System.out.print("玩汉诺塔，请输入圆盘的个数：");
        int n = input.nextInt();
        char a = 'A';
        char b = 'B';
        char c = 'C';
        
        hanoi(n, a, b, c);
        
        System.out.println("把A上的圆盘都移动到了C上，总共移动了" + m + "次。");
    }

    /** * 汉诺塔 * * @param n 盘子的数量 * @param a 柱子 A * @param b 柱子 B * @param c 柱子 C */
    public static void hanoi(int n, char a, char b, char c) { 
   
        if (n == 1) { 
   
            move(1, a, c);
        } else { 
   
            // 递归 把A柱子上面的n-1层，从A，经C，到B
            hanoi(n - 1, a, c, b);
            move(n, a, c);
            // 递归 把B柱子上的n-1层，从B，经A，到C
            hanoi(n - 1, b, a, c);
        }
    }

    /** * 移动 * * @param n 圆盘的个数 * @param i 移动前的位置 * @param j 移动后的位置 */
    public static void move(int n, char i, char j) { 
   
        m++;
        System.out.println("第" + m + "次: " + n + "号圆盘: " + i + " -> " + j);
    }
}

代码执行结果：

玩汉诺塔，请输入圆盘的个数：3
第1次: 1号圆盘: A -> C
第2次: 2号圆盘: A -> B
第3次: 1号圆盘: C -> B
第4次: 3号圆盘: A -> C
第5次: 1号圆盘: B -> A
第6次: 2号圆盘: B -> C
第7次: 1号圆盘: A -> C
把A上的圆盘都移动到了C上，总共移动了7次。

2.延伸问题

如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，需要多少长时间？

1个圆盘的时候，2的1次方减1
2个圆盘的时候，2的2次方减1
3个圆盘的时候，2的3次方减1
4个圆盘的时候，2的4次方减1
…
n个圆盘的时候，2的n次方减1

当 n=64的时候是（2的64次方减1）次。

代码示例：

public class Test { 
   
    public static void main(String[] args) { 
   
        double a = Math.pow(2, 64) - 1;
        System.out.println("2^64-1的值： " + a);
        // 移动一个圆盘需要1秒，一年可以移动b个圆盘
        double b = 60 * 60 * 24 * 365;
        System.out.println("一年时间移动圆盘的个数: " + b);
        // 移动64个圆盘需要的时间
        double time = a / b;
        System.out.println("移动64个圆盘需要的时间: " + time + " 年");
    }
}

代码执行结果：

2^64-1的值： 1.8446744073709552E19
一年时间移动圆盘的个数: 3.1536E7
移动64个圆盘需要的时间: 5.84942417355072E11 年

移动完所有的圆盘大概需要5849亿年，这是一个多么可怕的数字！

上一篇 算法（8）利用循环法和辗转相除法求 最大公约数和最小公倍数