算法题--汉诺塔

### 题目：

有三根杆，编号x,y,z，在x杆上自下而上、由大到小顺序放置着n个盘子，请问怎样能将所有盘子从x杆移动到z杆？

要求移动过程中每次只能移动一个盘子，且三根杆上的盘子要始终保持大盘在下，小盘在上（意思就是每次只能移动一个，并且只能将小盘放在比他大的盘子上）

![](http://minio.riun.xyz/riun1/2022-02-25_2axTJYcvwNODF3WfGe.jpg)

### 思路：

这类问题一看就是一个规律题，我们首先要从最简单的场景寻找它的规律。

如果只有2个盘子，小的是1，大的是2。三根柱子分别是x,y,x。
移动过程：
1、1从x移动到y
2、2从x移动到z
3、1从y移动到z

将上述的1看成是前n-1个, 2看成是第n个，带入有3个盘子时的移动过程：

1、1从x-->z
2、2从x-->y
3、1从z-->y //到这里是前n-1从x移动到y
4、3从x-->z //这一步是第n个从x移动到z
5、1从y-->x
6、2从y-->z
7、1从x-->z //后面这几步是前n-1个从y移动到z

为什么能这样分？

因为第n个是最大的，而最大的能承载所有其余盘子，所以第n个能做为一个分界点。摆正了它的位置，后面移动过程中就不用动它了。
然后前面的n-1个又能找出第n-1大的盘子，作为剩余这些盘子中最大的，移动到z。所以就造就了这个递归循环。

> 分治思想

### 代码：

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/25
 * Class description: 汉诺塔：有三根杆，编号x,y,z，在x杆上自下而上、由大到小顺序放置着n个盘子，请问怎样能将所有盘子从x杆移动到z杆？
 * 要求移动过程中每次只能移动一个盘子，且三根杆上的盘子要始终保持大盘在下，小盘在上（意思就是每次只能移动一个，并且只能将小盘放在比他大的盘子上）
 *
 */
public class HanoiDemo {
    
    public static void main(String[] args) {
        hanoi(3, 'x', 'y', 'z');
    }

public static void hanoi(int n, char x, char y, char z) {
        //将问题分为两个：1、如果只有1个盘子 2、如果不止一个盘子
        if (n == 1) {
            System.out.println(x + "-->" + z);
        } else {
            //如果盘子数大于1，那么分三步走：
            //1、将前n-1个盘子从x移动到y
            hanoi(n - 1, x, z, y);
            //2、将第n个盘子从x移动到z
            System.out.println(x + "-->" + z);
            //3、将剩余n-1个盘子从y移动到z
            hanoi(n - 1, y, x, z);
        }
    }
}

/*
如果只有2个，小的是1，大的是2.三根柱子分别是x,y,x
移动过程：
1、1从x移动到y
2、2从x移动到z
3、1从y移动到z

将上述的1看成是前n-1个, 2看成是第n个

代码中n为3时的移动过程：
x-->z
x-->y
z-->y //到这里是前n-1从x移动到y
x-->z //这一步是第n个从x移动到z
y-->x
y-->z
x-->z //后面这几步是前n-1个从y移动到z

为什么能这样分？因为第n个是最大的，而最大的能承载所有其余盘子，所以第n个能最为一个分界点，摆正它的位置，而后面移动过程中不用动。
然后前面的n-1个又能找出第n-1大的盘子，作为这些盘子中最大的，移动到z。所以就造就了这个递归循环。
 */
/*
x-->z
x-->y
z-->y
x-->z
y-->x
y-->z
x-->z
 */
```

文章目录

发表评论