《本科毕业设计猴子吃桃问题》由会员分享，可在线阅读，更多相关《本科毕业设计猴子吃桃问题（19页珍藏版）》请在金锄头文库上搜索。
1、3毕 业 设 计课程设计名称： 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间：2 计算机应用技术专业课程设计任务书学生姓名专业班级）学号题 目猴子吃桃问题课题性质A工程设计课题来源D自拟课题指导教师同组姓名无主要内容猴子吃桃子问题（限1 人完成） 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。任务要求要求：1) 采用数组数据结构实现上述求解2) 采用链数据结构实现上述求解3) 采用递归实现上述求解4) 如果采用4种方法者,适当加分参考文献1C程序设计（第三版）
2、谭浩强 著 清华大学出版社，20052数据结构C语言版 严蔚敏，吴伟民 著 清华大学出版社，20083Visual C+教程 郑阿奇，丁有和 著 著机械工业出版社，20064 数据结构(C+版) 王红梅，胡明，王涛 著 清华大学出版, 20075 C语言编程基础. 王森 著 电子工业出版社.2001年12月审查意见指导教师签字：教研室主任签字： 2010年 12月 26 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 国际学院 学院课程设计成绩评价表课程名称：总课程设计设计题目：猴子吃桃问题专业：计算机应用 班级： 姓名： 学号：序号评审项目分 数满分标
3、准说明1内 容思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。2创 新内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解3完整性、实用性整体构思合理，理论依据充分，设计完整，实用性强4数据准确、可靠数据准确，公式推导正确5规 范 性设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定6纪 律 性能很好的遵守各项纪律，设计过程认真；7答 辩准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。总 分综合意见 指导教师： 刘於勋 2010年 11月28 日 1
4、 引 言在日常生活中经常遇到一些与数据计算有关的问题，许多与猴子吃桃问题类似的问题要求用计算机程序语言来解决，用这个程序算法可以解决一些类似问题，以便利于生活实际。1.1课程设计背景猴子吃桃问题涉及一个比较有趣的数组，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为ai=3*pow（2，(i-1)）-2 (i=2)1.2 课程设计目的在这个程序中我们主要是用C语言解决猴子吃桃问题，一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一
5、个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。生活中或学术上有很多类似的问题，这个问题看似简单，却可能使很多重大问题的重要组成部分或者是核心。解决此问题的目的是以便在生活中解决根本性问题，是生活变得更加便利。1.3 课程设计内容这个程序的内容是以C语言为程序语言载体分别用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。1 需求分析这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的项来实现。用链结构实现的算法，则是建立链表，将每天的桃子数目存入链表，然后输出第一天的桃子数
6、。用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解。3 概要设计3.1设计思路C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。3.2设计方案如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。所以可以求得
7、此数组的通项公式为ai=3*2e(i-1)-2 (i=2)。如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递归算法。4 详细设计4.1 数组结构把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数ai的递推公式为ai=(ai-1+1)*2。ai实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为ai=3*pow（2，(i-1)）-2 (i=2)。数组结构算法的流程图如图3-1：开
8、 始建立一个以天数为下标以剩下桃子数为元素的数组规定此数组的通向公式求第一天的桃子数结 束图3-1int day,tao11; /定义数组和下标tao0=0; /tao0赋值为0tao1=1; /倒数第一天的桃子数为1for(day=2;daynext=NULL;这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部分构成。在插入数据时，将插入的位置的前一项的原有后去指针赋给此结点的后去指针，然后把插入结点的data地址赋给前一结点的后驱指针，插入就完成了。插入结点的程序代码如下：Status ListInsert(LinkList L,int i,ElemType e)/在第
9、i个位置之前插入元素e int j=0;/计数器初值为0LinkList s,p=L;/p指向头结点while(p&jnext;4.3递归设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。递归算法的流程图如图3-3开 始定义参数i和ni0NY调用本身，且-i输出sum开 始主要程序代码如下：int sum_fan(int n,int i) /子函数sum_fun，参数n和i接受主函数的参数 x和day if (i0) n = sum_fan(n+1)*2,-i); /每一次都用(n+1)*2)的值去调用子函数本身 return n; /返回结果
10、5调试分析5.1运行环境在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程
11、序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更
12、多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。5.2出现错误及调试猴子吃桃虽然只是C语言实现猴子吃桃子问题，这对我来说是个很具有挑战性的任务，因为我的C语言学的只能说是马马虎虎，所以在编译源代码时出了许多问题，但是在老师和同学的帮助下我还是顺利的完成时源代码的编写，下面我把一些典型的错误说明一下：第一个是比较低级错误，编写递归代码时头文件include在编译时错
