汉诺塔递归算法.doc

文档介绍：
问题抽象
3个塔，n个碟子
初始：所有碟子放在1号塔，大的在底下，小的在上面 任务：把碟子移动到2号塔，顺序不变，可用3号塔辅助 限制
每次只能移动一个碟子
总是人碟子在下，小的在上
递归解法
移动碟子的方法：move(n, tl, t2, t3)
将n个碟子从tl移到t2, t3辅助
可分解为3个步骤
将 n-l 个碟子从 tl 移到 t3： move(n-l, tl, t3, t2)
将最大的碟子从tl移到t2
将 n-l 个碟子从 t3 移到 t2： move(n-l, t3, t2, tl) 汉诺塔递归程序
void TowersOfHanoifint n, int x, int y, int z)
{// Move the top n disks from tower x to tower y.
// Use tower z for intermediate storage.
if (n > 0) {
TowersOfHanoi(n-l, x, z, y);
cout« "Move top disk from tower" « x
« " to top of tower " « y « endl;
TowersOfHanoi(n-l, z, y, x);}
}
moves(n)=2n-l 最少次数，@(2n)
一般递归程序转换为循坏
递归函数主体的转换 转换为循环，while(l)即可 递归调用的转换
将当前参数、局部变量…(活动记录)压栈
参照调用方式改变参数，继续循环 函数执行结束一一递归返回的处理 若栈空，整个递归过程结束，跳出循环 否则，将调用者的活动记录弹出栈，恢复其坏境，继续循坏 递归函数不同入口的区分一一返回地址的处理
上例：ENTRANCE. FIRST、SECOND
活动记录的一部分，与参数、局部变量一同压栈、出栈 在循环主体中，根据当前活动记录的入I I值，执行不同代码 汉诺塔的递归栈实现
#include <>
#include <>
#include <>
#inelude <iostream>
#inelude <stack>
using namespace ::std;
enum {
ENTRANCE = 0,
FIRST
SECOND
};
struct ac {
int nz x, y, z;
int r;
};
汉诺塔的递归栈实现
void hanoi(int n, int x, int y, int z)
{
stack<struct ac> stack;
struct ac ac = { n, x, y, z, ENTRANCE };
while (1)
{
if ( <= 0)
{
if (())
break;
ac = ();
();
if (== ENTRANCE)