猴子吃桃問(wèn)題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

一、設(shè)計(jì)題目 猴子吃桃子問(wèn)題有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。二、 運(yùn)行環(huán)境（軟、硬件環(huán)境）VC++6.0PC電腦一臺(tái)三、算法的需求分析1） 采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解2） 采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解3） 采用遞歸實(shí)現(xiàn)上述求解4） 如果采用4種方法者，適當(dāng)加分〃用戶界面intDesk(intn){printf("**************************************************\n");printf("l歡迎進(jìn)入猴子吃桃子系統(tǒng) printf("l歡迎進(jìn)入猴子吃桃子系統(tǒng) l\n"）；printf（"l1-數(shù)組法2-鏈表法3-遞歸法4-二叉樹(shù)法5-退出l\n"）;printf("***************************************************\n");printf（-請(qǐng)輸入要選擇的方法：”）;scanf("%d”,&n);getchar();system("cls");//刷新屏幕while(n<1lln>5){printf("***輸入錯(cuò)誤！請(qǐng)重新輸入***\n");scanf("%d”,&n);}returnn;}四、算法概要設(shè)計(jì)〃采用鏈數(shù)據(jù)結(jié)構(gòu)(棧)實(shí)現(xiàn)上述求解typedefstruct{int*top;int*base;}stack;//初始化一個(gè)棧stackInit(stack*s)s->base=(int*)malloc(STACK_SIZE*sizeof(int));if(s->base==NULL){printf("Initfailed!\n");exit(-1);}s->top=s->base;return*s;}//二叉樹(shù)創(chuàng)建一個(gè)大小為DAYS(由用給出)的二叉樹(shù),二叉樹(shù)的左孩子節(jié)點(diǎn)存放當(dāng)天的桃子數(shù)，右節(jié)點(diǎn)存放數(shù)字1,即為多吃的一個(gè)桃子。typedefstructTNode{intdata;structTNode*lchild;structTNode*rchild;}tree;//創(chuàng)建一個(gè)二叉樹(shù)treeCreatTree(tree*T)//T為指針類型{intn=0,i=0;tree*p,*pr,*T1;T=(tree*)malloc(sizeof(TNode));T1=T;T->data=1;//根節(jié)點(diǎn)內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)for(i=1;i<DAYS;i++){p=(tree*)malloc(sizeof(TNode));pr=(tree*)malloc(sizeof(TNode));pr->lchild=NULL;pr->rchild=NULL;p->data=0;pr->data=1;T1->lchild=p;T1->rchild=pr;T1=p;}T1->lchild=NULL;T1->rchild=NULL;return*T; 〃返回T的地址//算法框架圖五、算法詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#include"peach.h"http://函數(shù)聲明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){intdata=0;intn=1,i=1;stacks;treeT;s=Init(&s);T=CreatTree(&T);while(1){switch(Desk(n)){case1: peach_1();break;case2: peach_2(&s);break;case3: peach_3(n,i);break;case4: peach_4(&T);break;case5: exit(0);break;}}return0;}〃頭文件代碼#defineDAYS10//定義給定的天數(shù)#defineSTACK_SIZE5//棧的容量，實(shí)際只用了一個(gè)#defineTRUE1#defineERROR0voidpeach_3(intn,inti);Desk(intn)//用戶界面int{Desk(intn)printfk**************************************************\n/?printf(-| 歡迎進(jìn)入猴子吃桃子系統(tǒng) |\n〃)；printf(〃|1-數(shù)組法2-鏈表法3-遞歸法4-二叉樹(shù)法5-退出|\n〃)；1—.reprintfk個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)\n/；printf(〃請(qǐng)選擇要使用的方法：〃)；scanf(〃％d〃，&n);getchar();system(〃cls〃)；//刷新屏幕while(n<1||n>5){printf(〃***輸入錯(cuò)誤！請(qǐng)重新輸入***\n〃)；scanf(〃％d〃，&n)；}returnn；}//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解voidpeach_1(void){intpeach[50]={0}；inti=0,j=0；peach[DAYS-1]=1；//最后一天的桃子數(shù)for(i=DAYS；i>0；--i,j=i-1){peach[j]=2*(peach[i]+1)；}printf(〃*********************\n〃)；printf(〃* 數(shù)組法 *\n〃)；printf(〃* 這群猴子共摘了%d個(gè)桃子*\n〃,peach[0])；printf(〃*********************\n〃)；}//采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解typedefstruct{int*top；int*base；}stack；//初始化一個(gè)棧stackInit(stack*s)s->base=(int*)malloc(STACK_SIZE*sizeof(int));if(s->base==NULL){printf("Initfailed!\n");exit(-1);}s->top=s->base;return*s;}//把當(dāng)天的桃子數(shù)進(jìn)棧voidPush(stack*s,intnum){*s->top++=2*(num+1);}//把前一天的桃子數(shù)出棧voidPop(stack*s,int&num)//&num位地址傳遞，可以直接對(duì)參數(shù)進(jìn)行修改{num=*—s->top;}voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子數(shù)進(jìn)棧i++;while(i<DAYS){Pop(s,num);Push(s,num);i++;}printf("*********************\n");printf("* 鏈 表 法 *\n");printf("* 這群猴子共摘了%d個(gè)桃子*\n",num);printf("*********************\n");}voidpeach_3(intn,inti){if(i==DAYS)//DAYS為遞歸終止條件由用戶給出{printf("*********************\n");printf("* 遞歸法 *\n");printf("* 這群猴子共摘了%d個(gè)桃子 *\n",n);printf("*********************\n");}else{n=2*(n+1);peach_3(n,i+1);//二叉樹(shù)typedefstructTNode{intdata;structTNode*lchild;structTNode*rchild;}tree;treeCreatTree(tree*T)//T為指針類型{intn=0,i=0;tree*p,*pr,*T1;T=(tree*)malloc(sizeof(TNode));T1=T;T->data=1;//根節(jié)點(diǎn)內(nèi)的數(shù)據(jù)為第DAYS天的桃子數(shù)for(i=1;i<DAYS;i++){p=(tree*)malloc(sizeof(TNode));pr=(tree*)malloc(sizeof(TNode));pr->lchild=NULL;pr->rchild=NULL;p->data=0;pr->data=1;T1->lchild=p;T1->rchild=pr;T1=p;}T1->lchild=NULL;T1->rchild=NULL;return*T; 〃返回T的地址}//對(duì)二叉樹(shù)進(jìn)行賦值計(jì)算voidcalculate(tree*T){inti=0;tree*T1,*T2,*T3;//T1,T3分別為T(mén)2的左右孩子T2=T;for(i=0;i<DAYS-1;i++){T1=T2->lchild;T3=T2->rchild;T1->data=2*(T2->data+T3->data);T2=T1;

}//二叉樹(shù)遍歷最左下角的孩子節(jié)點(diǎn)voidpeach_4(tree*T){calculate(T);while(T->lchild!=NULL){T=T->lchild;}printf(〃** **** **** ***** *** ***\n〃)；printf(〃* 二叉 樹(shù)法*\n〃)；printf(〃* 這群猴子共摘了%d個(gè)桃子*\n",T->data);printf(〃*********************\n〃)；}六、算法的測(cè)試//主函數(shù)#include<stdio.h>#include<stdlib.h>#include"peach.h"六、算法的測(cè)試//主函數(shù)#include<stdio.h>#include<stdlib.h>#include"peach.h"http://函數(shù)聲明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){intdata=0;intn=1,i=1;stacks;treeT;s=Init(&s);T=CreatTree(&T);while(1){switch(Desk(n)){開(kāi)始函數(shù)功能：1-數(shù)組法2-鏈表法3-遞歸法

4-二叉樹(shù)法5-退出選擇一個(gè)功能執(zhí)行該功能case1:peach_1();break;case2:peach_2(&s);break;case3:peach_3(n,i);break;case4:peach_4(&T);break;case5:exit(0);break;}}return0;}//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解voidpeach_1(void){intpeach[50]={0};inti=0,j=0;peach[DAYS-1]=1;//最后一天的桃子數(shù)for(i=DAYS;i>0;--i,j=i-1){peach[j]=2*(peach[i]+1);}printf(〃*********************\n〃)；printf(〃* 數(shù)組法 *\n〃)；printf(〃* 這群猴子共摘了%d個(gè)桃子*\n〃,peach[0]);printf(〃*********************\n〃)；voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子數(shù)進(jìn)棧i++;while(i<DAYS){Pop(s,num);Push(s,num);i++;}printf("*********************\n");*\n");*\n",num);printf("**\n");*\n",num);printf("*這群猴子共摘了%d個(gè)桃子printf("*********************\n");?'C:\Users\Administrator\Desktop漩子吃桃子問(wèn)題\Debug懶子吃桃子問(wèn)題,exe- [口|?回*********************關(guān) 概 圭 注*「這群猴子共摘了1534個(gè)桃子**********************voidpeach_3(intn,inti){if(i==DAYS)//DAYS為遞歸終止條件由用戶給出{printf(〃*********************\n〃)；printf(〃* 遞歸法 *\n〃)；printf(〃* 這群猴子共摘了%d個(gè)桃子*\n〃,n);printf(〃*********************\n〃)；}else{n=2*(n+1);peach_3(n,i+1); //循環(huán)體}}//二叉樹(shù)遍歷最左下角的孩子節(jié)點(diǎn)voidpeach_4(tree*T){calculate(T);while(T->lchild!=NULL){T=T->lchild;}printf(〃** **** **** ***** *** ***\n〃)；printf(〃* 二叉 樹(shù)法*\n〃)；printf(〃* 這群猴子共摘了%d個(gè)桃子*\n",T->data);printf(〃*********************\n〃)；}七、運(yùn)行結(jié)果分析1、 數(shù)組法：創(chuàng)建一個(gè)大小為DAYS的一維數(shù)組a[DAYS]，a[0],a[1]...a[DAYS-1]分別存放當(dāng)天的桃子數(shù)，其