算法题--汉诺塔 2022-02-25 10:45 ### 题目: 有三根杆,编号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 */ ``` --END--
发表评论