相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、 由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在 移动过程中三根杆上都始 终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
因为无法直接从题目中获得思路,所以采用数学归纳法进行推导
让n为当前层数上的圆盘编号,当 n=1
的时候:
圆盘1
直接从 A
到 C
当 n=2
的时候:
圆盘1
需要从 A
到 B
圆盘2
需要从 A
到 C
圆盘1
需要从 B
到 C
其中 B
作为中间柱被使用过一次
当 n=n
的时候(将 n-1
看为一个整体):
A. A
上的 n-1
个圆盘需要从 A
移动到 B
(借助于 C
)
圆盘n
需要从 A
到 C
C. B
上的 n-1
个圆盘需要从 B
到 C
(借助于 A
)
当步骤为A的时候:
1. 将 A
上的 n-2
个圆盘移到 C
上。
2. 将 A
上的第 n-1
个圆盘移到 B
。
3. 将 C
上的 n-2
个圆盘移到 B
。
当步骤为C的时候:
1. 将 B
上的 n-2
个圆盘移到 A
。
2. 将 B
上的第 n-1
个盘子移到 C
。
3. 将 A
上的 n-2
个圆盘移到 C
。
所以从上面可以分析出来,当n>=2的时候可以分为三个步骤:
(A为初始位置,C为中间位置,B为目的位置) (B为初始位置,A为中间位置,C为目的位置)
可以创建方法:
/** * @param layer 层数 * @param init 初始位置 * @param middle 中间位置 * @param target 目标位置 * @return void */ private static void solve(int layer, String init, String middle, String target) { if (1 == layer) { System.out.printf("%d从%s移动到%s;/n", layer, init, target); } else { solve(layer - 1, init, target, middle); //1. System.out.printf("%d从%s移动到%s;/n", layer, init, target); //2. solve(layer - 1, middle, init, target); //3. } }
System.out.printf("%d从%s移动到%s;/n", layer, init, target);