有I、II、III三个底座,底座上面可以放盘子。 初始时, I座上有n个盘子,这些盘子大小各不相同,大盘子在下,小盘子在上,依次排列,如下图1所示。 要求将I座上n个盘子移至III座上,每次只能移动1个,并要求移动过程中保持小盘子在上,大盘子在下,可借座实现移动(不能放在别处或拿在手中)。 编程序输出移动步骤。
这个问题可采用递归思想分析,讲n个盘子由I座移动到III座可以分为三个过程:
- 将 I 座上最上面的n-1个盘子移动到 II 座上。
- 再将 I 座上最下面一个盘子移至 II 座。
- 最后将 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