猴子吃桃问题

1、数据结构课程设计 猴子吃桃问题目 录一、问题描述.3二、基本要求.3三、 工具/准备工作.3四、分析与实现.41.1题目分析.41.2基本流程图.42.1数组求解法的分析.42.2链表求解法的分析.52.3递归求解法的分析.63.实现相应功能的代码.6五、测试与结论.81.运行结果显示.82.运行结果的测试.9六、课程设计总结.91.算法特点及其功能拓展.92.个人感悟.9一、问题描述有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。要求用多种方法实现求出原来这群猴子共摘了多少个桃子。1)采用数组数据结构实现上述求解2)采用链式数据结构实现上述求解3

2、)采用递归实现上述求解二、基本要求2.1分别用数组数据结构、链式数据结构和递归的方法实现上述问题的求解。2.2运行时分别显示用上述三种方法求解过程中每一天所剩下的桃子个数以及原来这群猴子共摘的桃子个数。2.3程序要有必要的文字说明，测试结果稳定。三、工具/准备工作3.1需要的工具：一台安装有Microsoft Visual C+ 6.0软件的PC机3.2理论准备：根据课程设计内容的相关要求，深入复习有关数组、链表和递归函数的内容，对相应的知识进行进一步理解，如数组的定义和for循环的使用，另外链表方面要注意复习如何建立单链表以及指针的运用，而递归则要着重于递归函数的理解，同时还要兼顾其他一些要

3、运用到的理论知识的查阅和复习。四、分析与实现4.1.1题目分析由题目可设猴子共摘的桃子个数为n即是第一天猴子摘的桃子的个数n1, 第二天时猴子摘的桃子个数n2，第三天时猴子摘的桃子个数n3，第四天时猴子摘的桃子个数n4，第五天时猴子摘的桃子个数n5，第六天时猴子摘的桃子个数n6，第七天时猴子摘的桃子个数n7，第八天时猴子摘的桃子个数n8，第九天时猴子摘的桃子个数n9，第十天时猴子摘的桃子个数n10。由问题重述内容中“每天都吃当前桃子的一半且再多吃一个”可得n10=1，n9-（n9/2+1）=n10，n8-（n8/2+1）= n9， 依次推出公式：ni-1 -（ni-1/2+1）= ni (0i

4、10)。即ni-1=2 *（ni+1）(0=0;i-)ai= (ai+1+1)*2;为其余各数组元素赋值，则当i=0时就可得到我们要求的解a0了。4.2.2链表求解法分析要用链表求解首先要建立单链表，然后声明一个类用来对链表的结点指针进行定义，并在初始化函数中利用头插法创建具有10个元素的链表，并依次通过ni-1= 2*（ni+1）(0i10)进行赋值就可得到一个链表如图2所示。headN3 nextN4 nextN5 nextN7 nextN8 nextN9 nextN10 next nextN6 nextN1 NULLN2 next图2 链表结点逻辑结构图通过链表可知N1便是要求问题的解。

5、相关数据类型定义如下：class listpublic:int data; class list *next;void push();typedef class list node; /建立单链表typedef node *link; /定义结点指针4.2.3递归法分析递归法是通过一个递归函数来进行求值，然后用返回值来记录每一天剩余桃子个数即可，相关代码如下：int process(int n) if(n=10)return 1;else return 2*(process(n+1)+1);4.3相应功能代码以下所示代码是三种求解方法放一起进行实现的过程，这样减少了代码量，也利于运行结果的显示

6、，具体代码如下：9#includeclass list public: 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 pr

7、ocess(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-)c

8、out第i天剩下的桃子个数为:process(i)endl;cout所以猴子共摘了process(1)个桃子endl;五、测试与结论5.1运行结果显示该运行显示了三种方法所求得的结果皆为：1534个，另外还显示了每一天剩下的桃子个数以及原来这群猴子共摘的桃子个数，达到了预期的效果和目标。5.2结果的验证由运行结构可知原始桃子个数为：1534 个，则以下为每天所剩余桃子个数的验证： 第一天：3070-（3070/2+1）=153 第二天：1534-（1534/2+1）=766 第三天：766-（766/2+1）=382 第四天：382-（382/2+1）=190 第五天：190-（190/2+1

9、）=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）=1六、课程设计总结6.1 各算法特点及其功能扩展：运用数组数据结构求解最大的优点是存取方便，但是由于在使用之前得确定数组长度，所以有时会使得空间利用率不高，浪费内存；而链式存储是一种动态的存储方式，其长度可以根据需要进行适当的变动的，因为它是利用指针来找元素所在的存储单元的；另外递归算法所需的存储空间要相对少，但在分析时相对来说会显得较复杂些。其实，我们可以综合各种方法的利弊，通过以下代码的功能，如利用for循环进行输出，就可以得到每一天桃子的剩余量，从而提高解决问题的效率。6.2个人感悟由于这段时间都在进行期末的复习工作，所以相对来说本次课程设计所要用到的知识还是不陌生的，而且在以前上机实验中也做过类似实验，所以做起来还是有一定头绪的。但是，毕竟之前学习时掌握的知识比较凌乱，真正运用到时还是会出现一些头脑短路现象，我觉得还是知识掌握得不够系统，其次在编写代码时有些语句不能牢记，还是要参考之前编写的代码，这使