目录

汉诺塔

汉诺塔的传说

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 https://gitee.com/lienhui68/picStore/raw/master/null/20200618192448.png 假如每秒钟一次,共需多长时间呢?移完这些金片需要5845.54亿年以上,太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年,地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

解题思路

换一种问题描述:有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问该如何移动 分析问题 当只有两个盘子时,我们先移动小盘到B,再将大盘移动到C,再将小盘移动到C。 假设有n个盘子,我们使用分治的思想处理这个问题,把上面n-1个盘子当成1个盘子,这样我们就可以按照处理2个盘子的方式处理这n-1个盘子。先移动上面n-1个盘子到B,再移动最后一个盘子到C,再将B上面的n-1个盘子移动到C,很明显使用递归就可以处理了。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package com.eh.ftd.dsa.ds.impl;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/18 19:28
 */
public class Hanoi {

    // 移动次数
    static int count = 0;

    /**
     * 打印移动过程
     *
     * @param n 盘子数量
     * @param a 起始柱子
     * @param b 辅助柱子
     * @param c 目标柱子
     */
    private static int processHanoi(int n, char a, char b, char c) {

        if (n == 1) {
            System.out.println(a + "-> " + c);
            count++;
        } else {
        	// n-1个盘子(也就是上面的盘子)从a移动到b
            processHanoi(n - 1, a, c, b);
            // 将第n个盘子从a移动到c
            System.out.println(a + "-> " + c);
            count++;
            // n-1个盘子(也就是上面的盘子)从b移动到c
            processHanoi(n - 1, b, a, c);
        }
        return count;
    }

    public static void main(String[] args) {
        int steps = processHanoi(4, 'A', 'B', 'C');
        System.out.printf("共计%d步", steps);
    }
}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200618194853.png