资源描述：
《【精品】数据结构论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、我濮二理2尊级课程（设计）论文阿克曼函数题目专业班级学号学生姓名指导教师指导教师职称学院名称完成日期：年月曰录耍II言II章绪论1课题背景2课题意义3文献综述2章课题的具体分析及程序的实现1课题分析12递归算法32.1递归32.2递归算法程序的设计32.3实验结果33利用栈的菲递归算法93.1栈93.2主要成员函数的设计93.3利用栈的非递归算法程序的设计883.4实验结果994算法的复杂性分析105存在的问题及改进103章总结11谢11参考文献15摘要“数据结构”是计算机程序设计的重要理论技术基
2、础，它是计算机学科的核心课程。用数据结构中的知识、算法、思想解决一些实际问题可使得一些问题变得一H了然，易懂。本课程设计的目的是通过C++语言平台实现阿克曼函数问题的算法设计，采用递归调用和以栈作为存储的非递归调用的方法解决，使抽象的数学问题程序化，并-I-IT然，更便于理解。关键词：数据结构，阿克曼函数，递归，非递归冃
3、JR本文解决了递归和非递归方法实现阿克曼函数的问题，同时在非递归调用时利用了栈作为元素的存储空间。全文共3章，详细的介绍了对本课题的算法设计过程及类容。第1章介绍了课题背景和课题
4、的意义。在本章中，还给出了我们查阅并借用的一些参考文献的主要内容。第2章主要介绍了课题的分析与算法的设计，对存在的问题作了简要分析并予以改进以及算法的复朵性的分析。第3章是木次课程设计的总结。全文的最后是致谢、参考文献和对程序优化处理的源代码。高金金2011-1-6武汉T程大学理学院in第1章课题背景1・1课题背景阿克曼函数是数学中的经典问题，是非原始递归函数的例了。已知其函数定义如下：h+1m=0cin)0,n=0ahi(m一1,dkn(m.n一1))m>0,«>0现
5、要求：(1)、根据定义，写出它的递归求解算法；(2)、利用栈，写出它的非递归求解算法。1.2课题意义通过木问题的探究与设计，培养了学生对算法分析的能力，同时加强锻炼了学生以计算机编程解决数学复朵问题，达到了跨学科知识的联系与运用，以及理论与实际的相结合。另外，对栈的理解与运用有了更深的理解与掌握，同时对比分析相同问题采用不同方法解决的优缺性，对学生今后学习与实践有很人的帮助。1.3文献综述文献［1］介绍了栈的基本概念，给出了栈的定义，较为详细地介绍了实现的数据结构，本文中的许多程序的编写均参考了该
6、书中的相关内容，这是一本关于以面向对象的思想，用C++语言來描述数据结构的经典教材，给了我很大的帮助。文献［2］介绍了C++的一些算法和应用，是C++的入门教材。文献［3］给出许多数据结构的应用问题以及这些问题的求解程序，具有很人的参考价值。第2章课题的具体分析及程序的实现1.1课题分析阿克曼函数(AckeTman)是非原始递归函数的例子；它需要两个自然数作为输入值，输出一个自然数。然后，就是递归转非递归的标准流程：a从一个简单的实例，分析其递归调用树；b•分析哪些元素需要放在栈中；c.跟踪递归调
7、用过程，分析栈的变化；d・由实例・＞普通，演绎出算法，这一过程也称作建模。卜湎，我们就以akm(2,l)为例，开始分析递归调用树，采用一个栈记忆每次递归调用时的实参值，每个结点两个域。对以上实例，递归树以及栈的变化如下：实例:akm(2,l)=(2,l)=(1,(2,0))=(1,(1,1))=(1,(0,(1,0)))=(1,(0,(0,1)))=(1,(0,2))=(1,3)=(0,(0,3))=5图2.1栈的变化A(m,/?)的值m01234n012345n+11234562+(n+3)
8、-323579112.(n+3)-3351329611252(“+3)_3413655332^5536_3A(3,265536-3)A(3,A(4,3))222*-3兀+3twos565533A(4,65533)A(4,A(5,1))A(4,A(5,2))A(4,A(5,3))61A(5,1)14(5,4(5,1))iA(5,A(6,1))1A(5,A(6,2))1jA(5,A(6,3))图2.2函数值表1.2递归算法2.2.1递归定义：为一种算法在程序设计语言中广泛应用•是指函数/过程/子程序在
9、运行过程序屮直接或间接调用门身而产生的重入现像.程序调用£1身的编程技巧称为递归。一个过程或函数在其定义或说明中又直接或间接调用口身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题和似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，人人地减少了程序的代码量。递归的能力在于用有限的语句來定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条
