《数据结构与算法 猴子吃桃》由会员分享，可在线阅读，更多相关《数据结构与算法 猴子吃桃（17页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 说 明 书课程名称： 数据结构与算法 设计题目： 猴子吃桃问题 院 系：计算机科学与信息工程系学生姓名： 学 号： 专业班级： 指导教师： 2010年 6月18日课 程 设 计 任 务 书设计题目猴子吃桃问题学生姓名蒋耀辉所在院系计算机科学与信息工程系专业、年级、班08软件工程班设计要求：分别用以下三种方法实现对猴子吃桃问题的求解：（1）数组数据结构 （2）链表数据结构（3）递归问题描述如下：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第十天就只剩下一只桃子，求出它们第一天摘了多少桃子。学生应完成的工作：以小组为单位，分工合作完成以下任务（1）编写程序实
2、现对上述猴子偷桃问题的求解并运行出结果；（2）在制定期限内提交程序并完成答辩；（3）提交出详细的课程设计说明书。参考文献阅读：（1）严蔚敏，吴伟民.数据结构（C语言版）北京：清华大学出版社2007IBSN978-7-302-14751-0；（2）谭浩强.C语言程序教程 北京：清华大学出版社 2007.7 IBSN978-7-302-15157-9；（3）（美）（Liang，Y.D）C+程序设计 北京：机械工业出版社 2008.5 IBSN978-7-111-23996-3。工作计划：1、确定自己负责模块的作用 2、写出模块算法 3、写出源代码 4、验证与修改任务下达日期： 2010 年 6 月
3、 7 日 任务完成日期： 2010 年 6 月 18 日指导教师（签名）： 学生（签名）： （设计题目）摘 要：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解关键词：数组 链 递归 目 录1. 设计背景11.1时代背景11.2能力要求12.设计方案12.1初步分析12.2 问题细化23. 方案实施23.1初步探讨23.2 详细过程24.结果与结论35. 收获与致谢36. 参考文献37. 附件4源程序41. 设
4、计背景1.1时代背景数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。为了编写出一个“好”程序，必须分析待处理对象的特性以及各个对象之间存在的关系，“数据结构”正是我们学习这些处理方法的课程。1.2能力要求课程设计是理论学习的补充环节，是对学生所学知识的综合运用能力的检验，也是学生提高分析问题解决问题能力的大好实践时机。通过课程设计，让学生接触社会，深入实际，亲自动手运用所学的专业知识和技巧，去分析、研究、
5、解决这些实际问题，从而灵活运用所学知识，增强实际工作能力，为顺利走向工作岗位打下坚实的基础。数据结构课程设计是在学生学完了C程序设计教程课程后开设的一门实践性课程，旨在通过对课程设计从分析、设计到实现的全过程剖析和实践，更好地理解数据结构中的概念和原理，并由此掌握数据结构的基本思路和方法。2.设计方案2.1初步分析 用数学方法对问题进行分析，写出详细的问题分析过程。mainAnalysisSwitchInterFaceArrayAnalysisRecursionArralysisLinkListArraysisUseArrayUseLinkListUseRecursion2.2 问题细化将问题
6、的数学解决方法及思维转化成C语言数据结构的方法。对问题进行分块设计，分别用C语言实现问题的数组、链表、递归的解决方法。 当对程序进行初步调试并能运行得到正确结果时对程序进行进一步的完善，添加适当的模块使程序输出界面清楚明了便于操作。3. 方案实施3.1初步探讨问题数学分析：猴子每天都吃当前桃子的一半多一个，假设今天还有n个桃子，则前一天就有（n+1）*2个桃子。又已知第十天只剩下一个桃子，则可代入以上公式求出第九天的桃子数，以此类推求下去便可得到第一天的桃子数。将上述解题过程思维转化为C语言的编程方法，先在草稿纸上列出初步的程序的框架，然后逐步实现。3.2 详细过程在电脑上建立一个空的C/C+
7、工程，在工程里分别添加以下文件“MEP.h”,“main.cpp”，“METP.cpp”,“Interface.cpp”，“ProblemAnlysis.cpp”。其中头文件包含所有需要用的的相关函数，其它源文件分别实现不同的功能（详细请参照附件中的源程序）。程序初步完成时对程序各方面进行测试，弥补不足之处最终得到比较完善的程序。4.结果与结论 运行结果请参照附件中对程序运行结果的截图。同一问题可以有多个不同的解决路径及方法，但是方法有优劣之分，就本题而言，递归方法最容易写程序最简单，但是其时间复杂度最大，运行速度慢。本题链表法和数组法时间复杂度相当，但是一个是动态的存储结构，一个是静态的存储
8、结构，各有各的长处和短处。 所以解决问题时要仔细分析，从多种不同的方法中找出最优的一种，以提高解决问题的效率。5. 收获与致谢通过本次课程设计，让我们接触，深入实际，亲自动手运用所学的专业知识和技巧，去分析、研究、解决这些实际问题，从而灵活运用所学知识，增强了实际编程能力，为顺利走向工作岗位打下坚实的基础。通过对课程设计从分析、设计到实现的全过程剖析和实践，更好地理了解数据结构中链表，数组，以及递归的概念和原理，并由此掌握数据结构的基本思路和方法。在此，对我们数据结构老师冯慧玲女士的精心教学与辅导表示诚挚的感谢！6. 参考文献1 严蔚敏，吴伟民.数据结构（C语言版）北京：清华大学出版社2007
9、IBSN978-7-302-14751-0.2 谭浩强.C语言程序教程 北京：清华大学出版社 2007.7 IBSN978-7-302-15157-9.3（美）（Liang，Y.D）C+程序设计 北京：机械工业出版社 2008.5 IBSN978-7-111-23996-37. 附件源程序1）Header Files MEP.H#ifndef MEP_H#define MEP_H#include#includeusing namespace std;typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;void UseL
10、inkList();int UseRecursion(int n);int Swicth();void InterFace();void UseArray();void Analysis();void LinkListAnalysis();void RecursionAnalysis();void ArrayAnalysis();static unsigned short arr10=0,0,0,0,0,0,0,0,0,1;#endif MEP_H;#includeMEP.h2)main .cppvoid main() InterFace(); 3)Interface.CPP#includeM
11、EP.hvoid InterFace()cout 猴子吃桃子问题 nn; cout有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一n;cout半且再多吃一个，到了第10天就只余下一个桃子。用多n;cout种方法实现求出原来这群猴子共摘了多少个桃子。n; cout要求：n; cout(1)采用数组数据结构实现上述求解n; cout(2)采用链数据结构实现上述求解n; cout(3)采用递归实现上述求解n;cout(4)退出程序。n; Swicth();int Swicth()Analysis();int n; for(; ;)coutn;if(n4)cout输入错误！请重新输入。;switch(
12、n)case 1: ArrayAnalysis();break;case 2:LinkListAnalysis();break;case 3:RecursionAnalysis();break;case 4:return 0;4)ProblemsAnalysis.cpp#includeMEP.hvoid Analysis()cout问题分析：n;cout猴子每天都吃当前桃子的一半多一个，假设今天还有nn;cout个桃子，则前一天就有（n+1）*2个桃子。又已知第十n;cout天只剩下一个桃子，则可代入以上公式求出第九天的n;cout桃子数，以此类推求下去便可得到第一天的桃子数。n;coutn;
13、void LinkListAnalysis()cout链表法采用后序插入的方法，先创建一个空的链表n;cout每次生成一个新的节点存储当前桃子数然后插入表n;cout头。最后生成的链表的头结点指向的下一个节点存n;cout储的关键字便为第一天的桃子数。n;cout最终结果为：;UseLinkList();coutn;void RecursionAnalysis()cout采用递归的方法求解关键在于写递归函数，函数n;cout应定为int型，每次递归上次函数的返回值参与本n;cout次的运算。最后当递归函数返回到第一层最终所得n;cout的结果变为第一天的桃子数。n;cout其结果为：; coutUseRecursio
