数据结构课程设计-猴子吃桃问题

0数学与计算机学院课程设计说明书课程名称:课程代码:6015059题目:年级/专业/班:学生姓名:学号:312011070102216开始时间:2014年5月14日完成时间:2014年5月28日课程设计成绩：学习态度及平时成绩（20）技术水平与实际能力（20）完成情况(20)创新（5）说明书（计算书、图纸、分析报告）撰写质量（35）总分（100）指导教师签名：年月日文章编辑系统1目录1需求分析……………………………………………………………………32概要设计……………………………………………………………………33详细设计……………………………………………………………………44调试分析……………………………………………………………………115用户使用说明………………………………………………………………126测试结果……………………………………………………………………127结论………………………………………………………………………14致谢……………………………………………………………………………15参考文献………………………………………………………………………15文章编辑系统2摘要本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。在课程设计中，系统开发平台为Windows2000，程序设计设计语言采用VisualC++，数据库采用MSSQL2000，程序运行平台为Windows98/2000/XP。在整个程序中分别采用数组数据结构、链数据结构、递归等结构形式实现此问题的求解。程序通过调试运行，初步实现了设计目标。关键词：程序设计；C++；数组；链；递归；猴子吃桃引言在日常生活中经常遇到一些与数据计算有关的问题，许多与猴子吃桃问题类似的问题要求用计算机程序语言来解决，用这个程序算法可以解决一些类似问题，以便利于生活实际。文章编辑系统31需求分析1.1任务与分析任务功能：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子要求：采用数组数据结构实现上述求解采用链数据结构实现上述求解采用递归实现上述求解如果采用4种方法者,适当加分分析：这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的项来实现。用链结构实现的算法，则是建立链表，将每天的桃子数目存入链表，然后输出第一天的桃子数。用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解。1.2测试数据输入任意一篇文章，按要求输入功能序号与字符串。测试是否能按要求输出正确结果。2概要设计文章编辑系统4C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标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,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递归算法。3详细设计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：建立一个以天数为下标以剩下桃子数为元素的数组规定此数组的通向公式开始文章编辑系统5图3-1intday,tao[11];//定义数组和下标tao[0]=0;//tao[0]赋值为0tao[1]=1;//倒数第一天的桃子数为1for(day=2;day=10;day++)tao[day]=3*pow(2,day-1)-2;//给数组的赋值printf(最初的桃子数为%d\n,tao[10]);//输出最初的桃子数3.2链表结构用链结构实现这个算法，其核心是利用链表这种存储结构，将每天的桃子数存储在链表中，在链表中实现数的递推。首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给L。然后把每天的桃子数从链表的第一个结点插入链表。最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e，最后只要输出e即得到第一天的桃子数。建立单链表的程序代码如下：voidInitList(LinkList&L)//构造一个空链链表{L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点if(!L)exit(OVERFLOW);L-next=NULL;}求第一天的桃子数结束文章编辑系统6这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部分构成。在插入数据时，将插入的位置的前一项的原有后去指针赋给此结点的后去指针，然后把插入结点的data地址赋给前一结点的后驱指针，插入就完成了。插入结点的程序代码如下：StatusListInsert(LinkListL,inti,ElemTypee)//在第i个位置之前插入元素e{intj=0;//计数器初值为0LinkLists,p=L;//p指向头结点while(p&&ji-1)//寻找第i个结点{j++;p=p-next;}3.3递归设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。递归算法的流程图如图3-3开始定义参数i和ni0调用本身，且--i输出sum开始YN文章编辑系统7主要程序代码如下：intsum_fan(intn,inti)//子函数sum_fun，参数n和i接受主函数的参数x和day{if(i0){n=sum_fan((n+1)*2,--i);//每一次都用((n+1)*2)的值去调用子函数本身}returnn;//返回结果）程序完整代码//zhanghang123.cpp:主项目文件。#includestdafx.h#includestdio.h#includemath.h#includestring.h#includeiostream#includestdlib.husingnamespaceSystem;//ConsoleApplication1.cpp:主项目文件。voidmethod1()//数组实现{intday,tao[11];//定义数组和下标tao[0]=0;//tao[0]赋值为0tao[1]=1;//倒数第一天的桃子数为1for(day=2;day=10;day++)tao[day]=3*pow(2.0,day-1)-2;//给数组的赋值printf(最初的桃子数为%d\n,tao[10]);//输出最初的桃子数文章编辑系统8getchar();}intsum_fan(intn,inti)//子函数sum_fun，参数n和i接受主函数的参数x和day{if(i0){n=sum_fan((n+1)*2,--i);//每一次都用((n+1)*2)的值去调用子函数本身}returnn;//返回结果}voidmethod3()//递归{intsum;intday=9;//实现函数调用的次数intx=1;//最后一天还剩得一个桃子sum=sum_fan(x,day);//调用子函数sum_fan,并把返回得结果赋给sumprintf(%d,sum);getchar();}#defineTRUE1#defineFALSE0#defineERROR0#defineOVERFLOW0#defineOK1#defineNULL0typedefintStatus;typedefintElemType;structLNode{ElemTypedata;LNode*next;};typedefLNode*LinkList;voidInitList(LinkList&L)//构造一个空链链表{L=(LinkList)malloc(sizeof(LNode));//申请内存，产生头结点,并使L指向此头结点文章编辑系统9if(!L)exit(OVERFLOW);//判断是否申请成功L-next=NULL;//next指针置空}StatusGetElem(LinkListL,inti,ElemType&e)//当第i个元素存在的时，将其值赋给e{intj=1;//计数器初值为0LinkListp=L-next;//p指向第一个结点while(p&&ji)//顺指针向后查找，直到找到p指向第i个结点{j++;p=p-next;}if(!p||ji)returnERROR;e=p-data;returnOK;}StatusListInsert(LinkListL,inti,ElemTypee)//在第i个位置之前插入元素e{intj=0;//计数器初值为0LinkLists,p=L;//p指向头结点while(p&&ji-1)//寻找第i个结点{j++;p=p-next;}if(!p||ji-1)return0;//当第i节点不存在时s=(LinkList)malloc(sizeof(LNode));//生成新的结点s-data=e;s-next=p-next;//新结点指向原第i个结点p-next=s;//原第i-1个结点指向新结点return1;}voidmethod2(){LinkListL;inti,e,n;InitList(L);//初始化链表for(i=1,n=1;i10;i++){n=2*n+2;//将每一天的桃子数赋值给nListInsert(L,1,n);//将n的值输入链表}GetElem(L,1,e);文章编辑系统10printf(%d,e);//输出桃子的数目getchar();}intmain(arraySystem::String^^args){L:system(cls);puts(选择需要的方法来求解：请输入数字选项：);puts(*****************************);puts(1.数组求解法；);puts(2.链表求解法；);puts(3.递归求解法；);puts(*****************************);chara=getchar();if(a=='1'){method1();puts(\n请按任意键返回：);getchar();gotoL;}elseif(a=='2'){method2();puts(\n请按任意键返回：);getchar();gotoL;}elseif(a=='3'){method3();puts(\n请按任意键返回：);getchar();gotoL;}elseputs(请输入合法的选项；);gotoL;文章编辑系统11return0;}4调试分析运行环境在本课程设计中，系统开发平台为Windows2000,程序设计语言为VisualC++6.0，程序的运行环境为VisualC++6.0。VisualC++一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual