汉诺塔问题的三种实现
// test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的
//
//递归实现
/*#include "stdafx.h"
#include
using namespace std;
int count=0;//记录移动到了多少步
void Move(int n,char From,char To);
void Hannoi(int n,char From, char Pass ,char To); //把圆盘从From，经过pass,移动到To
int main()
{
int n_count=0;
cout<<"请输入圆盘个数:";
cin>>n_count;
Hannoi(n_count,'A','B','C');
}
void Move(int n,char From,char To)
{
count++;
cout<<"第"< "< } void Hannoi(int n,char From,char Pass,char To) { if(n==1) Move(1,From,To);//哈哈，注意这里的From,已经不等于第一次调用Hannoi的from了，好好体会 else { Hannoi(n-1,From,To,Pass); Move(n,From,To); Hannoi(n-1,Pass,From,To); } }*/ //非递归实现 //非递归实现的算法描述，要通过画图理解 /*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include #include using namespace std; const int MAX=64; //圆盘的个数最多为 //表示每根柱子的信息struct st { int s[MAX]; int top; char name; int Top()//取栈顶元素 { return s[top]; } int Pop()//出栈 { return s[top--]; } void Push(int x)//入栈 { s[++top]=x; } }; void My_Initial(st ta[],long n);//给结构数组设置初始值void Hannoi(st ta[],long Mov_count); int main() { int n; cout<<"请输入圆盘个数："< cin>>n; //输入圆盘的个数 st ta[3];//三根柱子的信息用数据结构数组存储 My_Initial(ta,n);//初始化结构数组 long Mov_count=pow((double)2,n)-1; //移动的次数为^n-1 Hannoi(ta,Mov_count); return 0; } void My_Initial(st ta[],long n) { ta[0].name='A'; ta[0].top=n-1; //开始时圆盘从大到小顺序放在柱子A上 for(int i=0;i ta[0].s[i]=n-i; //柱子B，C上开始没有圆盘 ta[1].top=ta[2].top=0; for(int i=0;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'; } } void Hannoi(st ta[],long Mov_count) { int k=0;//累计移动的次数 int i=0; int ch; while(k { //按顺时针方向把圆盘从现在的柱子移动到下 //一根柱子 ch=ta[i%3].Pop(); ta[(i+1)%3].Push(ch); cout<<++k<<" :"<< "Move disk "< " to "< i++; //把另外两根柱子上可以移动的圆盘移动到新的柱子上 if(k { if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top()) { ch = ta[(i-1)%3].Pop(); ta[(i+1)%3].Push(ch); cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl; } else { ch = ta[(i+1)%3].Pop(); ta[(i-1)%3].Push(ch); cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl; } } } }*/ //栈实现 /*#include "stdafx.h" #include #include using namespace std; int count=0;//用于记录是第几次操作 struct My_Hanoi { char a;//起始柱 char b;//中间柱 char c;//目标柱 int n; My_Hanoi(char a1,char b1 ,char c1 ,int n1) :a(a1),b(b1),c(c1),n(n1) { } }; void HanoiS(char a,char b,char c ,int n); void main() cout<<"请输入圆盘个数:"; int n; cin>>n; HanoiS('A','B','C',n); } void HanoiS(char a,char b,char c ,int n) { stack My_Hanoi tmp(a,b,c,0); s.push(My_Hanoi(a,b,c,n)); while(!s.empty()) { tmp=s.top(); s.pop(); if(tmp.n>1) { //注意了先操作的后进栈 s.push(My_Hanoi(tmp.b,tmp.a,tmp.c,n-1)); s.push(My_Hanoi(tmp.a,tmp.b,tmp.c,1)); s.push(My_Hanoi(tmp.a,tmp.c,tmp.b,n-1)); } else { count++; cout<<"第"< } } }*/ void Hanoi(int platesCount, int from, int dest, int by) { if (platesCount==1) { printf( "Move the plate from %d to %d through %d" , from, dest, by); }else { Hanoi(platesCount -1, from, by, dest); Hanoi(1, from, dest, by); Hanoi(platesCount -1, by, dest, from); } } // Advance one step to solve Hanoi void HanoiDrawer::SolveNextStep() { int platesCount , source , destination , intermediate; if(listSavedState.size()==0) { this->Hanoi(this->iPlatesCount, HanoiDrawer::SOURCE , HanoiDrawer::DESTINATION, HanoiDrawer::INTERMEDIATE); } if(listSavedState.size() % 4 != 0 ) { return; } platesCount = listSavedState.front(); listSavedState.pop_front(); source = listSavedState.front(); listSavedState.pop_front(); destination = listSavedState.front(); listSavedState.pop_front(); intermediate = listSavedState.front(); listSavedState.pop_front(); 汉诺塔java 程序 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class AutoMoveDisc extends JDialog implements ActionListener{ int amountOfDisc=3; TowerPoint [] pointA,pointB,pointC; char [] towerName; Container con; StringBuffer moveStep; JTextArea showStep; JButton bStart,bStop,bContinue,bClose; Timer time; int i=0,number=0; AutoMoveDisc(Container con){ setModal(true); setTitle("自动演示搬盘子过程"); this.con=con; moveStep=new StringBuffer(); time=new Timer(1000,this); time.setInitialDelay(10); showStep=new JTextArea(10,12); bStart=new JButton("演示"); bStop=new JButton("暂停"); bContinue=new JButton("继续"); bClose=new JButton("关闭"); bStart.addActionListener(this); bStop.addActionListener(this); bContinue.addActionListener(this); bClose.addActionListener(this); JPanel south=new JPanel(); south.setLayout(new FlowLayout()); south.add(bStart); south.add(bStop); south.add(bContinue); south.add(bClose); add(new JScrollPane(showStep),BorderLayout.CENTER); add(south,BorderLayout.SOUTH); setDefaultCloseOperation(JFrame.DO_NOTHING_ON_CLOSE); towerName=new char[3]; addWindowListener(new WindowAdapter(){ public void windowClosing(WindowEvent e){ time.stop(); setVisible(false); // test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include { count++; cout<<"第"< /*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include 数据结构 学院：信息学院 班级：计科高职13-2 姓名：曲承玉 学号：201303014044 汉诺塔程序设计报告 一、题目 汉诺塔（Towers of Hanoi）问题 二、设计要求 1、在窗口中画出初始时塔和碟子的状态。 2、可以以自动或手动两种方式搬移碟子。 3、自动搬移可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的移动过程如能实现动画最好。 4、定义塔的描述类和碟子的描述类。 5、在程序中，碟子的数目及每次移动的时间间隔可以通过对话框设置（也应该有默认值）。 6、支持暂停功和继续的功能（在自动搬移过程中可以暂停，并继续）。 7、暂停后，可以将当前的状态保存（碟子和塔的组合关系）。 8、可以从7中保存的文件中读出某个状态，并继续移动。 三、问题分析 1、已知有三个塔（1、 2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。 2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆放至顶部）。 3、每次移动一个碟子。 4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。 5、可以借助塔3。（图1-1） 图1-1 首先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了： 1、将上面的63个盘子移到b杆上； 2、将a杆上剩下的盘子移到c杆上； 3、将b杆上的全部盘子移到c杆上。 将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子....1个盘的工作。 四、算法选择 汉诺塔程序设计算法的实质就是递归递归思想的运用。现将其算法简述如下： 为了更清楚地描述算法，可以定义一个函数hanoi(n,a,b,c)。该函数的功能是：将n个盘子从塔a上借助塔b移动到塔c上。这样移动n 个盘子的工作就可以按照以下过程进行： 1) hanoi(n-1,a,c,b);//将n-1个金盘由a借助c移到b 2) 将最下面的金盘从a移动到c上； 实验二知识表示方法 梵塔问题实验 1．实验目的 （1）了解知识表示相关技术； （2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现） （1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法； （2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求 （1）简述实验原理及方法，并请给出程序设计流程图。 我们可以这样分析： （1）第一个和尚命令第二个和尚将63个盘子从A座移动到B座； （2）自己将底下最大的盘子从A移动到C； （3）再命令第二个和尚将63个盘子从B座移动到C；（4）第二个和尚命令第三个和尚重复（1）（2）（3）；以此类推便可以实现。这明显是个递归的算法科技解决的问 题。 （2）源程序清单： #include int n; printf("input the number of diskes\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(int n,char p1,char p2,char p3) { if(1==n) cout<<"盘子从"< 实验题目： Hanoi 塔问题 一、问题描述： 假设有三个分别命名为 A , B 和C 的塔座，在塔座 B 上插有n 个直径大小各不相同、从小到 大编号为1, 2,…，n 的圆盘。现要求将塔座 B 上的n 个圆盘移至塔座 A 上并仍按同样顺序 叠排，圆盘移动时必须遵守以下规则： (1 )每次只能移动一个圆盘； (2)圆盘可以插在 A , B 和C 中任一塔上； ( 3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求： 用程序模拟上述问题解决办法,并输出移动的总次数, 圆盘的个数从键盘输入； 并想 办法计算出程序运行的时间。 二、 算法思路： 1 、建立数学模型： 这个问题可用递归法解决,并用数学归纳法又个别得出普遍解法： 假设塔座B 上有3个圆盘移动到塔座 A 上： (1) "将塔座B 上2个圆盘借助塔座 A 移动到塔座C 上; (2) "将塔座B 上1个圆盘移动到塔座 A 上; (3) "将塔座C 上2个圆盘借助塔座 B 移动到塔座A 上。 其中第 2步可以直接实现。第 1步又可用递归方法分解为： 1.1"将塔座B 上1个圆盘从塔座 1.2"将塔座B 上1个圆盘从塔座 1.3"将塔座A 上1个圆盘从塔座 第 3 步可以分解为： 3.1将塔座C 上1个圆盘从塔座 3.2将塔座C 上1个圆盘从塔座 3.3将塔座B 上1个圆盘从塔座 综上所述：可得到移动 3 个圆盘的步骤为 B->A,B->C, A->C, B->A, C->B, C->A, B->A, 2、算法设计： 将n 个圆盘由B 依次移到A , C 作为辅助塔座。当 n=1时，可以直接完成。否则，将塔 座B 顶上的n-1个圆盘借助塔座 A 移动到塔座C 上；然后将圆盘B 上第n 个圆盘移到塔 座A 上；最后将塔座 C 上的n-1个圆盘移到塔座 A 上，并用塔座B 作为辅助塔座。 三、原程序 #include 1.实验目的： 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。 2.问题描述： 汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A 上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 3.算法设计思想： 对于汉诺塔问题的求解，可以通过以下三个步骤实现： (1)将塔A上的n-1个碟子借助塔C先移到塔B上。 (2)把塔A上剩下的一个碟子移到塔C上。 (3)将n-1个碟子从塔B借助于塔A移到塔C上。 4.实验步骤： 1.用c++ 或c语言设计实现汉诺塔游戏； 2.让盘子数从2 开始到7进行实验，记录程序运行时间和递 归调用次数； 3.画出盘子数n和运行时间t 、递归调用次数m的关系图， 并进行分析。 5.代码设计： Hanio.cpp #include"stdafx.h" #include 问题重述： 有三根柱A、B、C，在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块盘片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，输入任意的N，输出移动方法。 (注意：这是一个古老的传说，传说是如果把64个盘子由A柱移到了C柱的话，那么世界末日就到了，事实上如果要把64个盘子从A柱移到C柱的话，即使用计算机运算，也要计算数亿年，所以这个预言未必不是真实。) 【分析】 我们可以这样考虑，当n=1时，我们只要直接将A柱的盘子移到C柱，当n>1时，我们可以先把n-1个盘子由A柱通过C柱移到B柱，此时就可以把A柱剩下的最后一个盘子直接移到C柱，这样接下来只要把n-1个盘子通过A柱移到C 柱即可，如果就构成了递归的思路，我们可以定义个移动过程mov(n,a,b,c)表示将n个盘子从a通过b移到c 1.只要求输出搬运的次数 #include int fact(int n) { if(n==1) return(1); else return((2*fact(n-1)+1)); } int main() { cout< 汉诺塔游戏 学院：理学院 班级：信科102班 组长：李万东 组员1：袁雪娇 组员2：张瑜 设计期限2012 年3月1开始 至2012年6月20 结束 课程设计题目：汉诺塔游戏 课程设计目的： 《JA V A程序设计》是计算机相关专业的必修专业基础课程，其实践性、应用性很强。实践教学环节是必不可少的一个重要环节。本课程的程序设计专题实际是计算机相关专业学生学习完《JA V A程序设计》课程后，进行的一次全面的综合训练，JA V A程序设计的设计目的是加深对理论教学内容的理解和掌握，使学生较系统地掌握程序设计及其在网络开发中的广泛应用，基本方法及技巧，为学生综合运用所学知识，利用软件工程为基础进行软件开发、并在实践应用方面打下一定基础。 随着社会的进步，我们用来娱乐的游戏世界也越来越丰富，越来越复杂。本程序的汉诺塔游戏不但包括了游戏最基本的功能，而且还能培养用户的逻辑思维能力，同时也给玩家提供了一定的娱乐空间。本游戏还包括一个自动演示搬移汉诺塔的功能，此功能能够帮助初次接触此游戏的用户了解此游戏的玩法。 课程设计理论： 本程序要求实现用图形界面，画出3个杆和若干个大小不一的矩形盘子，形成3个塔，分别为A塔，B塔，C塔，同时盘子数目可以人工设定。用户可以用鼠标选中盘子，然后通过拖动鼠标来移动该盘子、释放鼠标来放置该盘子。用户在移动盘子的过程中，可以随时单击汉诺塔菜单栏的菜单中提供的按钮，重新开 1格式已调整，word版本可编辑. 始游戏，并且可以通过单击汉诺塔菜单栏的菜单提供的按钮，让程序自动完成把A塔上的盘子全部移动到C塔上，实现自动演示。 汉诺塔算法属于递归算法，该算法过程为： 假定要把n个盘子按题目规定由A杆借助B杆移动到C杆。 第一步：先把上面的n-1个盘子借助C杆放到B杆。 第二步：把第n个盘子从A杆直接移到C杆。 第三步：把B杆上的n-1个盘子借助A杆移到B杆。 概要设计： 1.课程设计内容： 有三个表示塔的对象，分别命名为A、B和C。A塔上有若干个盘子，盘子的大小不等，并按着大小顺序依次摆放在A塔上，大盘在下，小盘在上。用户可以用鼠标拖动盘子，把A塔上的盘子全部移动到另外两个塔中的任何一个塔上。要求每次只能移动一个盘子，在任何时候不允许大盘压在小盘的上面。用户也可以选择让程序自动演示。选择自动演示后，程序将以动画形式演示把A塔上的盘子全部移到C塔的过程。 2.课程设计功能： (1)设计GUI界面的汉诺塔。汉诺塔中有三个座，名字分别是A、B和C。初始状态是A座上有四个大小不等的盘子，这些盘子从座底到座顶按着大小顺序依次摆放在A座上。用户可以用鼠标选中盘子，然后通过拖动鼠标来移动该盘子、释放鼠标来放置该盘子。 (2)程序要求用户在移动盘子过程中，不允许把大盘子放在小盘子的上面，用户最终要完成的是把A座上的全部盘子移动到B座或C座上。 (3)用户可以通过单击汉诺塔菜单栏的菜单提供的按钮，让程序自动完成把A座上的盘子全部移动到B座或C座上。 (4)用户在移动盘子的过程中，可以随时单击汉诺塔菜单栏的菜单提供的按钮，重新开始游戏。 3. 2. hanoi塔程序如下： main() {hanoi(3,'A','B','C'); } hanoi(n,a,b,c) int n; char a,b,c; {if (n==1) printf("%c-->%c\n",a,c); else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} } 运行结果： A-->C A-->B C-->B A-->C B-->A B-->C A-->C 问题： hanoi(n,a,b,c) int n; char a,b,c; {if (n==1) printf("%c-->%c\n",a,c); else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} } 我给你详细解释下这个程序中的代码吧。我也是刚学，希望对你有用。可能有些不好之处，还希望谅解。 先说下这个问题的整体思想： 1，如果只有1个盘，那么就直接把这个盘从A移动到C上。 2，如果存在两个盘，那么先把第一个盘移动到B上，在把最下面一个盘移动到C上，在把B上的盘移动到C上。 3，这样，我们可以得出一个结论，如果存在N个盘，可以先把上面N-1个盘通过C 移动到B上，然后把第N个盘移动到C上，再把B上的N个盘通过A 移动到C上。 if (n==1) printf("%c-->%c\n",a,c); 这一句，表示只有1个盘子的时候，那么就是把第一个盘子直接移到第三个盘子上。 else {hanoi (n-1,a,c,b); 如果超过一个盘字，则需要先把N-1个盘子通过C 移动到B上。 printf ("%c-->%c\n",a,c); 把剩下的第N个盘，从A移动到C上。 hanoi (n-1,b,a,c);} 再把剩下的在B上的N-1个盘，通过A移动到C上。 这属于一个递归算法。 现在，N=3。 我们看下程序怎么运行的。 else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} N=3，也就是开始程序会执行 hanoi (2,a,c,b);这句语句。 再看，2还是大于1，所以 程序会继续运行。注意，这里，为hanoi (2,a,c,b); C和B 换了位置。 hanoi (2,a,c,b); 我们把数字代入，得出。 根据N=2，C和B 互换。以及下面的代码，得出 ```````````````````````````````````````````````` 数据库课程设计报告------------题目：汉诺塔 学院名称：计算机学院 专业名称：计算机科学与技术 班级：计算机08-08班 学号：0804010807 姓名:田昊 指导教师：孙冬璞 起始时间：2011年1月5日-------2011年1月9日 摘要 汉诺塔（又称河内塔）问题是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。 利用计算机图形学进行汉诺塔演示程序设计,是利用C语言绘图函数实现汉诺塔的递归算法图形界面演示过程。通过C语言实现图形学的绘图，程序控制，以及区域填充，并根据汉诺塔的算法原理实现大小不同的盘子移动的全过程演示。 1 需求分析 1.1 需求概述 汉诺塔演示程序设计是计算机图形学中图形变换的内容之一。而图形学中的图形变换的概念是由简单图形生成复杂图形，可用二维图形表示三维形体，甚至可以对静态图形经过快速变换而获得图形的动态显示效果。其任务是研究各点坐标之间的变化规律。而本次课程设计就是利用C语言以及图形函数实现汉诺塔的递归算法来进行其盘块移动的全过程显示。在TC环境中要实现这样的功能，就要牵涉到图形设备接口的知识。Windows图形设备接口是为与设备无关的图形设计的，是Windows系统的重要组成部分,负责系统与用户或绘图程序之间的信息交换,并控制在输出设备上显示图形或文字。应用程序必须通知图形设备接口来加载特定的设备驱动，一旦驱动得以加载，就可以准备应用设备进行相关的操作这些任务都要通过创建和维护设备描述表来完成。在实现汉诺塔演示程序设计时，是利用坐标系统而得到的，而在Windows应用程序中有两种坐标系统：设备坐标系统和逻辑坐标系统。其中设备坐标系统中又有三种相互独立的坐标系统：屏幕坐标系统、窗口坐标系统和用户区坐标系统。这些坐标系统均以像素点来表示度量的单位。屏幕坐标系统使用整个屏幕作为坐标区域，原点为屏幕原点。窗口坐标系统使用了边界在内的应用程序的窗口作为坐标区域。窗口边界的左上角是坐标系统的原点。用户坐标系统是最经常使用的坐标系统。用户区是窗口工作区，不包括窗口边界、菜单条及滚动条等。用户一般只需操作应用程序的用户区，因此用户区坐标系统对大多数应用程序都是适用的。 XXXX大学信息学院 课程设计报告 教师签名：xxxxx 题目1实验报告 1．数据结构定义 因为该算法需要用到循环队列、堆和线性表，因此采用以下数据类型： typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue;//循环队列 typedef struct { int *elem; int length; int listsize; }SqList;//堆排序 2．算法说明 void HeapAdjust(int flag,SqList &H,int s,int m) void HeapSort(int flag,SqList &H)//对H进行堆排序； Status InitQueue(SqQueue &Q)//构造一个空队列Q，该队列预定义大小为MAXQSIZE; Status EnQueue(SqQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素; Status DeQueue(SqQueue &Q, QElemType &e) // 若队列不空, 则删除Q的队头元素, 用e 返回其值, 并返回OK; 否则返回ERROR; Status GetHead(SqQueue Q, QElemType &e)// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR; Status QueueLength(SqQueue Q) // 返回Q的元素个数; Status QueueTraverse(SqQueue Q)// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR. 3．用户使用说明 运行程序，根据屏幕上的文字提示一步步操作。 4．个人测试结果（截图） 部分测试结果截图 三峡大学理学院2011级电信专业 《高级语言程序设计》课程设计 说明书 设计题目: 汉诺塔的搬移过程设计 班级：高级语言程序设计1 班 学号：2011142227 姓名：徐飞 完成日期：2012 年6月20日 1设计任务 设计题目：用递归法计算解决汉诺塔问题，并能够演示解决汉诺塔问题过； 要求：设计一个运用递归法计算解决汉诺塔问题C语言程序； 2 汉诺（Hanoi）塔问题的提出 古代有一个梵塔，塔内有A,B,C，3个座，座A上有64个大小不等的盘子，大的在下，小的在上（如下图）。有一个和尚想把这64个盘子从座A全部移到座C ，在移动过程中可以借用座A，座B或座C,但每次只允许移动一个盘子，并且不允许大盘放在小盘的上面。 3编程思路 首先，要找出递归的两个关键点，即： 递归终止条件：只有一个盘子时，可以移动。 递归表达式：要找出递归表达式，可以如下设想： 下面以3个盘子为例说明详细的移动过程： (1)将座A上的2个盘子移动到座B上； (2)将座A上的1个盘子移动到座C上； (3)将座B上的2个盘子移动到座C上； 上面第1步可用递归方法分解为： （1）将座A上的1个盘子从座A移动到座C上； （2）将座A上的1个盘子从座A移动到座B上； (3)将座C上的1个盘子从座C移动到座B上； 第（3）步可用递归方法分解为： （1）将座B上的1个盘子从座B移动到座A上； （2）将座B上的1个盘子从座B移动到座C上； （3）将座B上的1个盘子从座A移动到座C上; 第（1）步操作可归纳为：将座A上的2个盘子借助座C移到座B; 第（3）步操作可归纳为：将座B上的2个盘子借助座A移到座C; 因此，将n个盘子从座A移到座C可以描述为： （1）将n-1个盘子从座A借助座C移到座B; （2）将剩下的一个盘子从座A移到座C; （3）将n-1个盘子从座B借助座A移到座C; 3系统操作流程图; 4.程序说明； 合肥学院 计算机科学与技术系 课程设计报告 2010～2011学年第一学期 课程 JAVA语言课程设计 课程设计名称汉诺塔模拟程序 学生姓名程伟 学号0704031021 专业班级网络工程(1)班 指导教师许强、张贯虹 2010年9月 1、 需求分析 本次的课程设计的主要任务是：设计一个模拟程序，图形化地展现汉诺塔的求解过程。主要解决的问题是： 1． 学习数据结构课程中关于汉诺塔的知识和算法。 N阶Hanoi塔，有3个柱子a、b、c，a柱子上从上至下叠放有n个直径由小到大、编号依次为1,2，…，n的圆盘。现要求将a柱上的n个圆盘移至c柱，并仍按同样顺序叠放。圆盘移动时须遵循以下原则： 1） 每次只能移动一个圆盘。 2） 圆盘可以插在a、b、c中的任何一个柱子上。 3） 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 圆盘的移动过程是一个递归调用过程。 2． 设计图形界面，画出3个柱子和若干个大小不一的圆盘，圆盘数量可人工设定。 Frame是一种具有边框的容器，它是Java中最常用的容器之一，它又是Java Application程序的图形用户界面。Frame只能作为最外层容器，不能被任何其他容器所包含。下拉列表是一种“多选一”的输入界面，通常只可看见下拉列表的一个选项和它右边的箭头按钮。当要改变盘子的个数时（即单击下拉列表中选中项），系统自动产生一个ItemEvent类对象所包含这个时间的信息，并将该对象作为实参传递给被自动调用的监听者的选择事件的响应方法。 3． 当点击“开始”按钮后，系统自动展现圆盘的移动过程，一秒移动一次。 线程是进程中一段连续的控制流程或是一段执行路径。在Java语言中，线程的创建有两种方式：（1）定义一个Thread类的子类，并在该子类中重写run()方法，该run()方法是线程执行的起点；（2）定义一个实现Runnable接口的类，并在该类中定义Runnable接口的run()方法，同样，该run()方法代表了线程执行的起点。本程序中用到第二种创建线程的方法。 2、 设计 .1 设计思想 本程序要求实现用图形界面，画出3个柱子和若干个大小不一的圆盘，同时圆盘数目可以人工设定，当点击“开始”按钮后，系统自动展现圆盘的移动过程，从而实现汉诺塔问题，其中圆盘移动速度是每秒移动一次。 1、 所谓汉诺塔，既是一种游戏，游戏的装置是一块铜板，上面有3根 杆，最左 杆自下而上、由大到小顺序串有64个金盘，呈一个塔形(如图1.1所示)。游戏要求把左边杆上的金盘全部移动到最右 题目描述Description 汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在A，B，C 三根柱子上，有n个不同大小的圆盘（假设半径分别为1-n吧），一开始他们都叠在我A上（如图所示），你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。 游戏中的每一步规则如下： 1. 每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方） 2. 移动的过程中，你必须保证大的盘子不能在小的盘子上方（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子） 如对于n=3的情况，一个合法的移动序列式： 1 from A to C 2 from A to B 1 from C to B 3 from A to C 1 from B to A 2 from B to C 1 from A to C 给出一个数n，求出最少步数的移动序列 输入描述Input Description 一个整数n 输出描述Output Description 第一行一个整数k，代表是最少的移动步数。 接下来k行，每行一句话，N from X to Y，表示把N号盘从X柱移动到Y 柱。X,Y属于{A,B,C} 样例输入Sample Input 3 样例输出Sample Output 7 1 from A to C 2 from A to B 1 from C to B 3 from A to C 1 from B to A 2 from B to C 1 from A to C 数据范围及提示Data Size & Hint n<=10 #include 汉诺塔c语言程序代码集团文件版本号：（M928-T898-M248-WU2669-I2896-DQ586-M1988） 汉诺塔c语言程序代码（通过vc++6.0验证）（附讲解）让我们先看看代码吧 #include } } main() { int a,b,c,i; a=1; b=2; c=3; printf("请输入汉诺塔的盘数"); scanf("%d",&i); hj(a,b,c,i); return 0; } 以上是汉诺塔的代码，该程序主要是运用了递归的思想，比如数学中的 f(x)=f(x-1)+f(x-2)，在本程序中为：int hj(int a,int b, int c,int i) { int t; if(i==1) printf("%d->%d\n",a,c); else {t=c; c=b; b=t; hj(a,b,c,i-1); 也就是说，我们在这个函数中再次调用这个函数，相当于一个循环，而在再次调用的过程中，i的值变成i-1，就类似于f（x-1），这样层层调用，最终就变成当i=1的时候的值，然后通过运算，计算出想要得到的值。 汉诺塔的数值分析： 我们可以发现，当只有一个盘的时候，我们只需要做1->3（就是把第一个柱子上的最顶端的盘移动到第三根柱子，以下不再解释） 当有两个盘的时候，是1->2 1->3 2->3 三个盘子是：1->3 1->2 3->2 1->3 2->1 2->3 1->3 分析一下可以得出以下结论： 初始值a=1 b=2 c=3 一个盘子就是a->c 两个盘子与一个盘子的关系是： 第一步：b与c交换值，然后打印a->c 第二步：打印a->b 第三步：a与c交换值，b与c交换值，打印a->c 进一步分析，便可以得出以下结论 只要盘子数量为i（i大于1），那么它就有三部分 第一部分，b与c交换值，然后运行i-1 汉诺塔C递归算法详细解答 程序如下： void move(char x,char y){ printf("%c-->%c\n",x,y); } void hanoi(intn,charone,chartwo,char three){ /*将n个盘从one座借助two座，移到three座*/ if(n==1) move(one,three); else{ hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } main(){ int n; printf("input the number of diskes:"); scanf("%d",&n); printf("The step to moving %3d diskes:\n",n); hanoi(n,'A','B','C'); } Hanoi塔问题, 算法分析如下，设A上有n个盘子。 如果n=1，则将圆盘从A直接移动到C。 如果n=2，则： （1）将A上的n-1（等于1）个圆盘移到B上； （2）再将A上的一个圆盘移到C上； （3）最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则： A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。 （2）将A上的一个圆盘移到B。 （3）将C上的n`-1（等于1）个圆盘移到B。 B）将A上的一个圆盘移到C。 C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。 （2）将B上的一个盘子移到C。 （3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。 竭诚为您提供优质文档/双击可除汉诺塔程序实验报告 篇一：汉诺塔程序实验报告 实验题目： hanoi塔问题 一、问题描述： 假设有三个分别命名为A，b和c的塔座，在塔座b上插有n个直径大小各不相同、从小到大编号为1，2，…，n 的圆盘。现要求将塔座b上的n个圆盘移至塔座A上并仍按同样顺序叠排，圆盘移动时必须遵守以下规则： （1）每次只能移动一个圆盘； （2）圆盘可以插在A，b和c中任一塔上； （3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求：用程序模拟上述问题解决办法，并输出移动的总次数，圆盘的个数从键盘输入；并想办法计算出程序运行的时间。 二、算法思路： 1、建立数学模型： 这个问题可用递归法解决，并用数学归纳法又个别得出普遍解法： 假设塔座b上有3个圆盘移动到塔座A上： （1）"将塔座b上2个圆盘借助塔座A移动到塔座c上； （2）"将塔座b上1个圆盘移动到塔座A上； （3）"将塔座c上2个圆盘借助塔座b移动到塔座A上。 其中第2步可以直接实现。第1步又可用递归方法分解为： 1.1"将塔座b上1个圆盘从塔座x移动到塔座A； 1.2"将塔座b上1个圆盘从塔座x移动到塔座c； 1.3"将塔座A上1个圆盘从塔座Z移动到塔座c。 第3步可以分解为： 3.1将塔座c上1个圆盘从塔座Y移动到塔座b； 3.2将塔座c上1个圆盘从塔座Y移动到塔座A； 3.3将塔座b上1个圆盘从塔座x移动到塔座A。 综上所述：可得到移动3个圆盘的步骤为 b->A,b->c,A->c,b->A,c->b,c->A,b->A, 2、算法设计： 将n个圆盘由b依次移到A，c作为辅助塔座。当n=1时，可以直接完成。否则，将塔座b顶上的n-1个圆盘借助塔座A移动到塔座c上；然后将圆盘b上第n个圆盘移到塔 汉诺塔演示 课程设计报告 姓名学号分工 胡楠楠201212201401027组长统筹规划梅清晨201212201401009报告、部分代码刘安妮201212201401029报告、部分代码孙坡坡201212201402010PPT演示 目录 一、问题描述.................................................................................................................................. II 二、任务概述.................................................................................................................................. II 2.１课程设计的目的............................................................................................................... II 2.２课程设计的内容和要求................................................................................................... II 2.２.１功能要求.............................................................................................................. II 2.２.２环境要求............................................................................................................. I II 2.２.３课程设计设备..................................................................................................... I II 三、问题分析：............................................................................................................................. I II 四、设计思路.................................................................................................................................. V 4.１主程序流程图................................................................................................................... V 4.２功能模块示意图.............................................................................................................. V I 4.３汉诺塔求解流程图.......................................................................................................... V I 五、模块详细说明....................................................................................................................... VII 5.１背景初始化.................................................................................................................... VII 5.１.１开启DOS图形模式......................................................................................... VII 5.1.2字幕显示模块...................................................................................................... VII 5.2问题求解模块................................................................................................................... I X 5.2.1汉诺塔问题描述.................................................................................................... I X 5.2.2移动方案................................................................................................................. X 5.2.3演示动画................................................................................................................. X 5.2.4屏幕暂停函数........................................................................ 错误！未定义书签。 5.2.5路径清理模块...................................................................................................... XII 六、用户运行界面图示............................................................................................................... XII 七、心得体会........................................................................................................................ X VI汉诺塔c++程序
汉诺塔 java 程序
汉诺塔问题的三种实现
汉诺塔程序设计报告
汉诺塔问题
汉诺塔程序实验报告
汉诺塔问题实验报告
汉诺塔问题的程序实现(hanoi塔)
汉诺塔课程设计报告
汉诺塔程序解读
汉诺塔 面向对象课程设计
汉诺塔问题
汉诺塔问题C语言程序设计
汉诺塔模拟程序报告
汉诺塔问题 递归
汉诺塔c语言程序代码
汉诺塔C递归算法详细解答
汉诺塔程序实验报告
汉诺塔演示