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

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

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

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

4、 需求分析规格 .2 2.2.1数据求解法分析.3 2.2.2链表求解法分析.3 2.2.3递归法分析.4 2.2.4 队列法分析.4 2.3 数据流程图 .4 2.4 系统结构图.5 3 3 方案实施方案实施.5 5 3.1 数据类型定义.5 3.2 主要模块设计. 5 3.2.1 模块 1数组求解模块.5 3.2.2 模块 2链表求解模块.6 3.2.3 模块 3递归求解模块.7 3.2.4 模块 4队列求解模块.8 3.3 源程序.8 4 4 结果与结论结果与结论.1 13 3 4.1 调试分析.13 4.2 程序运行结果.13 4.3 结论.14 5.5.参考文献参考文献 .1515

5、0 1. 设计背景 1.11.1 问题描述问题描述 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 1.21.2 基本要求基本要求 (1)采用数组数据结构实现上述求解 (2)采用链式数据结构实现上述求解 (3)采用递归实现上述求解 (4)采用队列实现上述求解 1.31.3 开发及运行平台开发及运行平台 在本课程设计中，系统开发平台为 Windows2000,程序设计语言为 Visual C+ 6.0，程序的运行环境为 Visual C+6.0。Visual C+一般分为三个版本:学习版、专业 版

6、和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的 任意一种，在本课程设计中，以 Visual 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+已成为专业程序员进行软件 开发的首选工具。Visua

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

8、软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限 1 性，只适用于 Windows 2000,Windows XP 和 Windows NT4.0。所以实际中，更多的是以 Visual C+6.0 为平台。 Visual C+ 6.0 是 Microsoft 公司推出的目前使用最广泛的基于 Windows 平台的 可视化编程环境。Visual C+ 6.0 是在以往版本不断更新的基础上形成的，由于其功 能强大，灵活性好，完全课扩展以及具有强大的 Internet 支持，因而在各种 C+语言 开发工具中脱颖而出，成为目前最为流行的 C+语言集成开发环境

9、。 Visual C+ 6.0 秉承 Visual C+以前版本的优异特性，为用户提供了一套良好的 可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger 调试 器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、 编译、链接、运行、调试应用程序。 2.设计方案 2.12.1 题目分析题目分析 根据题目要求，设猴子共摘的桃子个数为 n 即是第一天桃子的个数 n1, 第第二天 时桃子个数 n2，第三天时桃子个数 n3，第四天时桃子个数 n4，第五天时桃子个数 n5，第六天时桃子个数 n6，第七天时桃子个数 n7，第八天时桃子个数 n8，第九天时桃 子

10、个数 n9，第十天时桃子个数 n10。 由题中“每天都吃当前桃子的一半且再多吃一个”很容易知道 n10=1，n9- （n9/2+1）=n10，n8-（n8/2+1）= n9 依 次推出公式：ni-1-（ni-1/2+1）= ni (0 。即 ni-1= 2*（ni+1）(0。 )10 i)10 i 2.22.2 需求分析规格需求分析规格 由上述描述及分析可知，该系统所要做的工作就是计算出原来这群猴子共摘了多 少个桃子。通过分析不同的解法，找到每种解法的优劣，得到最合适的求解方法。由 问题描述可知，该系统运行时，不需要手动输入任何数据，因此就没有输入的测试数 据，只有输出的测试数据，且输出数据的

11、形式是输出每天剩下的桃子数，最后输出这 群猴子总共摘了多少桃子。 .1 数组求解法分析数组求解法分析 2 分析： 声明一个长度为 10 的整形数组 a10,分别存放各天猴子吃前的桃子数。下图 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 链表求解法分析链表求解法分析 分析： 建立单链表，声明一

12、个类用来对链表的结点指针进行定义，在初始化函数中利用 头插法创建具有 10 个元素的链表，并依次安公式 ni-1= 2*（ni+1）(0。赋值得)10 i 到一个如图 2 所示的链表。 图 2.2.2 链表结点逻辑结构图 数据类型定义： class list public: int data; n1n2n3n4n5n6n7n8n9n10 3 class list *next; void push(); ;typedef class list node; /建立单链表(将 class 重定义为 node) typedef node *link; /定义结点指针 .3 递归法分析递

13、归法分析 分析： 利用一个递归函数来进行求值：依据返回值来记录每一天剩余桃子情况。 int process(int n) if(n=10) return 1; else return 2*(process(n+1)+1); .4 队列法分析队列法分析 分析： 定义一个队列，和一个临时变量，临时变量存放第十天到第一天的剩下的桃子数目， 每计算出一天的剩余的桃子数，就将其入队，十天的剩余桃子数全部入队以后就出对， 即得到每一天的剩余桃子数，最后得到的一个数据就是所要求的桃子的总数。 数据类型定义： typedef struct SqQueue int dataQueueSize;

14、int fornt,rear; / 队首、队尾指针 SqQueue; 2.32.3 数据流程图数据流程图 4 猴子吃桃子问题 求解系统 已知：第十天剩 1个桃，每天吃 当前桃子的一半 再加1个 解的结果，以及 每天剩下的桃子 个数 图 2.3.1 数据流程图 2.42.4 系统结构图系统结构图 猴子吃桃子求解系统 采 用 数 组 存 储 结 果 求 解 采 用 递 归 过 程 求 解 采 用 队 列 存 储 结 果 求 解 采 用 链 表 存 储 结 果 求 解 图 2.4.1 系统结构图 3. 方案实施 3.13.1 数据类型定义数据类型定义 in a10; class list publi

15、c: int data; class list *next; void push(); 5 ; typedef class list node; /建立单链表(将 class 重定义为 node) typedef node *link; /定义结点指针 typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue; 3.23.2 主要模块设计主要模块设计 .1 模块模块 1 1数组求解模块数组求解模块 模块算法： /数组求解 void Array_Solve() int a

16、10; / 存放 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; cout第 10 天剩下的桃子为:1endl; int i=9; while(p) 7 cout第 i天剩下的桃子为:dataendl; if(i=1) cout所以猴子共摘了data个桃子next; i-; coutendl; 3

17、. 模块模块 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所以猴子共摘了process(1)个桃子endlendl; .4 模块模块 4 4队列求解模块队列求解模块 模块算法 8 /队列求解 void Queue_Solve() SqQue

18、ue 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.fornt-1个桃子endlendl; 3.33.3 源程序清单源程序清单 #include #include #

19、include #define QueueSize 10 using namespace std; class list public: 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; int j=1; p-data=j; for(int i=9;i0;i-) s=new node; s-data=(j+1)*2; j=s

20、-data; s-next=NULL; p-next=s; p=p-next; typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue; /数组求解 void Array_Solve() int a10; / 存放 int i; a9=1; 10 cout数组数据结构实现:endl; cout第 10 天剩下的桃子为:a9=0;i-) ai=(ai+1+1)*2; cout第 i+1天剩下的桃子为:aiendl; cout所以猴子共摘了a0个桃子endl; coutnext; cout链式数据结构实

21、现:endl; cout第 10 天剩下的桃子为:1endl; int i=9; while(p) cout第 i天剩下的桃子为:dataendl; if(i=1) cout所以猴子共摘了data个桃子next; i-; coutendl; 11 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所以猴子共摘了process(1)个桃子endlend

22、l; /队列求解 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.fornt-1个桃子endlendl; void

23、 menu() 12 system(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按任意键继续.; ch=

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

25、数组求解模块的空间复杂度：因为不需要输入任何数据，所以该算法为原 地工作。 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 天剩下

26、的桃子为:46 第 5 天剩下的桃子为:94 第 4 天剩下的桃子为: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 第八天为：