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

《数据结构课程设计--猴子吃桃子问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Dataorganizationcurriculmproject数据结构课程设计设计题目：猴子吃桃子问题专业班级：通信工程0804班学生学号：0909082421学生姓名：王璐指导老师：彭春华完成时间：2010-06-06目录1.问题描述……………………………………………….1页2.基本要求………………………………………………..1页3.程序设计思想………………………………………1---2页4.软件模块结构图………………………………………..2页5.程序流程图……………………………………………..3页6.源程序………………………………………………4---7页7.调试分析…………………

2、…………………………8---9页8.测试数据…………………………………………..9---10页9.心得体会…………………………………………11---12页一．问题描述这是一个很经典的简易的程序设计题，具体题目为:有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 二．基本要求1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解虽然题目很简单，但是要求用多种方法实现，要求知识比较全面，涉及到数组，链表，函数，指针，结构体，循环等方面的基础知识。三．程序设计思想1

3、．分析题目。每天吃当前桃子数目的一半再加一个，所以桃子数目肯定为偶数。用我们所熟悉的函数来表示，即：f(x+1)=f(x)/2-1;其中x代表第多少天。：猴子摘桃子的那天也就是第一天就吃了所摘桃子的一半加一个，所以桃子总数应该为第一天加1再乘以2，等效为f(0)。2.实现方法。最容易想到的也是最简单的就是运用函数的递归。给出了边界条件与递归函数，直接调用就可以了。用数组实现，先定义一个一维数组，然后结合循环，也可以求解。如果用链表的话，相对来说要复杂点。先要构建一个动态链表，将头指针赋值给p,p赋值给q，使p,q同时指向链表头,将第十天的桃子数放在链表第一个数据域中，然后移动p,q使

4、后一个数据域中存放的是前一个加1的2倍，即倒过来存放数据。四．软件模块结构图猴子吃桃问题用数组实现用递归实现用链表实现五．程序流程图开始选择实现方法数组递归链表输入x=10输入nn==9输出y【10】=1TFm=2*(duigui(n+1)+1)i>=0T输出m=1FY【x-1】=(y【x】+1)*2输出mx--输出y【x】六．源程序#include#include#defineNULL0typedefintdatatype;typedefstructlink{datatypetao;structlink*next;}node;voidshuzu

5、(){intday[11],i;day[10]=1;for(i=10;i>0;i--){day[i-1]=2*(day[i]+1);printf("%dt",i);printf("%d",day[i]);}printf("thetotal:%d",day[0]);}intdigui(intn){intm;if(n==9)m=1;elsem=2*(digui(n+1)+1);printf("%dt",n+1);printf("%d",m);return(m);}node*init_link(node*head){head=NULL;return(head);}nodem

6、;voidtoutao(node*head){inti=10;node*p,*q;p=head;m.tao=1;p=&m;while(i>0){q=p;q->tao=p->tao;p->next=(node*)malloc(sizeof(node));p=p->next;p->tao=2*(q->tao+1);printf("%dt",i);printf("%d",q->tao);i--;}printf("thetotal:%d",p->tao);voidmain()}{inta,m,j;node*head;head=NULL;printf("pleasechooseone

7、method:1:shuzu2:digui3:lianbiao");for(j=0;j<3;j++){scanf("%d",&m);switch(m){case1:printf("theresultofusingshuzu:");shuzu();break;case2:printf("theresultofusingdigui:");a=digui(0);printf("thetotal:%d",2*(a+1));break;case3:p