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

《数据结构课程设计-猴子吃桃问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学与计算机学院课程设计说明书课程名称：课程代码：题冃：年级/专业/班：学生姓名：学号：开始时间：2014年5月14日宀兀成时间：2014年一5月一28日课程设计成绩:学习态度及平时成绩(20)技术水平与实际能力(20)完成情况(20)创新(5)说明书(计算书、图纸、分析报告)撰写质量(35)总分(100)指导教师签名：年—月—日1需求分析32概要设计…33详细设计•■…44调试分析……115用户使用说明126测试结果…127结论……14致谢…15参考文献15本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天

2、都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。在课程设计中，系统开发平台为Windows2000,程序设计设计语言采用VisualC++,数据库采用MSSQL2000，程序运行平台为Windows98/2000/XPo在整个程序中分别采用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。程序通过调试运行，初步实现了设计目标。关键词：程序设计；C++；数组；链；递归；猴子吃桃引言在日常生活中经常遇到一些与数据计算有关的问题，许多与猴子吃桃问题类似的问题要求

3、用计算机程序语言来解决，用这个程序算法可以解决一些类似问题，以便利于生活实际。1需求分析1.1任务与分析任务功能：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子要求：采用数组数据结构实现上述求解采用链数据结构实现上述求解采用递归实现上述求解如果采用4种方法者，适当加分分析：这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。用数组结构实现的算法，通过构造求桃子数的数组，然后输岀要求的项来实

4、现。用链结构实现的算法，则是建立链表，将每天的桃子数目存入链表，然后输出第一天的桃子数。用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解。1.2测试数据输入任意一篇文章，按要求输入功能序号与字符串。测试是否能按要求输岀正确结果。2概要设计C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向

5、，从而使程序完全结构化。如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i,剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2,a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*2e(i-1)-2(i>=2)o如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n二2F+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递

6、归算法。3详细设计3.1数组结构把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i,剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*pow(2,(i-1))・2(i>=2)o数组结构算法的流程图如图3-1：图3-1intday,tao[11];〃定义数组和下标tao[0]=0;//tao[0]赋值为0tao[1]=1;〃倒数第一天的桃子数为1for(day=2;day<=10;day++)tao[day]=3*pow

7、(2,day-1)-2;//给数组的赋值printf(H最初的桃子数为%dH,tao[10]);//输出最初的桃子数3.2链表结构用链结构实现这个算法，其核心是利用链表这种存储结构，将每天的桃子数存储在链表中，在链表中实现数的递推。首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给Lo然后把每天的桃子数从链表的第一个结点插入链表。最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e,最后只要输出e即得到第一天的桃子数。建立单链表的程序代码如下：voidlnitList(LinkList&L)〃构造

8、一个空链链表{L=(LinkList)malloc(sizeof(LNode));//产生头结点，并使L指向此头结点if(!L)exit(OVERFLOW);L->next=NULL;}这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部分构成。在插入数据时，将插入的位置