汉诺塔非递归算法.ppt

汉诺塔非 递归算法
汉诺塔
1
什么是汉诺塔问题
汉诺塔问题(又称河内塔问题)是根据一个传说形成的一个问题:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
1. 每次只能移动一个圆盘;
2. 大盘不能叠在小盘上面。
问:如何移?最少要移动多少次?
汉诺塔
2
算法分析
1. n个圆盘的汉诺塔实现过程正好是2的n次幂减一步。
2. 由于第一步肯定是第一类移动,所以循环执行第奇数次时,都是第一类移动。若将三个杆分别编为a、b、c,则第一类移动是从a杆移动到c杆,则当n为奇数时,第一类移动的次序为a到c到b再回到a的循环。当n为偶数时,第一类移动的次序为a到b到c再回到a的循环。
3. 循环执行第偶数次时,都是非第一类移动。比较三个杆的顶端的圆环,将两个顶端较大的圆环中较小的小圆环移动到顶端圆环最大的杆上即可。
汉诺塔
3
算法分析
实现思路:
1、最外层是一个2的n次幂减一的循环。
2、第一类移动的实现:一、可以根据以上的结论及n和循环的次数判断从哪杆移动到哪个杆。二、可以记录第一类环的位置结合以上结论确定移动到哪个杆上。三、可以记录第一类环的位置和它前一次所在的位置,剩下的那个杆就是此次移动的目的杆。开始循环前,前一次的初始位置设置为b(n为奇数时)或c(n为偶数时)。
3、非第一类移动的实现:一、可以取出三个杆上最上层的圆环,比较出大小,将第二大的圆环移动到最大圆环所在的杆即可。二、如果记录了第一类环的位置的话,只需取出剩余两个杆最上层的圆环,比较一次,将较小的圆环移动到较大的环所在的杆上即可。
汉诺塔
4
实现代码
#include <iostream>
using namespace std;
//圆盘的个数最多为64
const int MAX = 64;
//用来表示每根柱子的信息
struct st
{
int s[MAX]; //柱子上的圆盘存储情况
int top; //栈顶,用来最上面的圆盘
char name; //柱子的名字,可以是A,B,C中的一个
int Top()//取栈顶元素
{
return s[top];
}
int Pop()//出栈
{
汉诺塔
5
{
return s[top--];
}
void Push(int x)//入栈
{
s[++top] = x;
}
} ;
long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数
int main(void)
{
int n;
汉诺塔
6
cin >> n; //输入圆盘的个数
st ta[3]; //三根柱子的信息用结构数组存储
Creat(ta, n); //给结构数组设置初值
long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
Hannuota(ta, max);//移动汉诺塔的主要函数
system("pause");
return 0;
}
void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
汉诺塔
7
for (int i=0; i<n; i++)
ta[0].s[i] = n - i;
//柱子B,C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n为偶数,按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n为奇数,按顺时针方向依次摆放 A C B
{
ta[1].name = 'C';
ta[2].name = 'B';
}
}
汉诺塔
8
long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x;
return sum;
}
void Hannuota(st ta[], long max)
{
int k = 0; //累计移动的次数
int i = 0;
int ch;
while (k <