搜档网
当前位置:搜档网 › 栈与递归(下)

栈与递归(下)

栈与递归(下)
栈与递归(下)

数据结构考研真题 栈和队列

第3章栈和队列 一选择题 1. 对于栈操作数据的原则是()。【青岛大学 2001 五、2(2分)】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时,才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1(5分)】【上海海运学院 1999 二、1(5分)】 3. 一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是()。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p 1,p 2 ,p 3 ,…,p N ,若p N 是n,则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1(1.5分)】 6. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?() A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3(2分)】 7. 设栈的输入序列是1,2,3,4,则()不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1,2,4,3, B. 2,1,3,4, C. 1,4,3,2, D. 4,3,1,2, E. 3,2,1,4, 8. 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是()。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2(2分)】 9. 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是()。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1(2分)】 10. 某堆栈的输入序列为a, b,c ,d,下面的四个序列中,不可能是它的输出序列的是

汉诺塔问题的三种实现

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

栈与递归

目录 摘要 (1) 研究背景 (2) 基本概念及特性.......................................................... (2) 栈的运算 (3) 栈的运用举例 (5) 递归原理 (6) 迷宫求解 (8) 栈实现迷宫问题 (8) 递归实现迷宫算法 (8) 参考文献 (9) 附录 (9)

栈与递归的关系 摘要:栈(stack)又称堆栈,他是线性表中的一种特殊情况,并且也是最简单的情况之一,它是一种运算受限的线性表,其限制是仅仅允许在表的一端进行插入和删除运算。由于栈的插入和删除运算仅在栈的一端实现,后进栈的元素必定先出栈,所以又把栈称为后进先出表。 递归是一种非常重要的概念和解决问题的方法,在计算机科学和数学领域有着广泛的应用,递归调用是计算机解决部分疑难问题特别有效,易于实现的一种算法。比如著名的汉诺塔问题、八皇后问题、树的遍历等如果不用递归算法解决,几乎难以实现,大部分计算机语言教材都涉及到这一重要算法。在计算机系统内,执行递归函数是通过栈来实现的,栈中的每一个元素包含有递归函数的每一参数域、每一个局部变量和调用后的返回地址域,其中引用参数域只保存传送来的实参的地址,以便按此地址访问实参的储存空间存取其值,其他的每个域是用于存储其值的实际存储空间,每次进行函数调用的时候,都要把相应的填压入栈,每次结束调用时,都按照本次返回地址返回到指定的位置进行,并且自动做一次退栈操作,使得下一层所使用的参数称为新的栈顶,继续被使用。栈与递归都能够解决一些实际问题,主要是通过C/C++语言来实现编程运算,得到相应的结果。 递归和栈是可以相互转换的,当编写递归算法时,虽然表面上没有使用栈,但是系统执行时会自动建立和使用栈,本文中在求解迷宫问题时就充分的体现出了这一点。 关键词:栈递归C/C++语言迷宫问题

汉诺塔非递归算法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)

递归算法和非递归算法的区别和转换

递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如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) {

算法设计题详解

算法设计的特征:有穷性,确定性,输入和输出,可行性 运行算法的时间:硬件的速度。书写程序的语言。问题的规模,编译生成程序的代码质量算法复杂度: 时间复杂度和空间复杂度 1.迭代法 迭代法又称为辗转法,是用计算机解决问题的一种基本方法,为一种不断用变量的旧值递推新值的过程,与直接法相对应,一次性解决问题。迭代法分为精确迭代和近似迭代,“二分法”和“牛顿迭代法”属于近似迭代法。迭代法利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 利用迭代算法解决问题,需要做好以下三个方面的工作: 1.确定迭代变量(在可以用迭代算法解决的问题中,至少存在一个直接或间接地 不断由旧值递推出新值的变量,这个变量就是迭代变量。) 2. 建立迭代关系式(所谓迭代关系式,指如何从变量的前一个值推出其下一个值 的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以顺推 或倒推的方法来完成。) 3.对迭代过程进行控制(在什么时候结束迭代过程?这是编写迭代程序必须考虑 的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为 两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所 需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实 现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程 的条件。) 2.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。 即本方法使用可以理解为暴力循环方法,穷举所有可能性,一般这种方法的时间效率太低,不易使用。但是方法简单,易理解。 3.递推法 递推是计算机数值计算中的一个重要算法,思路是通过数学推导,将复杂的运算化解为若干重复的简单运算,以充分发挥计算机长于重复处理的特点。递推法: 递推法实际上是一种递推关系,就是为了得到问题的解,把它推到比原问题简单的 问题求解,可分为顺推法和倒推法。 i.顺推法,就是先找到递推关系式,然后从初始条件出发,一步步地按 递推关系式递推,直至求出最终结果。 ii.倒推法,就是在不知道初始条件的情况下,经某种递推关系而获知问题的解,再倒过来,推知它的初始条件。 4.递归法(递推加回归) 一个过程或函数在其定义或说明中又间接或间接调用本身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题类似的规模较小的问题来求解,递 归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了 程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想 写出的程序往往十分简洁易懂。 一般来说,递归需要有边界条件、递归前进段和递归前往段。当边界条件不满脚时,递归前进;当边界条件满脚时,递归前往。

c语言迷宫问题的求解(栈和递归)

实验报告 【实验名称】项目一迷宫问题的求解 【实验目的】 1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体 的运用。 2.学会用栈或者递归方法解决迷宫问题。 【实验原理】 1.本次实验中,以二维数组maze[row][col]表示迷宫,0表示通路,1表示墙,在构建迷宫时,为了清晰显示,在最外层添加一圈墙。 2.算法的核心思想是利用栈后进先出的特点,对迷宫进行探索,如果此路可行,则将此坐标的信息入栈,如果此路不通,则将此坐标的信息出栈。 3.输入形式:根据控制台的提示,依次输入迷宫的行数、列数,然后输入迷宫,再输入入口和出口坐标。 4.输出形式:由用户选择,由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案,并给出相应的三元组序列和迷宫方阵;以递归方式则会显示出所有的路线。 【实验内容】 1.需求分析 (1)问题描述 以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 要求以递归和非递归两种方式分别输出一条迷宫的通路,以带方向坐标和迷宫图像表示。

(2)基本要求 (1)首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如,对于下列数据的迷宫,输出一条通路为:(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),…。 (2)编写递归形式的算法,求得迷宫中所有可能的通路。 (3)以方阵形式输出迷宫及其通路。 2.概要设计 (1)栈的抽象数据类型 ADT Stack{ 数据对象:D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系:R1={|ai-1,ai∈D, i=1,2, …,n } 约定an端为栈顶,a1端为栈底。 基本操作: InitStack( &S ) 操作结果:构造一个空栈S。 DestroyStack ( &S ) 初始条件:栈S已存在。 操作结果:销毁栈S。 ClearStack( &S ) 初始条件:栈S已存在。 操作结果:将S清为空栈。 StackEmpty( S ) 初始条件:栈S已存在。 操作结果:若S为空栈,则返回TRUE,否则返回FALSE。 StackLength( S ) 初始条件:栈S已存在。 操作结果:返回S的数据元素个数,即栈的长度。 GetTop( S, &e ) 初始条件:栈S已存在且非空。 操作结果:用e返回S的栈顶元素。 Push( &S, e ) 初始条件:栈S已存在。 操作结果:插入元素e为新的栈顶元素。 Pop( &S, &e ) 初始条件:栈S已存在且非空。 操作结果:删除S的栈顶元素,并用e返回其值。 }ADT Stack (2)程序模块

汉诺塔问题

实验二知识表示方法 梵塔问题实验 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 #include using namespace std; void main() { void hanoi(int n,char x,char y,char z);

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<<"盘子从"<

递归算法详解

递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构,如果在其定义或说明内部直接或间接地出现对其本身的引 用,或者是为了描述问题的某一状态,必须要用至它的上一状态,而描述上一状态,又必须用到它的上一状态……这种用自己来定义自己的方法,称之为递归或递归定义。在程序设计中,函数直接或间接调用自己,就被称为递归调用。 二、递归的最简单应用:通过各项关系及初值求数列的某一项。 在数学中,有这样一种数列,很难求出它的通项公式,但数列中各项间关系却很简单,于是人们想出另一种办法来描述这种数列:通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式,至少要提供两个信息:一是最前面几项的数值,一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它,应该是: ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值,那么可以很容易地写成这样:

这就是递归函数的最简单形式,从中可以明显看出递归函数都有的一个特点:先处理一 些特殊情况——这也是递归函数的第一个出口,再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模,直到简单到可以作为 特殊情况处理而得出直接的结果,再通过递归关系逐层返回到原来的数据规模,最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时,由于3不是特殊值,因此需要计 算)2(*3f ,但)2(f 是对它自己的调用,于是再计算)2(f ,2也不是特殊值,需要计算 )1(*2f ,需要知道)1(f 的值,再计算)1(f ,1是特殊值,于是直接得出1)1(=f ,返回上 一步,得2)1(*2)2(==f f ,再返回上一步,得62*3)2(*3)3(===f f ,从而得最终解。 用图解来说明,就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为

栈与递归的关系

栈与递归的关系 姓名:郭小兵 学号:1007010210 专业:信息与计算科学院系:理学院 指导老师:彭长根 2012年10月17日

栈与递归的关系 郭小兵 摘要递归是计算机科学中一个极为重要的概念,许多计算机高级语言都具有递归的功能,对于初学计算机者来讲,递归是一个简单易懂的概念,但真正深刻理解递归,正确自如的运用递归编写程序却非易事,本文通过一些实例来阐述递归在计算机内的实现及递归到非递归的转换,也许使读者能加深对递归的理解。 关键词栈递归非递归 引言递归是一种程序设计的方式和思想。计算机在执行递归程序时,是通过栈的调用来实现的。栈,从抽象层面上看,是一种线性的数据结构,这中结构的特点是“先进后出”,即假设有a,b,c三个元素,依次放某个栈式存储空间中,要从该空间中拿到这些元素,那么只能以c、b、a的顺序得到。递归程序是将复杂问题分解为一系列简单的问题,从要解的问题起,逐步分解,并将每步分解得到的问题放入“栈”中,这样栈顶是最后分解得到的最简单的问题,解决了这个问题后,次简单的问题可以得到答案,以此类推。分解问题是进栈(或者说压栈)的过程,解决问题是一个出栈的过程。 科学家对栈与递归都做了很多深入的研究,研究表明“递归算法

和栈都有后进先出这个性质,基本上能用递归完成的算法都可以用栈完成,都是运用后进先出这个性质的”这个性质可用于进制的转换。与汇编程序设计中主程序和子程序之间的链接及信息交换相类似,在高级语言编制的程序中,调用函数和被调用函数之间的链接及信息交换需过栈来进行。递归是计算科学中一个极为重要的概念。许多计算机高级语言都具有递归的功能,本文将通过一些是例来阐述递归在计算机内的实现及递归到非递归的转换,也许能加深对递归的理解。递归是某一事物直接或间接地由自己完成。一个函数直接或间接地调用本身,便构成了函数的递归调用,前者称之为直接递归调用,后者为间接递归调用。递归会使某些看起来不容易解决的问题变得容易解决。特别当一个问题蕴含递归特性且结构比较复杂时,采用递归算法往往要自然、简洁、清晰,写出的程序较为简短。在很多时候,程序结构简单,可读性好甚至比运行时间更重要,所以掌握递归算法也就存在一定的必要性。但许多人,特别是计算机专业低年级和一些初学者,往往觉得递归很难理解。为了更好地掌握他,了解递归过程的操作原理就更有意义了。

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

一、教学思想(包括教学背景、教学目标) 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.每一组输入数据包括:汽车“到达”或“离去”信息、汽车牌照号码以 及到达或离去的时刻。 2.输出信息:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用。 3.测试数据 设n=2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3,20),(‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。其中:‘A’表示到达;‘D’表示离去;‘E’表示输入结束。 4.【选作内容】:两个栈共享空间,思考应开辟数组的空间是多少? 5.【选作内容】:停放在便道上的汽车也收费,收费标准比停放在停车场的车。 实习二栈、队列和递归算法设计 题目:停车场管理实习时间:2012/10/14 一、需求分析 1.每一组输入数据包括:汽车“到达”或“离去”信息、汽车牌照号码以 及到达或离去的时刻。 2.输出信息:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用。 3.测试数据 设n=2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3,20),(‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。其中:‘A’表示到达;‘D’表示离去;‘E’表示输入结束。 4.【选作内容】:两个栈共享空间,思考应开辟数组的空间是多少? 5.【选作内容】:停放在便道上的汽车也收费,收费标准比停放在停车场的车。 二、设计 二、 1. 设计思想 二、(1)存储结构 以栈模拟停车场,以队列模拟车场外的便道。栈以顺序结构实现,队列以链表结构实现。 不需另设一个栈,栈顶空间临时停放为将要离去的汽车让路而从停车场退出来的汽车,栈用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含三个数据项:汽车的牌照号码停车时刻和进入停车场的时刻。 (2)主要算法基本思想 按照顺序(两栈共享空间)栈和链式队列的基本操作,初始化一个栈和一个队列,若车辆进站,先判断车站是否满,未满就进车站,满了就进过道:若车辆离开,先在站中找到该车辆,再判断队列是否空,若非空则将车从过道进到站中并记录进站的时间;若不进行车辆的进出则终止程序。 2. 设计表示 (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<<"输入的盘子数量错误!!!"<

数据结构利用栈实现递归

利用栈实现递归参考程序1(Turbo2.0环境): #define MAXSIZE 100 #include struct stack{ int data[MAXSIZE]; int top; }; void init(struct stack *s){ s->top=-1; } int empty(struct stack *s){ if(s->top==-1) return 1; else return 0; } void push(struct stack *s,int i){ if(s->top==MAXSIZE-1){ printf("Stack is full\n"); return; } s->top++; s->data[s->top]=i; } int pop(struct stack *s){ if(empty(s)){ printf("stack is empty"); return -1; } return(s->data[s->top--]); } void trans(int num){ struct stack s; int k; init(&s); while(num){ k=num%16; push(&s,k); num=num/16; } while(!empty(&s)){ k=pop(&s); if(k<10)

printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ int num; clrscr(); printf("Input a num,-1 to quit:\n"); scanf("%d",&num); while(num!=-1){ trans(num); scanf("%d",&num); } } 参考程序2:(C++/VC环境) #define STACK_INIT_SIZE 100//存储空间初始分配量 #define OVERFLOW -1 #define OK 1 #define STACKINCREMENT 10//存储空间分配增量 #define ERROR 0 #define TRUE 1 #define FALSE 0 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "iostream.h" typedef int status; typedef char SElemType; typedef struct{//顺序栈的定义 SElemType *base; 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; }

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

汉诺塔递归与非递归算法研究 作者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个盘的汉

递归算法详解

递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归。但是在阶乘的计算里,递归并没有提供任何优越之处。在菲波那契数列中,它的效率更是低的非常恐怖。 这里有一个简单的程序,可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如:给出一个值4267,我们需要依次产生字符‘4’,‘2’,‘6’,和‘7’。就如在printf函数中使用了%d格式码,它就会执行类似处理。 我们采用的策略是把这个值反复除以10,并打印各个余数。例如,4267除10的余数是7,但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中,字符‘7’的值是55,所以我们需要在余数上加上48来获得正确的字符,但是,使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48,所以我们用余数加上‘0’,所以有下面的关系: ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中,我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值,4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反,它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看,函数似乎永远不会终止。当函数调用时,它将调用自身,第2次调用还将调用自身,以此类推,似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是,事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展,逐步迫近循环终止条件。递归函数也是如此,它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时,它便不在调用自身。 在程序中,递归函数的限制条件就是变量quotient为零。在每次递归调用之前,我们都把quotient除以10,所以每递归调用一次,它的值就越来越接近零。当它最终变成零时,递归便告终止。 /*接受一个整型值(无符号0,把它转换为字符并打印它,前导零被删除*/

递归算法工作栈的变化详解

通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点".

相关主题