出栈入栈演示的超详细过程(汉诺塔)

n a b c 返回地址3A B C 22A C B

13C 第1步：把1号盘从A 移到C 第2步：把2号盘从A 移到B 1C A B 16第3步：把1号盘从C 移到B 第4步：把3号盘从A 移到C 2B A C 16B C A 13第5步：把1号盘从B 移到A 第6步：把2号盘从B 移到C A B 第7步：把1号盘从A 移到C 总共移动了7次

演示结束，程序退出。进

栈

出

栈栈：是一种运算受限的线性表，只能够在表的一端进行增加、删除的操作。递归：程序直接或间接调用自己的一种方法。它可以把一个

大型的问题分解为一个较小的问题来解决。

栈里的工作记录列表

数据结构实验二_栈的基本操作

青岛理工大学课程实验报告

s->top=s->base; s->stacksize=stack_init_size; return 1; } int Push(sqstack *s,int e) { if(s->top-s->base>=s->stacksize) { s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int)); if(!s->base) return 0; s->top=s->base+s->stacksize; s->stacksize+=stackincrement; } *(s->top++)=e; return e; } int Pop(sqstack *s,int e) { if(s->top==s->base) return 0; e=*--s->top; return e; } int stackempty(sqstack *s) { if(s->top==s->base) { return 1; } else Push(s,n%flag); n=n/flag; } while(!stackempty(s)) { e=Pop(s,e); switch(e) { case 10: printf("A"); break; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break; default: printf("%d",e); } } printf("\n"); return 0; } int main() { sqstack s; StackInit(&s); conversion(&s); return 0; }

汉诺塔问题的三种实现

// 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<<"第"<

/*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子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

汉诺塔c++程序

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();

顺序栈的基本操作讲解

遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0

三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作

五、代码： #include #include #define maxsize 64 typedef int datatype; //定义结构体typedef struct { datatype data[maxsize]; int top; }seqstack; //建立顺序栈seqstack *SET(seqstack *s) { int i; s=(seqstack*)malloc(sizeof(seqstack)); s->top=-1; printf(" 请输入顺序栈元素(整型，以scanf("%d",&i); do{ s->top++; s->data[s->top]=i; scanf("%d",&i); 0 结束)："); }while(i!=0); printf(" 顺序栈建立成功\n"); return s; } //清空栈void SETNULL(seqstack *s) { s->top=-1;} //判断栈空 int EMPTY(seqstack *s) { if(s->top>=0) return 0; else return 1;} //进栈 seqstack *PUSH(seqstack *s) { int x; printf(" 你想要插入的数字："); scanf("%d",&x); if(s->top==maxsize-1) { printf("overflow"); return NULL; } else {

汉诺塔非递归算法C语言实现

汉诺塔非递归算法C语言实现 #include #include #define CSZL 10 #define FPZL 10 typedef struct hanoi { int n; char x,y,z; }hanoi; typedef struct Stack { hanoi *base,*top; int stacksize; }Stack; int InitStack(Stack *S) { S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base; S->stacksize=CSZL; return 1; } int PushStack(Stack *S,int n,char x,char y,char z) { if(S->top-S->base==S->stacksize) { S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base+S->stacksize; S->stacksize+=FPZL; } S->top->n=n; S->top->x=x; S->top->y=y; S->top->z=z; S->top++; return 1; } int PopStack(Stack *S,int *n,char *x,char *y,char *z) { if(S->top==S->base)

用VB设计汉诺塔动画游戏

本栏目责任编辑：谢媛媛软件设计开发Computer Knowledge and Technology 电脑知识 与技术第5卷第30期(2009年10月)用VB 设计汉诺塔动画游戏 刘德强 （无锡职业技术学院，江苏无锡214024） 摘要：汉诺塔问题是程序设计教学中关于递归调用的经典案例。该文介绍了用VB 设计汉诺塔动画游戏程序的基本过程，其中重点介绍了用VB 的自定义数据类型和图形处理技术设计游戏步点状态记录和动画效果的方法。 关键词：VB ；汉诺塔；动画 中图分类号：TP311文献标识码：A 文章编号：1009-3044(2009)30-8460-03 The Designing of Hanoi Towers Animation Game by VB LIU De-qiang (Wuxi Institute of Technology,Wuxi 214024,China) Abstract:The Hanoi Towers is a typical case of recursive calls in programming teaching.This paper introduces the basic process of design -ing Hanoi Towers animation game by VB,focuses on recording game state between two steps and designing animation by self-defined data type and graph skill in VB. Key Words:VB;Hanoi;animation 汉诺塔问题源自印度的一个古老传说，传至现代演变成了汉诺塔游戏：有A 、B 、C 三个垂直杆和若干个大小各不相同的圆片。开始时圆片全部套在A 杆上，且从下至上圆片大小依次递减。要求借助B 杆，将圆片全部移到C 杆上，每次只能移动一片，并且整个过程中三个杆上的圆片都必须保持大的在下小的在上。游戏的难度由开始时放置在A 杆上圆片的个数进行控制。 1游戏步点状态记录设计 笔者设计的汉诺塔游戏程序主要包括演示和游戏两方面的功能。演示功能实现的是根据汉诺塔问题算法预先计算出的圆片移动顺序由计算机自行对圆片进行移动；而游戏功能是指计算机通过人机交互界面根据游戏者的实时操作顺序进行圆片的移动。图1是程序运行时界面。无论是演示还是游戏，计算机执行的基本动作元素是相同的，即圆片从一个杆上移动到另一个杆上，这一过程体现在程序设计中就是在新的位置对圆片图形进行重画，它与每个杆的步点状态密切相关。 步点状态是指每完成一步操作以后，开始下一步操作之前，一个杆上 的圆片数量及各圆片的位置和大小等多个特征综合构成的状态，是多个 数据的集合。将开始时圆片数记为n ，从初始状态圆片都在A 杆上，到终 止状态n 个圆片移到C 杆上，其间每次移动圆片，各杆的步点状态都会 发生变化。游戏进程中“记”住各杆的当前步点状态，是实现不断移动圆片 的关键。以要移动A 杆上的一个圆片到B 杆为例：要判断圆片根据规则 是否可以移动及圆片移动后放置在B 杆的什么位置（y 坐标），就必须知 道当前B 杆上最上端圆片的大小和B 杆上当前圆片数量，即B 杆的当前 步点状态。综合以上分析，游戏步点状态记录是程序设计中的要点。 鉴于描述步点状态需要多个数据，且数据间相互关联并构成整体，笔 者在设计中采用了自定义数据类型的方法，数据类型名称为circles ，所含 内容和定义格式如下： Type circles counts As integer r()As integer x As integer y()As integer End Type circles 类型中，数据成员counts 用于记录杆上实际圆片数，r 用于记录各圆片的半径，x 记录各圆片圆心的x 坐标，y 记录各圆片圆心的y 坐标。因为每次游戏设置的初始圆片数是不确定的且游戏进程中各杆都可能出现多个圆片，所以数据成员r 和y 定义为动态数组。 数据类型circles 定义以后，先使用该类型定义三个实例a 、b 、c ，分别代表A 、B 、C 三个杆的步点状态。语句如下： Dim a As circles ，b As circles ，c As circles 当初始圆片数量确定后(记为n)，可使用下列语句对A 杆的步点状态a 进行初始化。 投稿日期：2009-08-22 作者简介：刘德强（1965-），江苏靖江人，无锡职业技术学院讲师。 图1运行界面ISSN 1009-3044Computer Knowledge and Technology 电脑知识与技术Vol.5,No.30,October 2009,pp.8460-8462E-mail:xsjl@https://www.docsj.com/doc/358094165.html, https://www.docsj.com/doc/358094165.html, Tel:+86-551-569096356909648460

数据结构栈的定义及基本操作介绍

北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）

四、程序清单(包含注释) 1、2. #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 #define INCREASEMENT 10 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); }

数据结构实验报告汉诺塔

实验报告书 课程名：数据结构 题目：汉诺塔 班级： 学号： 姓名： 评语： 成绩：指导教师： 批阅时间：年月日

一、目的与要求 1）掌握栈与队列的数据类型描述及特点； 2）熟练掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 5）认真书写实验报告,并按时提交。 二、实验内容或题目 汉诺塔问题。程序结果：给出程序执行过程中栈的变化过程与圆盘的搬动状态。 三、实验步骤与源程序 源程序： / *编译环境Visual C++6.0 */ #include "stdafx.h" #include #include void move(int h,char c,char f) { printf("%d:%c--->%c\n",h,c,f); } void hanoi(int n,char x,char y,char z) { if(n==1) move(1,x,z); else { hanoi(n-1,x,z,y); move(n,x,z); hanoi(n-1,y,x,z); } } void main(void) { int flag; do { printf(" 汉诺塔问题\n\n"); printf("[1] 开始\n"); printf("[2] 退出\n"); printf("1--2请选择:"); scanf("%d",&flag); printf("\n"); switch(flag) { case 1:

汉诺塔 java 程序

汉诺塔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);

数据结构栈的基本操作,进栈,出栈

第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： InitStack(SqStack &S) 操作结果：构造一个空栈 Push(L,e) 操作结果：插入元素e为新的栈顶元素

Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作： LinkStack(SqStack &S) 操作结果：构造一个空栈 Status Push(L,e) 操作结果：插入元素e为新的栈顶元素 Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 3、顺序栈程序包含的主要模块： (1) 已给定的函数库： （2）顺序栈结构体： （3）顺序栈初始化及创建: (4)元素插入 (5)元素删除

汉诺塔问题实验报告

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 #include #include void hanoi(int n,char x,char y,char z) { if(n==1) { printf("从%c->搬到%c\n",x,z); } else { hanoi(n-1,x,z,y); printf("从%c->%c搬到\n",x,z); hanoi(n-1,y,x,z); }

汉诺塔程序设计报告

数据结构 学院：信息学院 班级：计科高职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上；

数据结构——顺序栈的基本操作

#include using namespace std; # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 typedef struct { int * base; int * top; int stacksize;//当前栈可使用的最大容量 } SqStack; void InitStack(SqStack &S)//构造一个空栈 { S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) {cout<<"存储分配失败!!!"<=S.stacksize) { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) cout<<"存储分配失败!!!"<

汉诺塔问题的非递归算法分析

汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉

汉诺塔游戏设计过程

兰州交通大学 数理与软件工程学院 课程设计报告 2011 ～2012学年第二学期 课程名称数据结构 设计题目汉诺塔游戏程序 班级信计1001班 小组成员张章、王欣、李贵生 报告者李贵生201005235 指导老师金静 2012年6月

一、实验目的： 通过此次C++实训，一方面加深了对C++语言的了解，而不只是单单的在课本中学到的那些理论。通过学生动手亲自编写，平时乏味的课程，变的生动有趣。平时在课堂上学到的东西可以自己动手编写，将其转化成一些实用的技能。另一方面，通过学生小组完成任务，提高团队意识，增加凝聚力，让同学们意识到团结就是力量，每个人都是重要的一份子。 二、题目：汉诺塔游戏程序 <1> 问题描述：在平面上有三个位置A、B、C，在A位置上有n 个大小不等的圆盘、小盘压在大盘上形成圆盘堆。要求将A位置的N个圆盘通过B位置移动到C位置上，并按同样的顺序叠放。 移动圆盘时必须遵循以下规则： 1.每一次只能移动一个圆盘 2.圆盘可以放在A、B、C任何一个塔座上 3.任何时刻都不能将大圆盘压在小圆盘上 <2> 基本要求： 圆盘的个数从键盘输入（如3-64等）；用动画的形式在屏幕上显示盘的移动。 三、问题分析和任务定义 1、已知有三个塔（1、 2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。 2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆

放至顶部）。 3、每次移动一个碟子。 4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。 5、可以借助塔3。 先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了： 1、将上面的N个盘子移到b杆上； 2、将a杆上剩下的盘子移到c杆上； 3、将b杆上的全部盘子移到c杆上。 将这个过程继续下去，就是要先完成移动n个盘子、n-1个盘子、n-2个盘子....1个盘的工作。 四、课题介绍： 4.1 汉诺塔问题初始模型： 4.2 实现步骤： 为满足题目中盘子的移动问题，必须遵循的条件是：一次

(完整word版)顺序栈基本操作实验报告

数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算

?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include using namespace std; #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define OVERFLOW -1 #define OK 1 #define NO -1 #define NULL 0 typedef int Status; typedef char SElemType; typedef struct { SElemType *base; //在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 } SqStack; Status Initstack(SqStack &S)//构造一个空栈S { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; return OK; }//InitStack Status StackEmpty(SqStack &S) { if(S.base==S.top)

汉诺塔 面向对象课程设计

数据库课程设计报告------------题目：汉诺塔 学院名称：计算机学院 专业名称：计算机科学与技术 班级：计算机08-08班 学号：0804010807 姓名:田昊 指导教师：孙冬璞 起始时间：2011年1月5日-------2011年1月9日

摘要 汉诺塔（又称河内塔）问题是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。 利用计算机图形学进行汉诺塔演示程序设计,是利用C语言绘图函数实现汉诺塔的递归算法图形界面演示过程。通过C语言实现图形学的绘图，程序控制，以及区域填充，并根据汉诺塔的算法原理实现大小不同的盘子移动的全过程演示。 1 需求分析 1.1 需求概述 汉诺塔演示程序设计是计算机图形学中图形变换的内容之一。而图形学中的图形变换的概念是由简单图形生成复杂图形，可用二维图形表示三维形体，甚至可以对静态图形经过快速变换而获得图形的动态显示效果。其任务是研究各点坐标之间的变化规律。而本次课程设计就是利用C语言以及图形函数实现汉诺塔的递归算法来进行其盘块移动的全过程显示。在TC环境中要实现这样的功能，就要牵涉到图形设备接口的知识。Windows图形设备接口是为与设备无关的图形设计的，是Windows系统的重要组成部分,负责系统与用户或绘图程序之间的信息交换,并控制在输出设备上显示图形或文字。应用程序必须通知图形设备接口来加载特定的设备驱动，一旦驱动得以加载，就可以准备应用设备进行相关的操作这些任务都要通过创建和维护设备描述表来完成。在实现汉诺塔演示程序设计时，是利用坐标系统而得到的，而在Windows应用程序中有两种坐标系统：设备坐标系统和逻辑坐标系统。其中设备坐标系统中又有三种相互独立的坐标系统：屏幕坐标系统、窗口坐标系统和用户区坐标系统。这些坐标系统均以像素点来表示度量的单位。屏幕坐标系统使用整个屏幕作为坐标区域，原点为屏幕原点。窗口坐标系统使用了边界在内的应用程序的窗口作为坐标区域。窗口边界的左上角是坐标系统的原点。用户坐标系统是最经常使用的坐标系统。用户区是窗口工作区，不包括窗口边界、菜单条及滚动条等。用户一般只需操作应用程序的用户区，因此用户区坐标系统对大多数应用程序都是适用的。

汉诺塔问题与递归思想教学设计

一、教学思想（包括教学背景、教学目标） 1、教学背景 本课程“递归算法”，属于《数据结构与算法》课程中“栈和队列”章节的重点和难点。数据结构与算法已经广泛应用于各行各业的数据存储和信息处理中，与人们的社会生活密不可分。该课程是计算机类相关专业核心骨干课程，处于计算机学科的核心地位，具有承上启下的作用。不仅成为全国高校计算机类硕士研究生入学的统考科目，还是各企业招聘信息类员工入职笔试的必考科目。数据结构与算法课程面向计算机科学与技术、软件工程等计算机类学生，属于专业基础课。 2、教学大纲 通过本课程的学习，主要培养学生以下几个方面的能力： 1）理解递归的算法； 2）掌握递归算法的实现要素； 3）掌握数值与非数值型递归的实现方法。 根据学生在学习基础和能力方面的差异性，将整个课程教学目标分成三个水平：合格水平（符合课标的最低要求），中等以上水平（符合课标的基本要求），优秀水平（符合或超出课标提出的最高要求）。具体如下表：

二、课程设计思路（包括教学方法、手段） “递归算法”课程以故事引入、案例驱动法、示范模仿、启发式等多元化教学方法，设计课程内容。具体的课堂内容如下所示：

1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：若移动速度为1个/秒，则需要 (264-1)/365/24/3600 >= 5849亿年。 四、总结和思考 总结： 对于阶乘这类数值型问题，可以表达成数学公式，然后从相应的公式入手推导，解决这类问题的递归定义，同时确定这个问题的边界条件，找到结束递归的条件。 对于汉诺塔这类非数值型问题，虽然很难找到数学公式表达，但可将问题进行分解，问题规模逐渐缩小，直至最小规模有直接解。 思考： 数值型问题：斐波那契数列的递归设计。 非数值型问题：八皇后问题的递归设计。阐述总结知识拓展 三、教学特色（总结教学特色和效果） 递归算法课程主要讨论递归设计的思想和实现。从阶乘实例入手，由浅入深，层层深入介绍了递归的设计要点和算法的实现。从汉诺塔问题，通过“边提问，边思考”的方式逐层深入地给出算法的分析和设计过程。通过故事引入、案例导入、实例演示、PPT展示、实现效果等“多元化教学方式”，努力扩展课堂教学主战场。加上逐步引导、问题驱动，启发学生对算法的理解，并用实例演示展示算法的分析过程，在编译环境下实现该算法，加深对算法实现过程的认识。 1、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。