打开网易新闻 查看更多视频
用栈替代递归：汉诺塔问题
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子 ，盘子大小不等，大的在下，小的在上（如图）。有一个和尚 想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子 ，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘 在上。在移动过程中可以利用B座，要求输出移动的步骤。
打开网易新闻 查看精彩图片
汉诺塔问题递归解法：
打开网易新闻 查看精彩图片
汉诺塔问题递归解法：
打开网易新闻 查看精彩图片
汉诺塔问题手工解法(三个盘子）：
打开网易新闻 查看精彩图片
汉诺塔问题非递归解法：
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
编译器生成的代码自动维护一个问题的栈，相当于信封 堆。栈里每个子问题的描述中多了一项 --- 返回地址，返 回地址可以描述该子问题已经解决到哪个步骤了，下面 的(0) (1),(2),(3)就是返回地址。
汉诺塔问题递归解法：
打开网易新闻 查看精彩图片
汉诺塔问题递归解法：
打开网易新闻 查看精彩图片
热门跟贴