数据结构课程设计--猴子吃桃问题.doc

山东交通学院 数据结构设计 猴子吃桃问题 院(系)别 信息科学与电气工程学院 班 级 计算113 学 号 姓 名 王军 指导教师 王成 时 间 2012-03-09—2012-03-20 课 程 设 计 任 务 书 题 目 猴子吃桃 院 (部) 信息科学与电气工程学院 专 业 计算机科学与技术 班 级 学生姓名 学 号 3 月 9 日至 3 月 20 日 共 2 周 指导教师(签字) 王成 系 主 任(签字) 2015年 月 日  设计内容及要求 这个程序的内容是以C语言为程序语言载体分别用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。 设计原始资料 在这个程序中我们主要是用C语言解决猴子吃桃问题，一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 生活中或学术上有很多类似的问题，这个问题看似简单，却可能使很多重大问题的重要组成部分或者是核心。解决此问题的目的是以便在生活中解决根本性问题，是生活变得更加便利。 三、设计完成后提交的文件和图表 1．计算说明书部分 如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*2e(i-1)-2 (i=2)。 如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。 2．图纸部分： 程序流程图 图1-1 图1-2 四、进程安排 （1）设计题目、设计要求以及系统功能需求分析； （2）总体设计：包括系统总体设计框架和系统功能模块图； （3）详细设计：包括主要功能模块的算法设计思路以及对应的工作流程图； （4）主要源程序代码：包括存储设计说明，以及完整源程序清单(放在附录中)； （5）调试分析过程描述：包括测试数据、测试输出结果，以及对程序调试过程中存在问题的思考（列出主要问题的出错现象、出错原因、解决方法及效果等）； （6）总结：包括课程设计过程中的学习体会与收获、对C语言和本次课程设计的认识等内容。 （7）附录（完整源程序清单） 主要参考资料 [1] 王红梅，胡明，王涛. 数据结构(C++版) . 北京：清华大学出版社，2007 [2] 王红梅，胡明，王涛. 数据结构(C++版) 学习辅导与实验指导. 北京：清华大学出版, 2007 [3] 谭浩强 . C++程序设计. 北京：清华大学出版社, 2004 [4] 郑阿奇，丁有和. Visual C++教程.北京：机械工业出版社，2006 [5] 李文军，李师贤，周晓聪. C++作为计算机专业程序设计入门语言的实践与探讨. 计算机科学，1999，26（4）：80～83 成 绩 评 定 表 作品成绩 报告成绩 口试（答辩）成绩 总评成绩 摘要 当下C++语言是一门重要的课程学习，学会运用并结合其他的知识一起解题是一件值得我们重视的，数据结构是一门结合C++知识的重要课程，因此我们要学会将平时课本的知识运用到我们现实生活当中，这样才能让我们所学的知识更加深刻。猴子吃桃的问题就是一个例子，我们可以运用简单的三种解法进行解题，即数组求值解法，链表求值解法和递归求值解法，通过分析三种解法，根据各种解法的功能从而