汉诺塔递归算法.docx

文档介绍：汉诺塔递归栈
问题抽象
3 个塔， n 个碟子
初始：所有碟子放在 1 号塔，大的在底下，小的在上面任务：
把碟子移动到 2 号塔，顺序不变，可用 3 号塔辅助 限制
每次只能移动一个碟子
总是人碟子在下，小的在上
汉诺塔递归栈
问题抽象
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. FIRS、TSECOND
活动记录的一部分，与参数、局部变量一同压栈、出栈在循环
主体中，根据当前活动记录的入I I 值，执行不同代码汉诺塔
的递归栈实现
#include <>
#include <>
#include <>
#inelude <iostream>
#inelude <stack>
using namespace ::std;
enum {
ENTRANCE = 0,
FIRST
SECOND
};
struct ac {
int nzx, 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 (