- package com.wy.test;
- /*
- 汉诺塔问题描述：
- 假设有三个命名为X（TOWER 1),Y(TOWER 2),Z(TOWER 3)的塔座，
- 在塔座X上有n个直径大小各不相同，依次从小到大编号为1,2,3,...,n的圆盘。
- 现要求将X塔座上的n个圆盘移到Z塔座上并按同样顺序叠排，
- 圆盘移动时必须遵循下列规则：
- 1）每次只能移动一个圆盘；
- 2）圆盘可以插在X,Y,Z中的任意塔座上；
- 3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
- */
- /*
- 解决思路：
- 我们先考虑最简单的情况,假如只有一个盘子,就直接从origin搬到目的地to。
- 如果两个盘子则是先把小盘子放assist，然后大盘子放to，最后再把assist里的盘子放destination。
- 假如有N个盘子时,我们可以这样想,底下最大的那个我们先不管（因为最大的如果你把它放那不动，
- 则可以无视它的,其他盘子可以在三个柱子上移来移去，它是最大嘛)。
- 于是我们可以先想办法把origin上的N-1个盘子搬到assist上,然后把最大的那个搬destination上，
- 最后再想办法把assist上的N-1个搬到destination上。于是当有盘子3个时，
- 先把上面2个搬到assist上，再把最大那个搬到destination，最后再想办法把assist上的2个搬destination上来。
- */
- public class Hanoi {
- /**
- * @param n
- * 盘子的数目
- * @param origin
- * 源座
- * @param assist
- * 辅助座
- * @param destination
- * 目的座
- */
- public void hanoi(int n,char origin,char assist,char destination) {
- if (n == 1) {
- move(origin,destination);
- } else {
- hanoi(n - 1,origin,destination,assist);
- move(origin,destination);
- hanoi(n - 1,assist,origin,destination);
- }
- }
-
- // Print the route of the movement
- private void move(char origin,char destination) {
- System.out.println("Direction:" + origin + "--->" + destination);
- }
- public static void main(String[] args) {
- Hanoi hanoi = new Hanoi();
- hanoi.hanoi(10,'A','B','C');
- }
- }
|
|
收藏
淘帖
踩
