猴子吃桃問題大數據結構課程設計設計題目

猴子吃桃子問題有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現求出原來這群猴子共摘了多少個桃子。二、運行環境（軟、硬件環境）VC++6.0PC電腦一臺算法的需求分析1)

采用數組數據結構實現上述求解2)

采用鏈數據結構實現上述求解3)

采用遞歸實現上述求解4)

如果采用4種方法者,適當加分//用戶界面intDesk(intn){ printf("**************************************************\n"); printf("|歡迎進入猴子吃桃子系統|\n"); printf("|1-數組法2-鏈表法3-遞歸法4-二叉樹法5-退出|\n"); printf("***************************************************\n"); printf("請輸入要選擇的方法:"); scanf("%d",&n); getchar(); system("cls");//刷新屏幕 while(n<1||n>5) { printf("***輸入錯誤!請重新輸入***\n"); scanf("%d",&n); } returnn;}四、算法概要設計//采用鏈數據結構(棧)實現上述求解typedefstruct{ int*top; int*base;}stack;//初始化一個棧stackInit(stack*s)猴子吃桃問題大數據結構課程設計全文共12頁，當前為第1頁。猴子吃桃問題大數據結構課程設計全文共12頁，當前為第1頁。 s->base=(int*)malloc(STACK_SIZE*sizeof(int)); if(s->base==NULL) { printf("Initfailed!\n"); exit(-1); } s->top=s->base; return*s;}//二叉樹創建一個大小為DAYS(由用給出)的二叉樹,二叉樹的左孩子節點存放當天的桃子數，右節點存放數字1，即為多吃的一個桃子。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;//根節點的數據為第DAYS天的桃子數 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的地址}猴子吃桃問題大數據結構課程設計全文共猴子吃桃問題大數據結構課程設計全文共12頁，當前為第2頁。//算法框架圖打印共摘的桃子數量打印共摘的桃子數量判斷是否執行完畢進入猴子吃桃子系統界面開始選擇要使用的方法進入該函數判斷是否執行完畢繼續執行N Y NY猴子吃桃問題大數據結構課程設計全文共12頁，當前為第3頁。猴子吃桃問題大數據結構課程設計全文共12頁，當前為第3頁。算法詳細設計#include<stdio.h>#include<stdlib.h>#include"peach.h"http://函數聲明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;}//頭文件代碼猴子吃桃問題大數據結構課程設計全文共12頁，當前為第4頁。#defineDAYS10//定義給定的天數猴子吃桃問題大數據結構課程設計全文共12頁，當前為第4頁。#defineSTACK_SIZE5//棧的容量,實際只用了一個#defineTRUE1#defineERROR0voidpeach_3(intn,inti);//用戶界面intDesk(intn){ printf("**************************************************\n"); printf("|歡迎進入猴子吃桃子系統|\n"); printf("|1-數組法2-鏈表法3-遞歸法4-二叉樹法5-退出|\n"); printf("***************************************************\n"); printf("請選擇要使用的方法:"); scanf("%d",&n); getchar(); system("cls");//刷新屏幕 while(n<1||n>5) { printf("***輸入錯誤!請重新輸入***\n"); scanf("%d",&n); } returnn;}//采用數組數據結構實現上述求解voidpeach_1(void){ intpeach[50]={0}; inti=0,j=0; peach[DAYS-1]=1;//最后一天的桃子數 for(i=DAYS;i>0;--i,j=i-1) { peach[j]=2*(peach[i]+1); } printf("*********************\n"); printf("*數組法*\n"); printf("*這群猴子共摘了%d個桃子*\n",peach[0]); printf("*********************\n");}//采用鏈數據結構實現上述求解typedefstruct{ int*top; int*base;}stack;//初始化一個棧stackInit(stack*s)猴子吃桃問題大數據結構課程設計全文共12頁，當前為第5頁。{猴子吃桃問題大數據結構課程設計全文共12頁，當前為第5頁。 s->base=(int*)malloc(STACK_SIZE*sizeof(int)); if(s->base==NULL) { printf("Initfailed!\n"); exit(-1); } s->top=s->base; return*s;}//把當天的桃子數進棧voidPush(stack*s,intnum){ *s->top++=2*(num+1);}//把前一天的桃子數出棧voidPop(stack*s,int&num)//&num位地址傳遞，可以直接對參數進行修改{ num=*--s->top;}voidpeach_2(stack*s){ inti=0; intnum=0; Push(s,1);//先把最后一天的桃子數進棧 i++; while(i<DAYS) { Pop(s,num); Push(s,num); i++; } printf("*********************\n"); printf("*鏈表法*\n"); printf("*這群猴子共摘了%d個桃子*\n",num); printf("*********************\n");}voidpeach_3(intn,inti){ if(i==DAYS)//DAYS為遞歸終止條件由用戶給出 { printf("*********************\n"); printf("*遞歸法*\n"); printf("*這群猴子共摘了%d個桃子*\n",n); printf("*********************\n"); } else {猴子吃桃問題大數據結構課程設計全文共12頁，當前為第6頁。 n=2*(n+1);猴子吃桃問題大數據結構課程設計全文共12頁，當前為第6頁。 peach_3(n,i+1); }}//二叉樹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;//根節點的數據為第DAYS天的桃子數 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的地址}//對二叉樹進行賦值計算voidcalculate(tree*T){ inti=0; tree*T1,*T2,*T3;//T1,T3分別為T2的左右孩子 T2=T; for(i=0;i<DAYS-1;i++) { T1=T2->lchild; T3=T2->rchild; T1->data=2*(T2->data+T3->data); T2=T1;猴子吃桃問題大數據結構課程設計全文共12頁，當前為第7頁。 }猴子吃桃問題大數據結構課程設計全文共12頁，當前為第7頁。}//二叉樹遍歷最左下角的孩子節點voidpeach_4(tree*T){ calculate(T); while(T->lchild!=NULL) { T=T->lchild; } printf("*********************\n"); printf("*二叉樹法*\n"); printf("*這群猴子共摘了%d個桃子*\n",T->data); printf("*********************\n");}六、算法的測試開始函數功能：開始函數功能：1-數組法2-鏈表法3-遞歸法4-二叉樹法5-退出選擇一個功能執行該功能#include<stdio.h>#include<stdlib.h>#include"peach.h"http://函數聲明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: 猴子吃桃問題大數據結構課程設計全文共12頁，當前為第8頁。peach_1();猴子吃桃問題大數據結構課程設計全文共12頁，當前為第8頁。break;case2: peach_2(&s);break;case3:peach_3(n,i);break;case4:peach_4(&T);break;case5: exit(0);break;}}return0;}//采用數組數據結構實現上述求解voidpeach_1(void){intpeach[50]={0};inti=0,j=0;peach[DAYS-1]=1;//最后一天的桃子數for(i=DAYS;i>0;--i,j=i-1){peach[j]=2*(peach[i]+1);}printf("*********************\n");printf("*數組法*\n");printf("*這群猴子共摘了%d個桃子*\n",peach[0]);printf("*********************\n");}猴子吃桃問題大數據結構課程設計全文共12頁，當前為第9頁。猴子吃桃問題大數據結構課程設計全文共12頁，當前為第9頁。voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子數進棧i++;while(i<DAYS){Pop(s,num);Push(s,num);i++;}printf("*********************\n");printf("*鏈表法*\n");printf("*這群猴子共摘了%d個桃子*\n",num);printf("*********************\n");}voidpeach_3(intn,inti){if(i==DAYS)//DAYS為遞歸終止條件由用戶給出{printf("*********************\n");printf("*遞歸法*\n");猴子吃桃問題大數據結構課程設計全文共12頁，當前為第10頁。printf("*這群猴子共摘了%d個桃子*\n",n);猴子吃桃問題大數據結構課程設計全文共12頁，當前為第10頁。printf("*********************\n");}else{n=2*(n+1);peach_3(n,i+1);//循環體 }}//二叉樹遍歷最左下角的孩子節點voidpeach_4(tree*T){calculate(T);while(T->lchild!=NULL){T=T->lchild;}printf("*********************\n");printf("*二叉樹法*\n");printf("*這群猴子共摘了%d個桃子*\n",T->data);printf("******************