玩转汉诺塔（hanoi）游戏

痛定思痛。 2023-02-21 11:56 13阅读 0赞

## 汉诺塔由来 ##

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

[4399益智小游戏——汉诺塔游戏][4399]

## 游戏描述 ##

有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一一移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，怎么移动？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][2020063016354434.gif]

## 解决思路 ##

①若只有盘子1，则直接将盘子1从A移动到C；  
②若2个盘子，先盘子1从A移动到B，再将盘子2从A移动到C，最后将盘子1从B移动到C；  
③若3个盘子，第1个盘子从A到C，第2个盘子从A到B，第1个盘子从C到B，第3个盘子从A到C，第1个盘子从B到A，第2个盘子从B到C，第1个盘子从A到C；  
④综上，我们不管几个盘子（1个盘子除外），都把盘子记为2个，即：第1个作为一个，下面的n-1个盘子作为一个，那么就可以利用递归求解。

## JAVA实现 ##

**代码如下：**

class TestHanoi 
    { 
    	public static void main(String[] args) 
    	{ 
    		Hanoi(3,'A','B','C');
    	}
    	/** * @param n 共有n个盘子 * @param from 开始的柱子 * @param in 中间的柱子 * @param to 目标柱子 * 无论有多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子。 */
    	public static void Hanoi(int n,char from ,char in,char to)
    	{ 
    		if (n == 1)
    		{ 
    			System.out.println("第1个盘子从"+from+"到"+to);
    		}
    		else
    		{ 
    			Hanoi(n-1,from,to,in);  //移动上面所有的盘子到中间位置
    			System.out.println("第"+n+"个盘子从"+from+"到"+to);
    			Hanoi(n-1,in,from,to);//把上面的所有盘子从中间位置移到目标位置
    		}
    	}
    }

**结果如下：**  
（三个盘子时）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70 1]

[4399]: http://www.4399.com/flash/109504.htm#search3
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630161123473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg==,size_16,color_FFFFFF,t_70
[2020063016354434.gif]: https://img-blog.csdnimg.cn/2020063016354434.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200630163743561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg==,size_16,color_FFFFFF,t_70