C++课程设计报告---猴子吃桃问题
数据结构课程设计
设计名称: 数据结构课程设计 题 目: 猴子吃桃问题
学生姓名: xxx 专 业: 计算机科学与技术,数字媒体, 班 别: x
学 号: x
指导老师: x
日 期: 2010 年 7 月 4 日
数据结构课程设计 猴子吃桃问题
摘要
当下C++语言是一门重要的课程学习，学会运用并结合结合其他
的知识一起解题是一件值得我们重视的，数据结构是一门结合C++知
识的重要课程，因此我们要学会用平时课本的知识运用到我们的现实
生活当中，这样才能让我们所学的知识更加深刻。猴子吃桃的问题就
是一个例子，我们可以运用简单的三种解法进行解题，即数组求值解
法，链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
求值解法和递归求值解法，通过分析三种解法，根据各种解
法的功能，从而我们得到最合适的求法。
关键词:猴子吃桃，数组法，链表法，递归法，分析
Abstract:
Then the c + + language is an important course study, learn to use and combining together with other knowledge solution is worth our attention, data structure is a combination of c + + classes, the important knowledge so that we must learn to use ordinary textbooks to apply our real life, so that we can make us more profound knowledge. The monkeys eat the peach is
a simple example, we can use the three solutions to solving method, i.e. arrays are evaluated for value chain, and recursion evaluated method, by analyzing the three kinds of solutions, according to various solutions, which we have the function of the most suitable solution.
Keywords: the monkeys eat the peach, the array method, the list of recursion, method, the method of analysis
第 2 页 共 10 页
数据结构课程设计 猴子吃桃问题
目录
1.问题描述„„„„„„„„„„„„„„„„„„„„„„ 2 2.基本要求„„„„„„„„„„„„„„„„„„„„„„2 3工具/准备工作 „„„„„„„„„„„„„„„„„„„2 4.分析与实现„„„„„„„„„„„„„„„„„„„„„2 4.1题目分析„„„„„„„„„„„„„„„„„„„„„2 4.2.1数组求解法分析„„„„„„„„„„„„„„„„„„2 4.2.2链表求解法分析„„„„„„„„„„„„„„„„„„2 4.2.3递归法分析„„„„„„„„„„„„„„„„„„4 4.3功能代码„„„„„„„„„„„„„„„„„„„„„4 5.测试与结论„„„„„„„„„„„„„„„„„„„„„8 6.课程设计总结„„„„„„„„„„„„„„„„„„„„9 6.1算法特点及在例题功能扩展„„„„„„„„„„„„9 6. 2感悟„„„„„„„„„„„„„„„„„„„„„„„10 7.参考文献
第 3 页 共 10 页
数据结构课程设计 猴子吃桃问题
1.问题描述
有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
2.基本要求
(1)采用数组数据结构实现上述求解
(2)采用链式数据结构实现上述求解
(3)采用递归实现上述求解
3.工具/准备工作
1)程序调试采用到VC6.0的Win32 Console Application，所以要安装英文版VC6.0。
2)根据问题要求，深入复习有关数组，链表，递归函数相关内容，了解数组，链表的创建，特点，改如何使用，再者递归法是相对比较难理解，这就需要了解该如何使用递归函数了。
4.分析与实现
4.1题目分析
根据题目要求，设猴子共摘的桃子个数为n即是第一天桃子的个数n, 第第 1二天时桃子个数n，第三天时桃子个数n，第四天时桃子个数n，第五天时桃234子个数n，第六天时桃子个数n，第七天时桃子个数n，第八天时桃子个数n，5678第九天时桃子个数n，第十天时桃子个数n。 910
由题中“每天都吃当前桃子的一半且再多吃一个”很容易知道n=1，(n/2+1)109=n，n-(n/2+1)= n…… 依次推出公式:n-(n/2+1)= n(0。,i,10)10889i-1i-1i 即n= 2*(n+1)(0。 ,i,10)i-1i
4.2.1数组求解法分析
声明一个长度为10的整形数组a[10],分别存放各天猴子吃前的桃子数。下图所示
图1
第 4 页 共 10 页
数据结构课程设计 猴子吃桃问题
n n n n n n n n n n 12345678910
a[0] a[1]a[2]a[3] a[4] a[5] a[6] a[7] a[8] a[9] 先将a[9]赋值为1，用一个循环语句
for(int i=8;i>=0;i--)
a[i]=2*(a[i+1]+1);为其余各数组元素赋值，则数组元素a[0]的值便是该问题的解。
4.2.2链表求解法分析
建立单链表，声明一个类用来对链表的结点指针进行定义，在初始化函数中利用头插法创建具有10个元素的链表，并依次安公式n= 2*(n+1)(0。,i,10)i-1i赋值得到一个如图所示的链表。
图4-2
head
next N next N next N next 1098
N next N next N next N next 7654
N next N next N NULL 321
那么N便是要求问题的解。 1
4.2.3递归法分析
利用一个递归函数来进行求值:依据返回值来
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
每一天剩余桃子情况。 int process(int n)
{
if(n==10)
return 1;
else
第 5 页 共 10 页
数据结构课程设计 猴子吃桃问题
return 2*(process(n+1)+1);
}
4.3功能代码
#include
class 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;i>0;i--)
{
s=new node;
s->data=(j+1)*2;
j=s->data;
s->next=NULL;
p->next=s;
p=p->next;
}
}
第 6 页 共 10 页
数据结构课程设计 猴子吃桃问题 int process(int n)//递归法
{
if(n==10)
return 1;
else
return 2*(process(n+1)+1);
}
void main()
{
cout<<"*****数组数据结构实现:"<=0;i--)
{
a[i]=(a[i+1]+1)*2;
}
for(i=9;i>=0;i--)
{
cout<<"第"<next;
cout<<"第10天剩下的桃子为:1"<data<next;
i--;
}
cout<0;i--)
cout<<"第"<
规定
关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定
的，需要用指针来找到元素所在存储单元;而递归算法，存储空间要得少，但要知道准确计算函数，相对比较难。在本例题中，我们可以通过对各种方法，利用for循环进行输出，就得到每一天桃子的剩余量。
6.2感悟
1.这一次的实验可以说是对前面一些知识的回顾和温习，由于有一段时间都未看过，发现自己对于链表结构和递归法有些淡忘，所以花了不少时间去认识，解题。解题思路要经过在草纸上画出，有时候急忙着反而使后面的不知道怎么写。
2.发现自己在写报告组织语言方面挺欠缺，开始不能很清楚的表达分析解题，所以经过多次改进。许多解法功能自己不仅要懂得简单运用，更需要懂得如何表达出来。
7.参考文献
a(龚沛曾 杨志强主编 C/C++程序设计教程(visualC++环境) 高等教育出版社
b.王红梅 数据结构(C++版)北京 清华大学出版社 2009 内部
资料
新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单
仅供参考
第 9 页 共 10 页
数据结构课程设计 猴子吃桃问题
第 10 页 共 10 页
浙公网安备 33021202002483