汉诺塔非递归算法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)
return 0;
else
{
S->top--;
*n=S->top->n;
*x=S->top->x;
*y=S->top->y;
*z=S->top->z;
return 1;
}
}
int EmptyStack(Stack *S)
{
if(S->base==S->top)
return 1;
else
return 0;
}
int i=1;
void Move(char x,char z)
{
printf("\n\n\t\t第%d部，从%c移到%c。",i++,x,z);
}
int main()
{
int n;
char x,y,z;
Stack *S;
S=(Stack *)malloc(sizeof(Stack));
if(!S)
return 0;
if(!InitStack(S))
return 0;
printf("\n\n\t\t请输入汉诺塔的初始盘子数量以及轴的名称：");
scanf("%d%c%c%c",&n,&x,&y,&z);
if(!PushStack(S,n,x,y,z))
return 0;
while(!EmptyStack(S))
{
if(!PopStack(S,&n,&x,&y,&z))
break;
if(n==1)
{
Move(x,z);
}
else
{
if(!PushStack(S,n-1,y,x,z))
break;
if(!PushStack(S,1,x,y,z))
break;
if(!PushStack(S,n-1,x,z,y))
break;
}
}
free(S->base);
S->base=NULL;
S->top=NULL;
S->stacksize=0;
return 0;
}
计算机科学与工程学院 《算法与数据结构》试验报告[二] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-4-14 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（） 试验目的及要求（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。 成 绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告程序代码规范、功能正确 报告详实完整、体现收获 70分 备注： 评阅教师： 日期：年月日
试 验 内 容 一、实验目的和要求 1、实验目的： （1）掌握栈的特点及其存储方法； （2）掌握栈的常见算法以及程序实现； （3）了解递归的工作过程。 2、实验内容 Hanoi 塔问题。（要求4个盘子移动，输出中间结果） 3、实验要求： 要求实现4个盘子的移动，用递归和栈实现。 二、设计分析 三个盘子Hanoi 求解示意图如下： 三个盘子汉诺塔算法的运行轨迹： B A B C A B C A C A B C (a (b) (c (d) ⑸ ⑼ ⑶ Hanio(3,A,B,C) Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(2,A,C,B) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,C,A,B) Move (C,B) Move (A,B) Hanio(2,B,A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (B,A) 递归第一层 递归第二层 递归第三层 ⑴ ⑵ ⑷ ⑹ ⑺ ⑻ ⑽ ⑾ ⑿ ⒀ ⒁
递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习
递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) {
// 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 汉诺塔非递归算法C语言实现 #include n！非递归算法的设计与实现 1 课题描述 尽管递归算法是一种自然且合乎逻辑的解决问题的方式，但递归算法的执行效率通常比较差。因此在求解许多问题时常采用递归算法来分析问题，用非递归方法来求解问题；另外一些程序不支持递归算法来求解问题，所以我们都会用非递归算法来求解问题。 本次课程设计主要内容是：用非递归算法实现n!的计算，由于计算机中数据的存储范围有限，而又要求出尽可能大的n的阶乘的值，用数组构造n的运算结果的存储结构,用栈的存储方式，最后输出n!的运算结果。 本次课程设计的目的是：通过本次课程设计，可以使大家了解缓存中数据的存储范围，提高自学能力，增强团队合作意识。 2 需求分析 本次n!非递归算法的课程设计中主要用到的知识有：数组、函数、栈，选择条件中的结构语句（if…else），和循环结构语句中的语句while()语句、do…while()语句和for()语句，选择语句if的运用。 对n!的非递归的算法，主要是运用非递归的算法实现n的阶乘。 限制条件： (1).要求的n必须是整数； (2). n的范围； (3). 数据类型和表数范围。 递归和非递归算法是相通的，递归是一种直接或间接调用自身的算法，而非递归不调用自身函数递推采用的是递归和归并法，而非递推只采用递归法。递推法一般容易溢出，所以一般都采用递推法分析，而用非递推法设计程序。 将n定义为float型，便于查看n是否为整数； 本次试验分为两个模块： (1).当n小于都等于12时，实现阶乘的模块m(n): 直接用sum*=i;实现求n的阶乘，相对简单，容易就算。 (2).当n大于12时，如果用long型结果就会溢出，所以实现阶乘需调用的模块f(n): 采用数组存放计算的结果，用队列输出运行结果。由于计算结果较大，将结果除以数组最大存储位数，将高位结果存放在数组的起始地址上，将低位的结果存放在数组的末端地址上，最后采用队列输出运行结果。 (3).模块调用关系如图3.1所示 图3.1 模块调用图 课程设计报告 课程设计名称：C语言课程设计 课程设计题目：汉诺塔问题求解演示 院（系）：计算机学院 专业：计算机科学与技术 班级： 学号： 姓名： 指导教师： 完成时间：2010年3月18日 沈阳航空航天大学课程设计报告 目录 第1章需求分析 (3) 1.1 课程设计的题目及要求 (3) 1.2 总体分析 (3) 第2章系统设计 (4) 2.1 主要函数和函数功能描述 (4) 2.2 功能模块图 (4) 第3章详细设计 (5) 3.1主函数流程图 (5) 3.2各功能模块具体流程图 (6) 第4章调试分析 (10) 4.1.调试初期 (10) 4.2.调试中期 (10) 4.3.调试后期 (10) 参考文献 (11) 附录 (12) 第1章需求分析 1.1 课程设计的题目及要求 题目：汉诺塔问题求解演示 内容： 在屏幕上绘出三根针，其中一根针上放着N个从大到小的盘子。要求将这些盘子从这根针经过一个过渡的针移到另外一根针上，移动的过程中大盘子不能压在小盘子上面，且一次只能移动一个盘子。要求形象直观地演示盘子移动的方案和过程。 要求： 1）独立完成系统的设计，编码和调试。 2）系统利用C语言实现。 3）安照课程设计规范书写课程设计报告。 4）熟练掌握基本的调试方法，并将程序调试通过 1.2总体分析 本题目需要使用C语言绘制图形，所以需要turbo C，需要绘图函数，而汉诺塔的函数属于经典的函数，在书本上都学习过，所以这个题目的难点在于需要绘制汉诺塔图形。攻克这一点其他的问题都迎刃而解。但是我个人以前也没有学过一些关于turboC 方面的知识。所以我将重点放在了对#include 一、教学思想（包括教学背景、教学目标） 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、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。 实验二知识表示方法 梵塔问题实验 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<<"盘子从"< 汉诺塔递归与非递归算法研究 作者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个盘的汉 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 } 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<<"输入的盘子数量错误!!!"< 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 <> void print_star(void) { printf("*****************\n"); } void print_welcome(void) { printf("C language,welcome!\n"); } void main() { print_star(); print_welcome(); print_star(); getchar(); } 演示2 #include "" int sum(int i,int j) { return(i + j); } void main() { int n1,n2; printf("input 2 numbers:\n"); scanf("%d%d",&n1,&n2); printf("the sum = %d\n",sum(n1,n2)); getchar(); } 演示3 #include "" int maxnum(int,int,int); main() { int a,b,c; printf("Please enter 3 numbers:\n"); scanf("%d,%d,%d",&a,&b,&c); printf("Maxnum is %d\n",maxnum(a,b,c)); return 0; } int maxnum(int x,int y,int z) { int max=x; if(y>max) max = y; if(z>max) max = z; return max; } 演示4 #include <> int s1(int n) { int j,s; s=0; for(j=1;j<=n;j++) s=s+j; return s; } int sum(int n) { int i,s=0; for(i=1;i<=n;i++) s=s+s1(i); return s; } void main() { int n; printf("n:"); scanf("%d",&n); printf("s=%d\n",sum(n)); } 演示5 #include <> #include ny=sta.p[top].y+Htry2[z]; sta.p[top].dir=z; top++; sta.p[top].x=nx; sta.p[top].y=ny; board [nx][ny]=top; chech [nx][ny]=true; z=-1; } else if(z==7)//如果不可行，而且是最好一次检查 { chech [sta.p[top].x][sta.p[top].y]=false; top--; while(1) { z=sta.p[top].dir; if(z!=7) break; else { chech [sta.p[top].x][sta.p[top].y]=false; top--; } } } if(top==-1||top==63)break;//如果回溯到-1，或者栈满，则退出循环 z++; } for(i=0;i<8;i++) { for(j=0;j<8;j++) cout< 演示1 #include return 0; } int maxnum(int x,int y,int z) { int max=x; if(y>max) max = y; if(z>max) max = z; return max; } 演示4 #include 课程实践报告 题目：汉诺塔 姓名： 学号： 班级： 日期： 一实践目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力； 2、进一步提升C语言的应用能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 6、提升文档写作能力。 二问题定义及题目分析 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A，B，C。A杆上有若干圆盘。2.每次移动一块圆盘，小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。 程序所能达到的功能： 用户只需要输入所需的层数即可，程序会自动计算出最终需要的步骤，并同时给出中间移动的过程。 三概要设计 1、设计思想 如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。 2、数据类型 结构体：用来存放盘子的栈。同时，在函数的参数中还用到了结构体类型的引用。 其他类型：基本的数据类型，包括整形，字符型。用来存放临时变量。 3、主要模块 第六章树二叉树 后序遍历的非递归算法。在对二叉树进行后序遍历的过程中，当指针p 指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之后，再次搜索到该结点时(该结点的地址通过退栈得到) ，还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈，引入一个标志变量nae,有0 表示该结点暂不访问 1 表示该结点可以访问标志flag 的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈,其中, STACKlCM] 存放进栈结点的地址, STACK2[M] 存放相应的标志n 昭的值, 两个堆栈使用同一栈顶指针top , top 的初值为— 1 。 具体算法如下： #defineH 100 /?定义二叉树中结点最大数目。/ voidPOSTOiRDER(BTREET) { / *T 为二叉树根结点所在链结点的地址。/ BTREESTACKl[H] , p=T ；intSTACK2[M] , flag,top= —1；if(T!=NULL) d0{ while(p!=NULL){ STACK/[++top]=p ; /?当前p所指结点的地址进栈?/ STACK2[top]= 0 ; /,标志0 进栈?/ p=p->lchild ；/?将p 移到其左孩子结点x/ } p=STACKl[top) ；flag=STACK2[top--] ；if(flag==0){ STACKl[++top]=p ; /,当前p所指结点的地址进栈。/ STACK2[toP]=1 ; /?标志1 进栈?/ p=p->rchild ; /x将p移到其右孩子结点o/ } else{ VISIT(p) ; /x访问当前p所指的结点x/ p=NULL ； } }while(p!=NULLtttop!=-1) ； } 不难分析,上述算法的时间复杂度同样为O(n) 7．6．3 二叉树的线索化算法 对--X 树的线索化,就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程, 因此, 二叉树的线索化过程只能 在对二叉树的遍历过程中进行。 下面给出二叉树的中序线索化的递归算法。算法中设有指针pre,用来指向中序遍历过 程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点， 但在算法执行过程中，T总是指向当前访问的结点。voldlNTHREAD(TBTREET) { TBTREE pre ； if(T!=Null){ INTHREAD(T —>lchild)； if(T —>rchild==NULL) 汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且 f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下， 18446744073709551615/31556952=584554049253.855年 这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 算法介绍 其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n –1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C； 若n为奇数，按顺时针方向依次摆放 A C B。 （1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。 （2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C ○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树； 若D不为空集，则R为{H}，H是如下二元关系； （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； （3）若D1不为空，则D1中存在唯一的元素x1，汉诺塔非递归算法C语言实现
n!非递归算法的设计与实现
c语言课程设计--汉诺塔
汉诺塔问题与递归思想教学设计
汉诺塔问题
汉诺塔问题的非递归算法分析
汉诺塔问题非递归算法详解
汉诺塔问题实验报告
C语言程序设计 入门源代码代码集合
马踏棋盘非递归算法
C语言程序设计-入门源代码代码集合
课程实践报告_汉诺塔
后序遍历的非递归算法.doc
c语言汉诺塔
用递归和非递归算法实现二叉树的三种遍历
相关主题
文本预览