博客

问题描述：

• 古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下， 小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。

• 汉诺塔是一个对称的递归，最底层那一片将次数划分成两半
  
  1盘：1次
  
  2盘：3次-> 1 1 1
  
  3盘：7次-> 3 1 3
  
  4盘：15次->7 1 7
  
  5盘：31次-> 15 1 15
  
  …
  
  n盘：2^n-1次

• 三条柱子（规定），否则不是汉诺塔(原题是64个盘片)

// 递归过程分析
						A(61)->B(61)|
						A(1)->C(1)	|	...
						B(61)->C(61)|
						/
			A(62)->C(62)|
			A(1)->B(1)  |
			C(62)->B(62)|
			/			\C(61)->A(61)|
A(63)->B(63)|			 C(1)->B(1)	 |	...
A(1)->C(1)  |			 A(61)-B(61) |
B(63)->C(63)|
			\			 B(61)->C(61)|
			 \			/B(1)->A(1)  |	...
			B(62)->A(62)|C(61)->A(61)|
			B(1)->C(1)	|
			A(62)->C(62)|
						\A(61)->B(61)|
						 A(1)->C(1)  |	...
						 B(61)->C(61)|
选取三个盘片分析，最终会递归到移动一个盘片：
					A(1)->C(1)|
					A(1)->B(1)|
					C(1)->B(1)|
					/			
第一步： A(2)->B(2)|			    
第二步： A(1)->C(1)|			
第三步： B(2)->C(2)|
					\			
					B(1)->A(1)|
					B(1)->C(1)|
					A(1)->C(1)|
总共七步：A->C,A->B,C-B,A->C,B->A,B->C,A->C

明确开始是from，结束时to，中间是inter

• 理解重点：
  • 首先是递归知识点
  • 代码设计采用错开的方式交替，如上面的递归过程分析：盘片的移动总共有第三步，调用递归过程主要是
    
第一步

    和
    
第三步

    :
    • 第一步：总是从A柱移动到B柱和C柱，B、C两柱的作为中间缓存（inter）交替进行，代码设计的时候要注意错位。
    • 第三步：总是从A、B两柱缓存（inter）将盘片移动到C柱，A、B两柱子随着递归调用交替进行，代码设计的时候要注意错位。
• 结合下面的java代码和C代码理解更加透彻：
• java 描述

public class HanoiTower {
   

    /**     
     * @description 在程序中，我们把最上面的盘子称为第一个盘子，把最下面的盘子称为第N个盘子
     * @author toohoo
     * @param level：盘子的个数
     * @param from 盘子的初始地址
     * @param inter 转移盘子时用于中转
     * @param to 盘子的目的地址
     */

     public static