汉诺塔问题（编程）

题目：汉诺塔问题

1.问题描述

汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。

2.基本要求

(1)设计数据结构，表示三座宝塔和n个盘子；

(2)输出每一次移动盘子的情况；

(3)分析算法的时间性能。

3.设计思想

对于汉诺塔问题的求解，可以通过以下三个步骤实现：

(1)将塔A上的n-1个碟子借助塔C先移到塔B上。

(2)把塔A上剩下的一个碟子移到塔C上。

(3)将n-1个碟子从塔B借助于塔A移到塔C上。

显然，这是一个递归求解的过程，当n=3时的求解过程如图所示。

三座宝塔（塔A、塔B、塔C）分别用三个字符A,B,C来表示，n个盘子用从1开始的连续自然数编号。具体算法如下：

c)把塔A上剩下的一个碟子移到塔C上(d)把n-1个碟子从塔B移到塔C

图 汉诺塔求解示意图

汉诺塔算法Hanoi

void Hanoi( int n, char A, char B, char C)

{

if (n = = 1) cout<<“A→C”； //将碟子从A移到C上

else {

Hanoi (n-1,A,C,B);

cout<<“A→C”；

Hanoi (n-1,B,A,C);

}

}

1个盘子移动1次.

2个盘子移动3次.

3个盘子移动7次......

所以移动次数就是2^n-1. 时间复杂度就是O(2^n);

具体代码如下:

#include<iostream>
using namespace std;

int N=0;

void Hanoi( int n, char A, char B, char C)
{
if(n==1)
{
cout<<"第"<<++N<<"步"<<": 移动第"<<n<<"个盘子从"<<A<<"到"<<C<<endl;
}
else
{
Hanoi(n-1,A,C,B);
cout<<"第"<<++N<<"步"<<": 移动第"<<n<<"个盘子从"<<A<<"到"<<C<<endl;
Hanoi(n-1,B,A,C);
}
}
int main()

{
int n;
cout<<"请输入数字n以解决n阶汉诺塔问题：";
cin>>n;
Hanoi(n,'A','B','C');
cout<<"\n共需 "<<N<<"次移动盘子!"<<endl;
return 0;
}

#include<stdio.h> void move(char x,int n,char z) { //int c; printf("move disk %i from %c to %c\n",n,x,z); } void hanio(int n,char x,char y, char z) { if(n==1) move(x,1,z); else { hanio(n-1,x,z,y);//把n-1个盘子借助z柱子从x柱子移动到y柱子上去 move(x,n,z);//把第n个盘子从x柱子移动到z柱子上去 hanio(n-1,y,x,z);//把n-1个盘子借助x柱子移动到z柱子上去 } } int main() { int n; scanf("%d",&n);//请你输入盘子的个数，建议不要输入太大！ hanio(n,'a','b','c'); system("PAUSE"); return 0; }

在给你点建议，你如果你看懂了 你不防不使用递归，用迭代来做哈呢？

题目不是已经给出了程序了么？

只是输出结果不正确，需要做一点小修改：

void Hanoi( int n, char A, char B, char C)

{

if (n = = 1) cout<<A<<"→”<<C； //将碟子从A移到C上

else {

Hanoi (n-1,A,C,B);

cout<<A<<“→”<<C；

Hanoi (n-1,B,A,C);

}

}