汉诺塔算法问题

梦里梦外; 2022-05-09 06:06 169阅读 0赞

## 问题描述 ##

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

![70][]

## 问题分析 ##

对n个盘子分析的话，可以将分为两部分，一部分是上面的n-1个作为整体的这部分（忽略此整体自身的递归形成过程），另一部分是最下面的第n个盘子。

接下来简化该问题，大概分为三步：

step1：将n-1个盘子的整体从A移动到缓冲区B中；

step2：接着将第n个盘子从A移动到C中；

step3：将n-1个盘子的整体从缓冲区B移动到C中。

如下图所示：

![70 1][]

## 算法实现 ##

import java.util.Scanner;
    
    public class TestHanoi {
    
        static long moveCount = 0;
        public static void main(String[] args) {
            char src = 'a';
            char tmp = 'b';
            char dst = 'c';
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); // 需要移动的盘子总数n
            hanoi(n, src, tmp, dst);
            sc.close();
            System.out.printf("移动次数统计：%d", moveCount); // 2的n次方-1
        }
        
        /**
         * 将号码为number的盘子直接从柱子src放到dst
         * @param number
         * @param src
         * @param dst
         */
        static void move(int number, char src, char dst) {
            moveCount++;
            System.out.printf("将%d 号盘子从柱子%s 移动到%s 上\n", number, src, dst);
        }
        
        /**
         * 将n个盘子从柱子a经过b最终放到c
         * @param n
         * @param a
         * @param b
         * @param c
         */
        static void hanoi(int n, char a, char b, char c) {
            if (n == 0) {
                return;
            } else {
                hanoi(n-1, a, c, b); // step1
                move(n, a, c); // step2
                hanoi(n-1, b, a, c); //step3
            }
        }
    }

[70]: /images/20220509/906dc10b7dfc45db865228a66f623e37.png
[70 1]: /images/20220509/cecc7e9309824e9b93a475999651d6f3.png