递归实现与main():
/*------------------------------------------------------
汉诺塔主要是有三个塔座X,Y,Z,要求将从小到大编号为 1,2.....n 的
圆盘从X移动到塔座Z上,要求
(1):每次只能移动一个圆盘
(2):圆盘可以插到X,Y,Z中任一塔座上
(3):任何时候不能将一个较大的圆盘压在较小的圆盘之上
初始:所有圆盘都在 X 塔座,并且最大的圆盘在最底部,然后是次大的;
结束:所有圆盘都在 Z 塔座,并且最大的圆盘在最底部,然后是次大的;
------------------------------------------------------*/
#include <iostream>
#include <ctime> // time()
using namespace std;
/*-----------------------------------------------------------
前置条件: n > 0
后置条件: 输出将n个圆盘从源塔座(orig)移动到目的塔座(dest)的步骤,
临时塔座(temp)用于临时存放。
算法(递归):
n == 1时,把盘1从源移动到目的地
n > 1时,
1)将n-1个圆盘(每次移动一个)从源移动到临时塔座
2)将盘n从源移动到目的地
3)将n-1个圆盘(每次移动一个)从临时塔座移动到目的塔座
时间复杂度: wotstTime(n) 是 O(2^n).
空间复杂度: worstSpace(n) 是 O(n).
-----------------------------------------------------------*/
void move(int n, char orig[], char dest[], char temp[])
{
static char ori = 'X', tem = 'Y', des = 'Z', ch; // 三个塔座
static int num = 0, length = n; // num记录移动步数, length保存圆盘数目
if (n <= 0){ // 处理参数传递错误
cout << "The value is error!\n";
return;
}
if (n == 1){ // 通用策略: n == 1时情况
dest[n-1] = orig[n-1];
num++;
cout << num << ") Disc " << orig[n-1] << ": "
<< ori << "-->" << des << endl;
}
else{ // 通用策略: n > 1时情况
ch = des; des = tem; tem = ch;
move(n-1, orig, temp, dest);
ch = des; des = tem; tem = ch;
dest[n-1] = orig[n-1];
num++;
cout << num << ") Disc " << orig[n-1] << ": "
<< ori << "-->" << des << endl;
ch = ori; ori = tem; tem = ch;
move(n-1, temp, dest, orig);
ch = ori; ori = tem; tem = ch;
}
if (dest[length] != '\0')
dest[length] = '\0';
}
// move中声明的局部变量为静态的,这样在使用递归调用的move函数里只在第一次定义时初始化;
// 塔座名ori、tem、des要随着递归调用时参数的传递而变化,递归调用结束后应该及时恢复;
// n为圆盘数目,塔座结构采用C-styel字符串,因注意字符串末尾要有'\0';
void movecopy(int, char [], char [], char []);
int main()
{
long start_time, finish_time, elapsed_time1, elapsed_time2;
const int N = 5; // 圆盘数目为 N-1
char orig[N] = "abcd", temp[N], dest[N];
// 计算move()函数运行了多少时间(time()的返回值类型为long)
cout << "move::orig = " << orig << endl;
start_time = time(NULL);
move(N-1, orig, dest, temp);
finish_time = time(NULL);
elapsed_time1 = finish_time - start_time;
cout << "move::dest = " << dest << endl << endl;
// 计算movecopy()函数运行了多少时间
cout << "movecopy::orig = " << orig << endl;
start_time = time(NULL);
movecopy(N-1, orig, dest, temp);
finish_time = time(NULL);
elapsed_time2 = finish_time - start_time;
cout << "movecopy::dest = " << dest << endl << endl;
// move()和movecopy()运行时间比较
cout << "move::The elapsed time was " << elapsed_time1
<< " senonds." << endl;
cout << "movecopy::The elapsed time was " << elapsed_time2
<< " senonds." << endl;
return 0;
}
迭代实现:
/*-------------------------------------------------------------- 前置条件: n > 0 后置条件: 输出将n个圆盘从源塔座(orig)移动到目的塔座(dest)的步骤, 临时塔座(temp)用于临时存放。 算法(迭代): 1)确定哪一个圆盘要移动。 a.移动次数: c(n) = 2^n -1; b.m为n位的二进制数,则m的取值范围为0~2^n -1。 规律:让m每次递增1,可以发现,m中最高一位的刚刚由0变为1的位置的位置编号, 和即将要移动的盘子编号有确定关系。 2)这个盘子往哪个塔座上移动。 a.n为奇数时,奇数编号圆盘按顺时针移动(X->Y->Z->X),偶数编号圆盘按逆时针 移动(X->Z->Y->X); b.n为偶数时,偶数编号圆盘按顺时针移动(X->Y->Z->X),奇数编号圆盘按逆时针 移动(X->Z->Y->X); --------------------------------------------------------------*/ void movecopy(int n, char orig[], char dest[], char temp[]) { char ori[] = "orig(X)", tem[] = "temp(Y)", des[] = "dest(Z)";// 三个塔座 int num = 0; // num记录移动步数 int m1[32], m2[32], tempnum, i, j, k; // m1、m2数组存储 n的二进制bit位,且 n(m2对应) = n(m1对应) + 1; // i、j分别为m1、m2中存储n值要求的二进制的最小bit数; // k+1 为求得的盘子编号 int x = n, y = 0, z = 0; // x、y、z分别跟踪三个塔座当前的圆盘数目 if (n == 0){ // 处理参数传递错误 cout << "The value is error!\n"; return; } // 保存orig中元素到ch[32],然后反转orig塔座中圆盘的顺序 // (如:'a'在orig中第一个位置,但是 'a' 也在塔座的最上方--第n-1个位置) char ch[32]; for (i = 0; i < n; i++) ch[i] = orig[i]; for (int length = n-1, i = 0; i < n; i++, length--){ orig[i] = ch[length]; } ch[n] = '\0'; dest[n] = '\0'; temp[n] = '\0'; for (int l = 0; l < (1<<n)-1; l++) // 移动次数:2^n-1 既是 (1<<n)-1 { // 1)确定哪一个圆盘要移动(求 k+1 的值) tempnum = l; for (i = 0; tempnum != 1 && tempnum != 0; i++) {m1[i] = tempnum%2; tempnum = tempnum/2;} m1[i] = tempnum; tempnum = l+1; for (j = 0; tempnum != 1 && tempnum != 0; j++) {m2[j] = tempnum%2; tempnum = tempnum/2;} m2[j] = tempnum; if (j > i) k = j; else for (k = j; m2[k] == m1[k]; k--) ; num++; cout << num << ") Disc " << ch[k] << ": "; // 2)这个盘子往哪个塔座上移动。 if (((n % 2 == 0 && ((k+1)%2 == 0))) || // (n为偶数,偶数编号圆盘顺时针移动) ((n % 2 != 0) && ((k+1)%2 != 0))){ // (n为奇数,奇数编号圆盘顺时针移动) for (i = 0; ch[k] != orig[i] && i < x; i++) ; if ((i > 0 && i < x) || (i == 0 && orig[i] == ch[k])){ dest[y] = orig[i]; y++; x--; cout << ori << "-->" << des; orig[i] = '\0'; } else{ // (如果在orig塔座没有找到需要圆盘) for (i = 0; ch[k] != dest[i] && i < y; i++) ; if ((i > 0 && i < y) || (i == 0 && dest[i] == ch[k])){ temp[z] = dest[i]; z++; y--; cout << des << "-->" << tem; dest[i] = '\0'; } else{ // (如果在orig和dest塔座都没有找到需要圆盘) for (i = 0; ch[k] != temp[i] && i < z; i++) ; if ((i > 0 && i < z) || (i == 0 && temp[i] == ch[k])){ orig[x] = temp[i]; x++; z--; cout << tem << "-->" << ori; temp[i] = '\0'; } } } } else{ // (n为奇数,偶数编号圆盘逆时针移动)(n为偶数,奇数编号圆盘逆时针移动) for (i = 0; ch[k] != orig[i] && i < x; i++) ; if ((i > 0 && i < x) || (i == 0 && orig[i] == ch[k])){ temp[z] = orig[i]; z++; x--; cout << ori << "-->" << tem; orig[i] = '\0'; } else{ // (如果在orig塔座没有找到需要圆盘) for (i = 0; ch[k] != dest[i] && i < y; i++) ; if ((i > 0 && i < y) || (i == 0 && dest[i] == ch[k])){ orig[x] = dest[i]; x++; y--; cout << des << "-->" << ori; dest[i] = '\0'; } else{ // (如果在orig和dest塔座都没有找到需要圆盘) for (i = 0; ch[k] != temp[i] && i < z; i++) ; if ((i > 0 && i < z) || (i == 0 && temp[i] == ch[k])){ dest[y] = temp[i]; y++; z--; cout << tem << "-->" << des; temp[i] = '\0'; } } } } cout << endl; } // 保存dest中元素到ch[32],然后反转dest塔座中圆盘的顺序 for (i = 0; i < n; i++) ch[i] = dest[i]; for (int length = n-1, i = 0; i < n; i++, length--){ dest[i] = ch[length]; } }
运行结果:
我把main()中变动为 const int N = 15; 时,move()运行了 44 seconds,而movecopy()运行了 80 seconds..
这个递归版本明显好于迭代版本