算法(9)汉诺塔图解及其代码实现

算法(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);
    }
}

代码执行结果:

玩汉诺塔,请输入圆盘的个数:31: 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)利用循环法和辗转相除法求 最大公约数和最小公倍数

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/16138.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信