汉诺塔递归算法分析和理解

问题描述：

• 古代有一个梵塔，塔内有三个座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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！