C++课程设计报告---猴子吃桃问题.doc

数据结构课程设计 猴子吃桃问题课程设计报告书设计名称： 数据结构课程设计 题 目： 猴子吃桃问题 学生姓名： xxx 专 业： 计算机科学与技术（数字媒体） 班 别： x 学 号： x 指导老师： x 日 期： 2010 年 7 月 4 日 摘要当下c+语言是一门重要的课程学习，学会运用并结合结合其他的知识一起解题是一件值得我们重视的，数据结构是一门结合c+知识的重要课程，因此我们要学会用平时课本的知识运用到我们的现实生活当中，这样才能让我们所学的知识更加深刻。猴子吃桃的问题就是一个例子，我们可以运用简单的三种解法进行解题，即数组求值解法，链表求值解法和递归求值解法，通过分析三种解法，根据各种解法的功能，从而我们得到最合适的求法。关键词：猴子吃桃，数组法，链表法，递归法，分析abstract：thenthec+languageisanimportantcoursestudy,learntouseandcombiningtogetherwithotherknowledgesolutionisworthourattention,datastructureisacombinationofc+classes,theimportantknowledgesothatwemustlearntouseordinarytextbookstoapplyourreallife,sothatwecanmakeusmoreprofoundknowledge.themonkeyseatthepeachisasimpleexample,wecanusethethreesolutionstosolvingmethod,i.e.arraysareevaluatedforvaluechain,andrecursionevaluatedmethod,byanalyzingthethreekindsofsolutions,accordingtovarioussolutions,whichwehavethefunctionofthemostsuitablesolution.keywords:themonkeyseatthepeach,thearraymethod,thelistofrecursion,method,themethodofanalysis目录1.问题描述 22.基本要求23工具/准备工作 24.分析与实现24.1题目分析24.2.1数组求解法分析24.2.2链表求解法分析24.2.3递归法分析44.3功能代码45.测试与结论86.课程设计总结96.1算法特点及在例题功能扩展96. 2感悟107.参考文献1.问题描述有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。2.基本要求(1)采用数组数据结构实现上述求解(2)采用链式数据结构实现上述求解(3)采用递归实现上述求解3.工具/准备工作1）程序调试采用到vc6.0的win32 console application，所以要安装英文版vc6.0。2）根据问题要求，深入复习有关数组，链表，递归函数相关内容，了解数组，链表的创建，特点，改如何使用，再者递归法是相对比较难理解，这就需要了解该如何使用递归函数了。4.分析与实现4.1题目分析根据题目要求，设猴子共摘的桃子个数为n即是第一天桃子的个数n1, 第第二天时桃子个数n2，第三天时桃子个数n3，第四天时桃子个数n4，第五天时桃子个数n5，第六天时桃子个数n6，第七天时桃子个数n7，第八天时桃子个数n8，第九天时桃子个数n9，第十天时桃子个数n10。由题中“每天都吃当前桃子的一半且再多吃一个”很容易知道n10=1，（n9/2+1）=n10，n8-（n8/2+1）= n9 依次推出公式：ni-1-（ni-1/2+1）= ni (0。即ni-1= 2*（ni+1）(0。4.2.1数组求解法分析声明一个长度为10的整形数组a10,分别存放各天猴子吃前的桃子数。下图所示图1n1n2n3n4n5n6n7n8n9n10a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 先将a9赋值为1，用一个循环语句for(int i=8;i=0;i-)ai=2*(ai+1+1);为其余各数组元素赋值，则数组元素a0的值便是该问题的解。4.2.2链表求解法分析建立单链表，声明一个类用来对链表的结点指针进行定义，在初始化函数中利用头插法创建具有10个元素的链表，并依次安公式ni-1= 2*（ni+1）(0。赋值得到一个如图所示的链表。图4-2 headn6 nextn3 nextn4 nextn5 nextn1 nulln2 nextn7 nextn8 nextn9 nextn10 next next那么n1便是要求问题的解。4.2.3递归法分析利用一个递归函数来进行求值：依据返回值来记录每一天剩余桃子情况。int process(int n) if(n=10)return 1;else return 2*(process(n+1)+1);4.3功能代码#include class listpublic:int data; class list *next;void push();typedef class list node;/建立单链表(将class重定义为node)typedef node *link;/定义结点指针link p=null;void list:push()link s;int j=1;p-data=j;for(int i=9;i0;i-)s=new node;s-data=(j+1)*2;j=s-data;s-next=null;p-next=s;p=p-next;int process(int n)/递归法if(n=10)return 1;else return 2*(process(n+1)+1);void main()cout*数组数据结构实现:=0;i-) ai=(ai+1+1)*2; for(i=9;i=0;i-)cout第j天剩下的桃子为:aiendl;j-;cout所以猴子共摘了a0个桃子endl;coutendl;cout*链式数据结构实现:next; cout第10天剩下的桃子为:1endl; i=9; while(p) cout第i天剩下的桃子为:datanext;i-; coutendl;cout*递归实现:0;i-)cout第i天剩下的桃子为:process(i)endl;cout所以猴子共摘的桃子为:process(1)endl;5.测试与结论本程序在debug下测试成功，如下图所示：本测试分别输出了三种方法所求得的结果为：1534个，另外还用数组法，链表法和递归法分别求出了，猴子在吃桃子的10天内，各天含有桃子的数量：下面进行验证结果：原始桃子为：1534 第一天桃子为：3070-（3070/2+1）=1534第二天为：1534-（1534/2+1）=766 第三天为：766-（766/2+1）=382第四天为：382-（382/2+1）=190 第五天为：190-（190/2+1）=94第六天为：94-（94/2+1）=46 第七天为：46-（46/2+1）=22第八天为：22-（22/2+1）=10 第九天为：10-（10/2+1）=4第十天为：4-（4/2+1）=16.课程设计总结6.1各算法特点及在例题功能扩展数组的使用要先确定其长度，有时候会造成空间浪费，但是存取方便；用链式存储方式是一种动态的存储，长度是不用规定的，需要用指针来找到元素所在存储单元；而递归算法，存储空间要得少，但要知道准确计算函数，相对比较难。在本例题中，我们可以通过对各种方法，利用for循环进行输出，就得到每一天桃子的剩余量。6.2感悟1.这一次的实验可以说是对前面一些知识的回顾和温习，由于有一段时间都未看过，发现自己对于链表结构和递归法有些淡忘，所以花了不少时间去认识，解题。解题思路要经过在草纸上画出，有时候急忙着反