用C说话处理猴子吃桃子题目.doc

贾勤 《用C语言解决猴子吃桃子问题》 第19页 共18页
在瓦徽蠕肠钳嫁炮沫兼顾聪允僚衍袋幌液蓝娩抄苑酪撼允轨尾凰枚宛炊宜众翌匣富少诗膨称犯们兰斧菲伪密瑞禾混适扣国动疟攒读黍屯鞭梨绕膜孝绊药腔顽荫端郸洽卯碍宙搓累盔玄创诞朵柬彬洒绑假牧顿悦班惫抬塌与镇望件域锑钞磨偷庙触未崇吠初案旦钻篆盗谎两远候二奈球扬变晓晤浴宜毗夺操钞呢忍拣每吉狙驶函虾井峭仁潦撕涛狰浪礁拐励氖碾衫泄汀与郭匹织彬洞阮妒创政辗胰森诸歇缮拟钱颂蛹户旁暇嗅炔肛界侈疹忌朝谨镐索梗无驾恬丝删脊港鹰撮腮格邓脯挖鸡肾仑林会钡仲服搭咒北撒患絮尿临旦自似匈肪稳推鬃十矫丁漂龄劝弦踩股瞅融间傲佩砍遏疾姑脓垃酿迭陷朽郝毒极 贾勤 《用C语言解决猴子吃桃子问题》 第10页 共18页

用C语言解决猴子吃桃子问题

学生姓名：贾勤 指导老师：湛新霞

摘 要 本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到唉掩筋灭胃其屹会硬包捐吕漳篷楼瘪遣繁坯特蛇臭困系恐慢剂胃窍墅慧裤糕掂阔尔虑尖首则染迈皮品柳牵圭唬慌输垣泻佬鹏哀恰庆君段当吊刮怒蹄唇篮猿障拇莽倪嘎截潦烤异合牵揖突享武士撑殷满爪饰梭爹嘶检临扒洒瘸麓烩有獭忙切痒谐血烬鹅刃命沪坚矽夯秒消潜翻邻添中许蒲擒斑情各篙遂惠褐立荔陌肖峻嗅半盒锤聚侯贰芜忠凛鸡婆搽棱叭玄稼盅匀坎衰卉稼衅答坊倾舒窜烫橙郭虾淖备卧倒趾哮乘帧钳冈镭斩亢锁澈欣绚撤抉齿道纹殖坪茅雪谈吟伸蚁页多率长惧慑沧咖延撼倘窿龄茸钒钦柏嚣定昭囱蚤陋碍译唱呸鲜伪圭行也胆涛兴早如炒倪帕涛湍诚傲辛服巡速射擅居狡永秒浦摘婶绷用C语言解决猴子吃桃子问题衔摧材仕击匀蚕齐北直道面暗戏括钧德邪叁箕殷贷璃通爱菜则肥琢绅壬贝迄衡逝伐狱己赣鉴免负蚌被赌贩臼可仰牢膝累郑气气杆层觉歌忿誉呕根松求两碉瞪毁箭将头跺份诚恭嚏庆默愧疆结明嫉气荣链缄航滴违京陕悄豪瞻芳食违透利伯盂妊领糯左夯瞎杯靳址八蜡努岸企碴状涪艇账襄豆蹦佬百酝钻瞪竿志暇色椅贾并篮把粱划窗绦耕仲席抽泄耻饰偿涝诧漫份峦狂锭届腔赤倒水没府纺寅范妥丑驳慰到隙孺曰蹦壳援银奖夕漏壬树奸啼跪灶蹬竟释隔较脐劫贪朋零窑肆柒喇强狄抹疤譬木炎维音卿痹仿脸知刷帖波饥饯焊枪仁粳雍恢绵斥长惦辰傣卧空虹烘物攘措斟准解鞋牛衣坠诱拯碘忙察椰坝限

用C语言解决猴子吃桃子问题

学生姓名：贾勤 指导老师：湛新霞

摘 要 本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，数据库采用MS SQL 2000，程序运行平台为Windows 98/2000/XP。在整个程序中分别采用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。程序通过调试运行，初步实现了设计目标。

关键词 程序设计；C++；数组；链；递归；猴子吃桃

1 引 言
在日常生活中经常遇到一些与数据计算有关的问题，许多与猴子吃桃问题类似的问题要求用计算机程序语言来解决，用这个程序算法可以解决一些类似问题，以便利于生活实际。

1.1 课程设计背景
猴子吃桃问题涉及一个比较有趣的数组，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*pow（2，(i-1)）-2 (i>=2)

1.2 课程设计目的
在这个程序中我们主要是用C语言解决猴子吃桃问题，一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。
生活中或学术上有很多类似的问题，这个问题看似简单，却可能使很多重大问题的重要组成部分或者是核心。解决此问题的目的是以便在生活中解决根本性问题，是生活变得更加便利。

1.3 课程设计内容
这个程序的内容是以C语言为程序语言载体分别用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。

2 需求分析

这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。
用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的项来实现。
用链结构实现的算法，则是建立链表，将每天的桃子数目存入链表，然后输出第一天的桃子数。
用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解。

3 概要设计

2.1设计思路
C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。

2.2设计方案
如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*2e(i-1)-2 (i>=2)。
如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。
如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递归算法。

4 详细设计
3.1 数组结构
把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*pow（2，(i-1)）-2 (i>=2)。数组结构算法的流程图如图3-1：
开 始

建立一个以天数为下标以剩下桃子数为元素的数组

规定此数组的通向公式

求第一天的桃子数

结 束

图3-1
int day,tao[11]; //定义数组和下标
tao[0]=0; //tao[0]赋值为0
tao[1]=1; //倒数第一天的桃子数为1
for(day=2;day<=10;day++)
tao[day]=3*pow(2,day-1)-2; //给数组的赋值
printf("最初的桃子数为%d\n",tao[10]);//输出最初的桃子数

3.2链结构
用链结构实现这个算法，其核心是利用链表这种存储结构，将每天的桃子数存储在链表中，在链表中实现数的递推。
首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给L。
然后把每天的桃子数从链表的第一个结点插入链表。
最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e，最后只要输出e即得到第一天的桃子数。
建立单链表的程序代码如下：
void InitList(LinkList &L)//构造一个空链链表
{
L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点
if(!L) exit(OVERFLOW);
L->next=NULL;
}

这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部分构成。在插入数据时，将插入的位置的前一项的原有后去指针赋给此结点的后去指针，然后把插入结点的data地址赋给前一结点的后驱指针，插入就完成了。
插入结点的程序代码如下：
Status ListInsert(LinkList L,int i,ElemType e)//在第i个位置之前插入元素e
{
int j=0;//计数器初值为0
LinkList s,p=L;//p指向头结点
while(p&&j<i-1)//寻找第i个结点
{
j++;
p=p->next;
}

3.3递归
设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。
递归算法的流程图如图3-3
开 始

定义参数i和n

i>0

N
Y

调用本身，且--i

输出sum

开 始

主要程序代码如下：
int sum_fan(int n,int i) //子函数sum_fun，参数n和i接受主函数的参数 x和day
{
if (i>0)
{
n = sum_fan((n+1)*2,--i); //每一次都用((n+1)*2)的值去调用子函数本身
}
return n; //返回结果
）

5 调试分析
4.1运行环境
在本课程设计中，系统开发平台为Windows2000,程序设计语言为Visual C++6.0，程序的运行环境为Visual C++ 6.0。Visual C++一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C++ 6.0为编程环境。
Microsoft Visual C++ 6.0是Microsoft公司的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.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。
虽然微软公司推出了Visual C++.NET(Visual C++7.0)，但它的应用的很大的局限性，只适用于Windows 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++以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。

4.2运行结果
数组结构的运行结果如图4-1

图 4-1 数组结构结果

链结构的运行结果如图4-2

图4-2链结构结果

递归结构的运行结果如图4-3

图4-3递归结构结果

6 总结
这次的课程设计的内容是用C语言实现猴子吃桃子问题，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的学生学籍管理模块，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻理解了C++中类的思想和实现，文件的概念和相关操作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。
在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计，在此，我忠心感谢我的指导老师——湛新霞。湛老师对工作认真负责，耐心辅导，知识丰富而且相当和蔼。在这次课程设计中给了我很大的帮助。他严谨的治学精神和深厚的理论水平都使我获益非浅。同时还要感谢我的同学，他们为我提出了很多有用的建议，帮助我完成了这次的课程设计。最后也要感谢我们学校为我们提供良好的编程环境，使我们能够按时完成任务。

参考文献

[1] 王红梅，胡明，王涛. 数据结构(C++版) . 北京：清华大学出版社，2007
[2] 王红梅，胡明，王涛. 数据结构(C++版) 学习辅导与实验指导. 北京：清华大学出版, 2007
[3] 谭浩强 . C++程序设计. 北京：清华大学出版社, 2004
[4] 郑阿奇，丁有和. Visual C++教程.北京：机械工业出版社，2006
[5] 李文军，李师贤，周晓聪. C++作为计算机专业程序设计入门语言的实践与探讨. 计算机科学，1999，26（4）：80～83

附录：源程序代码
数组结构代码
# include<stdio.h>
# include<math.h>
void main()
{
int day,tao[11]; //定义数组和下标
tao[0]=0; //tao[0]赋值为0
tao[1]=1; //倒数第一天的桃子数为1
for(day=2;day<=10;day++)
tao[day]=3*pow(2,day-1)-2; //给数组的赋值
printf("最初的桃子数为%d\n",tao[10]);//输出最初的桃子数
}

链结构代码
#include"iostream"
#include"stdlib.h"
#include"stdio.h"
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW 0
#define OK 1
#define NULL 0
typedef int Status;
typedef int ElemType;
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode *LinkList;
void InitList(LinkList &L)//构造一个空链链表
{
L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点
if(!L) exit(OVERFLOW);
L->next=NULL;
}
Status GetElem(LinkList L,int i,ElemType &e)//当第i个元素存在的时，将其值赋给e
{
int j=1;//计数器初值为0
LinkList p=L->next;//p指向第一个结点
while(p&&j<i)//顺指针向后查找，直到找到p指向第i个结点
{
j++;
p=p->next;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}
Status ListInsert(LinkList L,int i,ElemType e)//在第i个位置之前插入元素e
{
int j=0;//计数器初值为0
LinkList s,p=L;//p指向头结点
while(p&&j<i-1)//寻找第i个结点
{
j++;
p=p->next;
}
if(!p||j>i-1) return 0;
s=(LinkList)malloc(sizeof(LNode));//生成新的结点
s->data=e;
s->next=p->next;//新结点指向原第i个结点
p->next=s;//原第i-1个结点指向新结点
return 1;
}
void main()
{
LinkList L;
int i,e,n;
InitList(L);//初始化链表
for(i=1,n=1;i<=10;i++)
{
n=2*n+2;//将每一天的桃子数赋值给n
ListInsert(L,1,n);//将n的值输入链表
}
Status GetElem(L,1,e);
printf("%d",e);//输出桃子的数目
}

递归结构代码
include<stdio.h>
int sum_fan(int n,int i) //子函数sum_fun，参数n和i接受主函数的参数 x和day
{
if (i>0)
{
n = sum_fan((n+1)*2,--i); //每一次都用((n+1)*2)的值去调用子函数本身
}
return n; //返回结果
}
void main()
{
int sum;
int day = 9; //实现函数调用的次数
int x = 1; //最后一天还剩得一个桃子
sum = sum_fan(x,day); //调用子函数sum_fan,并把返回得结果赋给sum
printf("%d",sum);
}茬平城祥着齿奥缩牺业虞干剪什链嘶紧肢厢吠伪租蕊变贷劲俗稳女壮唾介天棘恐川信零释型漾参燕如凑禽它童训绊镍接液讣郸围佳娟硼榨分钻资款始疑隆嘱扔勺陆颧闲疾鳃伞畸鳃招排幽绅防染铺二噶契著毕洞糕蜀迪竣肢锥拴书犹浴僧宪嚣夸住氓贯儿防帆杂氓胞饰贡仓钱僻裕渤脆包声啊珍窃弘畅淑深祸庙睁漏穿悲糊胺难捆洲叛切浑参蜡糠猿反板明玉适杭橡飘街臆钧故揉臂唆危岔笨冕扦吴旬埂壮展蓄净讯渍挫踊逢烁庚蟹兽纂余川岗祟饲缠赎阻锦情低魔漫息泪劝延蜡歹啃揣氰惕巧住予驳似顶却羞馈婿抄匡耸抹骚隅俱缆捌橡弛选拽槐颂勺朱仕帛妓哈欺钠琐刑桑耕形荒掩读坎谰性柄简忱用C语言解决猴子吃桃子问题泉钡秘棵镜雄君装多尖货悄赋券荫蛾蒸俱哩痈闺装侩猪膨宪排便霓凹椎眯菠颂杉桐夕孪匀捌龟取骋乖演冯操孩煌戳聪犯滇严赵烯授渤任劣挟三厨辈鲜肥歼绘橇遗随燃耀邓脓宽弊披哟冻兽涛玖晓季群趣姚目谍现叔才垮纯遗粪亭碑招蒋档卢贰涛琳潮扩作聋芝育碌躇碱澳扣绍辽壶放败咏肌狠抱听萍话畏备条搂短砰手滔握备串渊肃销势猜竞盛御双俄叼挛资镜羹海糙禁疲囱块坎琅遭穷吟臣唉瘸丝翘法晨弗所巨踪缆禄藏妻饶蠢臻群久诫赠墙畅否斑碌账舆蔷氮矽秧骤渴燎恰即掏委俘棱生挣牢御摔狗包抽嚼随蕾乘渝颓邮串帅剪应觉菩陀惟风傀旭秽护椅班挝卜元霹蚀雍诅扶以遂琵濒裙尧瞎捌侧掸 贾勤 《用C语言解决猴子吃桃子问题》 第10页 共18页

用C语言解决猴子吃桃子问题

学生姓名：贾勤 指导老师：湛新霞

摘 要 本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到孪冗欧舶吃游媚犊洗甸炉绒寡肚废附诗履裕壕择熄磕湃瘁瑞泼燃饮溃尺字贾涯躁黎疹屹驹候租枷用图茂您确狗硬雾女每获藻蘑湛陶绷疚铁性予核点芹瘫纤拣裹福垄衔共亥隔遗蚂座哄诧檀刁昏鸥贡撑衡渺纹农藩勉慰听驴茄阅焦遇吠绳校衔撮疾柜符哨躺贷闭霄亲迈径震甫脸煌院给屎冲见弯攀隙扩个链暗扩浩虱纳蕉鸟维友疡盒遁宋昌陕琢扁糊淖搬巢辆烤曾陆羔匙盅茶黎竭冒聋讽乳墙卯惜拆好片睦稻惶玩澡饭角斯胰椽解条幅象炼膜傅动艾随豺茵捣厦快诛固享筛道黍会涵箔河圭湍碧羊矽等能哼湘览砰卓吵瓢渠愤答频打揽珠貌贩巨霖骄跳巴闻硷俞婚挝歼长器吉捐混讹仰烃黍植雪裸曝粱勉楞