数据结构大作业 猴子吃桃问题

1、课课 程程 设设 计计 说说 明明 书书课程名称： 数据结构 设计题目： 猴子吃桃问题 学 院： 计算机科学与信息工程学院 学生姓名： 学生学号： 专业班级： 软件工程 指导教师： 宋强 2014 年 06 月 15 日课课 程程 设设 计计 任任 务务 书书设计题目猴子吃桃问题学生姓名班级软件工程设计要求：设计要求：基本要求(1)采用数组数据结构实现上述求解(2)采用链式数据结构实现上述求解(3)采用递归实现上述求解(4)采用队列实现上述求解学生应完成的工作：学生应完成的工作：参考文献阅读：参考文献参考文献1 严蔚敏等编著. 数据结构（C 语言版）. 北京：清华大学出版社，20032 李春葆

2、，金晶编著.数据结构教程（C 语言版）.北京：清华大学出版社，20063 朱立华等编著.面向对象程序设计及 C+.北京：人民邮电出版社，2008工作计划：工作计划：任务下达日期： 2014 年 06 月 01 日 任务完成日期： 2014 年 06 月 15 日学生（签名）： 猴子吃桃问题猴子吃桃问题摘摘 要：要： 数据结构是一门结合 C+知识的重要课程，因此我们要学会用平时课本的知识运用到我们的现实生活当中，这样才能让我们所学的知识更加深刻。分析了猴子吃桃子问题的实质，得到了其数学模型 ni-1= 2*（ni+1）(0，接下来就是其需求分析和概要设计，大致的制)10 i定出其实现方案以及其系

3、统结构，然后就是利用掌握的语言 C/C+编程实现这一生活问题，该软件用了几种不同的方法解答出了所需要的答案。猴子吃桃的问题就是一个例子，我们可以运用简单的四种解法进行解题，即数组求值解法，链表求值解法，递归求值解法和队列求值法，通过分析四种解法，根据各种解法的功能，从而我们得到最合适的求法。关键词：关键词：猴子吃桃子；数组法；链表法；递归法；队列法；分析目目 录录 1 1 设计背景设计背景.1 11.1 问题描述.11.2 基本要求.11.3 开发及运行平台.12.2.设计方案设计方案 .2 22.1 题目分析 .2 2.2 需求分析规格 .22.2.1数据求解法分析.32.2.2链表求解法分

4、析.32.2.3递归法分析.4 2.2.4 队列法分析.4 2.3 数据流程图 .42.4 系统结构图.53 3 方案实施方案实施.5 5 3.1 数据类型定义.5 3.2 主要模块设计. 53.2.1 模块 1数组求解模块.53.2.2 模块 2链表求解模块.63.2.3 模块 3递归求解模块.73.2.4 模块 4队列求解模块.8 3.3 源程序.84 4 结果与结论结果与结论.1 13 3 4.1 调试分析.13 4.2 程序运行结果.13 4.3 结论.145.5.参考文献参考文献 .151501. 设计背景1.11.1 问题描述问题描述 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的

5、一半且再多吃一个，到了第10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。1.21.2 基本要求基本要求 (1)采用数组数据结构实现上述求解 (2)采用链式数据结构实现上述求解 (3)采用递归实现上述求解 (4)采用队列实现上述求解1.31.3 开发及运行平台开发及运行平台 在本课程设计中，系统开发平台为 Windows2000,程序设计语言为 Visual C+ 6.0，程序的运行环境为 Visual C+6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以 Vi

6、sual C+6.0 为编程环境。 Microsoft Visual C+6.0 是 Microsof 公司的 Microsoft Visual Studio 6.0 开发工具箱中的一个 C+程序开发包。Visual C+包中除包括 C+编译器外，还包括所有的库、例子和为创建 Windows 应用程序所需要的文档。自 1993 年 Microsoft 公司推出Visual C+1.0 后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。Visual C+从最早期的 1.0 版本，发展到最新的 7.0 版本，Visual C+已经有了很大的变化，在界面、功能、库

7、支持方面都有许多的增强。最新的 7.0 版本在编译器、MFC 类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。 Visual C+6.0 是 Microsoft 公司推出的目前使用最广泛的基于 Windows 平台的可视化编程环境。Visual C+ 6.0 是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的 Internet 支持，因而在各种 C+语言开发工具中脱颖而出，成为目前最为流行的 C+语言集成开发环境。 虽然微软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限1性，只适用于 Windows

8、2000,Windows XP 和 Windows NT4.0。所以实际中，更多的是以Visual C+6.0 为平台。 Visual C+ 6.0 是 Microsoft 公司推出的目前使用最广泛的基于 Windows 平台的可视化编程环境。Visual C+ 6.0 是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的 Internet 支持，因而在各种 C+语言开发工具中脱颖而出，成为目前最为流行的 C+语言集成开发环境。 Visual C+ 6.0 秉承 Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资

9、源编辑器、工程创建工具、Debugger 调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。 2.设计方案2.12.1 题目分析题目分析根据题目要求，设猴子共摘的桃子个数为 n 即是第一天桃子的个数 n1, 第第二天时桃子个数 n2，第三天时桃子个数 n3，第四天时桃子个数 n4，第五天时桃子个数n5，第六天时桃子个数 n6，第七天时桃子个数 n7，第八天时桃子个数 n8，第九天时桃子个数 n9，第十天时桃子个数 n10。由题中“每天都吃当前桃子的一半且再多吃一个”很容易知道 n10=1，n9-（n9/2+1）=n10，n8-（n8/

10、2+1）= n9 依 次推出公式：ni-1-（ni-1/2+1）= ni (0。即 ni-1= 2*（ni+1）(0。)10 i)10 i2.22.2 需求分析规格需求分析规格 由上述描述及分析可知，该系统所要做的工作就是计算出原来这群猴子共摘了多少个桃子。通过分析不同的解法，找到每种解法的优劣，得到最合适的求解方法。由问题描述可知，该系统运行时，不需要手动输入任何数据，因此就没有输入的测试数据，只有输出的测试数据，且输出数据的形式是输出每天剩下的桃子数，最后输出这群猴子总共摘了多少桃子。.1 数组求解法分析数组求解法分析2分析： 声明一个长度为 10 的整形数组 a10,分别

11、存放各天猴子吃前的桃子数。下图 1 所示：a0 a1 a2 a3 a4 a5 a6 a7 a8 a 图 2.2.1 数组元素分布图 先将 a9赋值为 1，用一个循环语句 for(int i=8;i=0;i-) ai=2*(ai+1+1);为其余各数组元素赋值，则数组元素 a0的值便是该问题解。 数据类型定义： int a10; a9=1;.2 链表求解法分析链表求解法分析分析： 建立单链表，声明一个类用来对链表的结点指针进行定义，在初始化函数中利用头插法创建具有 10 个元素的链表，并依次安公式 ni-1= 2*（ni+1）(0。赋值得)10 i到一个如图 2 所示的链表。 图

12、 2.2.2 链表结点逻辑结构图数据类型定义： class listpublic:int data;n1n2n3n4n5n6n7n8n9n103 class list *next;void push();typedef class list node; /建立单链表(将 class 重定义为 node)typedef node *link; /定义结点指针.3 递归法分析递归法分析分析： 利用一个递归函数来进行求值：依据返回值来记录每一天剩余桃子情况。 int process(int n) if(n=10) return 1; else return 2*(process(n+

13、1)+1); .4 队列法分析队列法分析分析： 定义一个队列，和一个临时变量，临时变量存放第十天到第一天的剩下的桃子数目，每计算出一天的剩余的桃子数，就将其入队，十天的剩余桃子数全部入队以后就出对，即得到每一天的剩余桃子数，最后得到的一个数据就是所要求的桃子的总数。数据类型定义： typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue;2.32.3 数据流程图数据流程图4猴子吃桃子问题求解系统已知：第十天剩1个桃，每天吃当前桃子的一半再加1个解的结果，以及每天剩下的桃子个数 图 2.

14、3.1 数据流程图2.42.4 系统结构图系统结构图 猴子吃桃子求解系统采用数组存储结果求解采用递归过程求解采用队列存储结果求解采用链表存储结果求解 图 2.4.1 系统结构图3. 方案实施3.13.1 数据类型定义数据类型定义 in a10; class list public: int data; class list *next; void push();5;typedef class list node; /建立单链表(将 class 重定义为 node)typedef node *link; /定义结点指针typedef struct SqQueueint dataQueueSize

15、;int fornt,rear; / 队首、队尾指针SqQueue;3.23.2 主要模块设计主要模块设计.1 模块模块 1 1数组求解模块数组求解模块 模块算法：/数组求解void Array_Solve()int a10; / 存放int i; a9=1;cout数组数据结构实现:endl;cout第 10 天剩下的桃子为:a9=0;i-) ai=(ai+1+1)*2;cout第 i+1天剩下的桃子为:aiendl; cout所以猴子共摘了a0个桃子endl;cout=0;i-)ai=(ai+1+1)*2;coutnext;cout链式数据结构实现:endl;

16、 cout第 10 天剩下的桃子为:1endl; int i=9; while(p)7 cout第 i天剩下的桃子为:dataendl;if(i=1)cout所以猴子共摘了data个桃子next;i-; coutendl;.3 模块模块 3 3递归求解模块递归求解模块 模块算法int process(int n) /递归if(n=10)return 1;else return 2*(process(n+1)+1);/递归求解void Fac_Solve()cout递归方法实现:0;i-)cout第 i天剩下的桃子为:process(i)endl;cout所以猴子共

17、摘了process(1)个桃子endlendl;.4 模块模块 4 4队列求解模块队列求解模块 模块算法8/队列求解void Queue_Solve()SqQueue SQ;SQ.fornt=SQ.rear=0;int temp; / 临时变量，存放每一天剩的桃子数temp=1; / 初始放第十天的for(int i=0;i10;i+)SQ.dataSQ.rear+=temp;temp=2*(temp+1);cout队列数据结构实现:endl;while(SQ.fornt!=SQ.rear)cout第11-SQ.fornt天剩下的桃子为:SQ.dataSQ.for

18、nt+endl;cout所以猴子共摘了SQ.dataSQ.fornt-1个桃子endlendl;3.33.3 源程序清单源程序清单#include #include #include #define QueueSize 10using namespace std;class listpublic:int data;9 class list *next;void push();typedef class list node; /建立单链表(将 class 重定义为 node)typedef node *link; /定义结点指针link p=NULL;void list:push()link s

19、;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;typedef struct SqQueueint dataQueueSize;int fornt,rear; / 队首、队尾指针SqQueue;/数组求解void Array_Solve()int a10; / 存放int i; a9=1;10cout数组数据结构实现:endl;cout第 10 天剩下的桃子为:a9=0;i-) ai=(ai+1+1)*2;cout第 i+1天剩下的桃子为:a

20、iendl; cout所以猴子共摘了a0个桃子endl;coutnext;cout链式数据结构实现:endl; cout第 10 天剩下的桃子为:1endl; int i=9; while(p) cout第 i天剩下的桃子为:dataendl;if(i=1)cout所以猴子共摘了data个桃子next; i-; coutendl;11int process(int n) /递归if(n=10)return 1;else return 2*(process(n+1)+1);/递归求解void Fac_Solve() cout递归方法实现:0;i-)cout第 i天剩下的桃子为:process(i

21、)endl;cout所以猴子共摘了process(1)个桃子endlendl;/队列求解void Queue_Solve()SqQueue SQ;SQ.fornt=SQ.rear=0;int temp; / 临时变量，存放每一天剩的桃子数temp=1; / 初始放第十天的for(int i=0;i10;i+)SQ.dataSQ.rear+=temp;temp=2*(temp+1);cout队列数据结构实现:endl;while(SQ.fornt!=SQ.rear)cout第11-SQ.fornt天剩下的桃子为:SQ.dataSQ.fornt+endl;cout所以猴子共摘了SQ.dataSQ.

22、fornt-1个桃子endlendl;void menu()12system(cls);system(color 0A);coutendlendl;cout| *主菜单* |endl;cout| |endl;cout| 1、数组求解 |endl;cout| 2、链表求解 |endl;cout| 3、递归求解 |endl;cout| 4、队列求解 |endl;cout| 5、退出 |endl;cout| |endl;void main()int n;char ch;while(1)menu();coutn;switch(n)case 1: Array_Solve(); cout按任意键继续.;c

23、h=getchar();ch=getchar();break;case 2: Link_Solve(); cout按任意键继续.;ch=getchar();ch=getchar();break;case 3: Fac_Solve(); cout按任意键继续.;13ch=getchar();ch=getchar();break;case 4: Queue_Solve(); cout按任意键继续.; ch=getchar();ch=getchar();break;case 5: exit(0);default: cout选择错误! =0;i-)，因此其时间复杂度为 O(9).数组求解模块的空间复杂

24、度：因为不需要输入任何数据，所以该算法为原地工作。4.1.2 链表求解模块的时间复杂度：因为算法中用到一个循环来输出，因此其时间复杂度为 O(9).链表求解模块的空间复杂度：原地工作。4.1.3 队列求解模块的时间复杂度：因为 for(i=0;i10;i+)，所以时间复杂度为 O(9)。队列求解模块的空间复杂度：因为用了一个存储临时变量的空间，所以其空间复杂度为 O(1)。4.24.2 程序运行结果程序运行结果程序运行结果：第 10 天剩下的桃子为:1第 9 天剩下的桃子为:4第 8 天剩下的桃子为:10第 7 天剩下的桃子为:22第 6 天剩下的桃子为:46第 5 天剩下的桃子为:94第 4

25、 天剩下的桃子为:190第 3 天剩下的桃子为:382第 2 天剩下的桃子为:766第 1 天剩下的桃子为:1534所以猴子共摘了 1534 个桃子 本测试分别输出了三种方法所求得的结果为：1534 个，另外还用数组法，链表法，队列法和递归法分别求出了，猴子在吃桃子的 10 天内，各天含有桃子的数量：15 下面进行验证结果：原始桃子为：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）=