数据结构及算法猴子吃桃

《数据结构及算法猴子吃桃》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计说明书课程名称：数据结构与算法设计题目：猴子吃桃问题院系：计算机科学与信息工程系学生姓名：学号：专业班级：指导教师：2010年6月18日课程设计任务书设计题目猴子吃桃问题学生姓名蒋耀辉所在院系计算机科学与信息工程系专业、年级、班08软件工程班设计要求：分别用以下三种方法实现对猴子吃桃问题的求解：（1）数组数据结构（2）链表数据结构（3）递归问题描述如下：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第十天就只剩下一只桃子，求出它们第一天摘了多少桃子。学生应完成的工作：以小组为单位，分工合作

2、完成以下任务（1）编写程序实现对上述猴子偷桃问题的求解并运行出结果；（2）在制定期限内提交程序并完成答辩；（3）提交出详细的课程设计说明书。参考文献阅读：（1）严蔚敏，吴伟民.数据结构（C语言版）—北京：清华大学出版社2007IBSN978-7-302-14751-0；（2）谭浩强.C语言程序教程—北京：清华大学出版社2007.7IBSN978-7-302-15157-9；（3）（美）（Liang，Y.D）C++程序设计—北京：机械工业出版社2008.5IBSN978-7-111-23996-3。工作计划：1、确定自己

3、负责模块的作用2、写出模块算法3、写出源代码4、验证与修改任务下达日期：2010年6月7日任务完成日期：2010年6月18日指导教师（签名）：学生（签名）：（设计题目）摘要：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解关键词：数组链递归目录1.设计背景11.1时代背景11.2能力要求12.设计方案12.1初步分析12.2问题细化23

4、.方案实施23.1初步探讨23.2详细过程24.结果与结论35.收获与致谢36.参考文献37.附件4源程序41.设计背景1.1时代背景数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。为了编写出一个“好”程序，必须分析待处理对象的特性以及各个对象之间存在的关系，“数据结构”正是我们学习这些处理方法的课程。1.2能力要求课程设计是理论

5、学习的补充环节，是对学生所学知识的综合运用能力的检验，也是学生提高分析问题解决问题能力的大好实践时机。通过课程设计，让学生接触社会，深入实际，亲自动手运用所学的专业知识和技巧，去分析、研究、解决这些实际问题，从而灵活运用所学知识，增强实际工作能力，为顺利走向工作岗位打下坚实的基础。数据结构课程设计是在学生学完了《C程序设计教程》课程后开设的一门实践性课程，旨在通过对课程设计从分析、设计到实现的全过程剖析和实践，更好地理解数据结构中的概念和原理，并由此掌握数据结构的基本思路和方法。2.设计方案2.1初步分析用数学方法对问

6、题进行分析，写出详细的问题分析过程。mainAnalysisSwitchInterFaceArrayAnalysisRecursionArralysisLinkListArraysisUseArrayUseLinkListUseRecursion132.2问题细化将问题的数学解决方法及思维转化成C语言数据结构的方法。对问题进行分块设计，分别用C语言实现问题的数组、链表、递归的解决方法。当对程序进行初步调试并能运行得到正确结果时对程序进行进一步的完善，添加适当的模块使程序输出界面清楚明了便于操作。3.方案实施3.1初步探

7、讨问题数学分析：猴子每天都吃当前桃子的一半多一个，假设今天还有n个桃子，则前一天就有（n+1）*2个桃子。又已知第十天只剩下一个桃子，则可代入以上公式求出第九天的桃子数，以此类推求下去便可得到第一天的桃子数。将上述解题过程思维转化为C语言的编程方法，先在草稿纸上列出初步的程序的框架，然后逐步实现。3.2详细过程在电脑上建立一个空的C/C++工程，在工程里分别添加以下文件“MEP.h”,“main.cpp”，“METP.cpp”,“Interface.cpp”，“ProblemAnlysis.cpp”。其中头文件包含所有

8、需要用的的相关函数，其它源文件分别实现不同的功能（详细请参照附件中的源程序）。程序初步完成时对程序各方面进行测试，弥补不足之处最终得到比较完善的程序。134.结果与结论运行结果请参照附件中对程序运行结果的截图。同一问题可以有多个不同的解决路径及方法，但是方法有优劣之分，就本题而言，递归方法最容易写程序最简单，但是其时间复杂度最大，