文档视界 最新最全的文档下载
当前位置:文档视界 › 汉诺塔的动态演示程序

汉诺塔的动态演示程序

汉诺塔的动态演示程序
汉诺塔的动态演示程序

汉诺塔问题的三种实现

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

汉诺塔非递归算法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/8b7528017.html, https://www.docsj.com/doc/8b7528017.html, Tel:+86-551-569096356909648460

数据结构实验报告汉诺塔

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

一、目的与要求 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.实验目的: 通过本实验,掌握复杂性问题的分析方法,了解汉诺塔游戏的时间复杂性和空间复杂性。 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上;

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

汉诺塔递归与非递归算法研究 作者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 实现步骤: 为满足题目中盘子的移动问题,必须遵循的条件是:一次

汉诺塔 面向对象课程设计

数据库课程设计报告------------题目:汉诺塔 学院名称:计算机学院 专业名称:计算机科学与技术 班级:计算机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、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用,并通过“世界末日问题” 故事引入非数值型问题的递归分析,激发学习积极性,挖掘学生潜能。

汉诺塔问题非递归算法详解

Make By Mr.Cai 思路介绍: 首先,可证明,当盘子的个数为n 时,移动的次数应等于2^n - 1。 然后,把三根桩子按一定顺序排成品字型(如:C ..B .A ),再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着,根据圆盘的数量确定桩子的排放顺序: 若n 为偶数,按顺时针方向依次摆放C ..B .A ; 若n 为奇数,按顺时针方向依次摆放B ..C .A 。 最后,进行以下步骤即可: (1)首先,按顺时针方向把圆盘1从现在的桩子移动到下一根桩子,即当n 为偶数时,若圆盘1在桩子A ,则把它移动到B ;若圆盘1在桩子B ,则把它移动到C ;若圆盘1在桩子C ,则把它移动到A 。 (2)接着,把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上,当两根桩子都非空时,移动较小的圆盘。 (3)重复(1)、(2)操作直至移动次数为2^n - 1。 #include #include using namespace std; #define Cap 64 class Stake //表示每桩子上的情况 { public: Stake(int name,int n) { this->name=name; top=0; s[top]=n+1;/*假设桩子最底部有第n+1个盘子,即s[0]=n+1,这样方便下面进行操作*/ } int Top()//获取栈顶元素 { return s[top];//栈顶 } int Pop()//出栈 { return s[top--];

} void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量:"; cin>>n; if(n<1) 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 #include #include int times = 0; void move(char a, char b) { printf("%c > %c \n", a,b); } void hno(int n,char a , char b, char c) { if (n==1) { move(a,c); times ++; } X 移动到塔座 A ; X 移动到塔座 C ; Z 移动到塔座 C 。 Y 移动到塔座 Y 移动到塔座 X 移动到塔座 B ; A ;

汉诺塔程序解读

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 互换。以及下面的代码,得出 ````````````````````````````````````````````````

汉诺塔课程设计报告

汉诺塔游戏 学院:理学院 班级:信科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塔)

问题重述: 有三根柱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 using namespace std; int m=0; void move() { m++; } void I(int n) { if(n==1) move(); else { I(n-1); move(); I(n-1); } } int main() { I(3); cout< using namespace std;

int fact(int n) { if(n==1) return(1); else return((2*fact(n-1)+1)); } int main() { cout< using namespace std; int m=0; void Move(int n,char x,char y) { cout<<"把"<>i; Hannoi(3,'a','b','c'); cout<<"总的搬运次数"<

相关文档