汉诺塔问题（java）

一、题目描述

        有I、II、III三个底座，底座上面可以放盘子。 初始时， I座上有n个盘子，这些盘子大小各不相同，大盘子在下，小盘子在上，依次排列，如下图1所示。 要求将I座上n个盘子移至III座上，每次只能移动1个，并要求移动过程中保持小盘子在上，大盘子在下，可借座实现移动（不能放在别处或拿在手中）。 编程序输出移动步骤。

 二、解题思路

          这个问题可采用递归思想分析，讲n个盘子由I座移动到III座可以分为三个过程：

1.  将 I 座上最上面的n-1个盘子移动到 II 座上。
2.  再将 I 座上最下面一个盘子移至 II 座。
3.  最后将 II  座上的n-1 个盘子借助 I 座移至 III 座。

        上述过程是把移动n个盘子的问题转化为移动n-1个盘子的问题。 按这种思路， 再将移动n-1个盘子的问题转化为移动n-2个盘子的问题……直至移动1个盘子。

        可以用两个函数来描述上述过程：

        1. 从一个底座上移动n个盘子到另一底座。

        2. 从一个底座上移动 1 个盘子到另一底座。

 三、算法实现

        这里我们柱子的编号用了char， a、b、c 对应 I、II、III  。

package java_code;

public class hanoi {

    // 打印移动过程
    void Move(char chSour, char chDest){
        System.out.println(" Move the top plate of " + chSour + " --> " + chDest);
    }

    // 递归函数,n为在第I个座上的盘子总数，   后三项为座的名字
    void hanoiFun(int n, char I , char II , char III){
        if(n==1)
            Move(I, III);
        else{
            // 先将I座上的n-1盘子移动到II座上
            hanoiFun(n-1, I, III, II);
            // 打印
            this.Move(I, III);
             // 先将II座上的n-1的盘子移动到III座上，完成
             hanoiFun(n-1, II, I, III);
        }
    }

    public static void main(String[] args){
        hanoi han = new hanoi();        
        // 这里我们假设有5个盘子， 三个座分别为a、b、c
        han. hanoiFun(5,'a','b','c'); 
    }    
}

        终端打印输出的过程：

 Move the top plate of a --> c
 Move the top plate of a --> b
 Move the top plate of c --> b
 Move the top plate of a --> c
 Move the top plate of b --> a
 Move the top plate of b --> c
 Move the top plate of a --> c
 Move the top plate of a --> b
 Move the top plate of c --> b
 Move the top plate of c --> a
 Move the top plate of b --> a
 Move the top plate of c --> b
 Move the top plate of c --> a
 Move the top plate of b --> a
 Move the top plate of b --> c
 Move the top plate of a --> c
 Move the top plate of a --> b
 Move the top plate of c --> b
 Move the top plate of a --> c
 Move the top plate of b --> a
 Move the top plate of b --> c
 Move the top plate of a --> c