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

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

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

采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解2)

采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解3)

采用遞歸實現(xiàn)上述求解4)

如果采用4種方法者,適當加分//用戶界面intDesk(intn){ printf("**************************************************\n"); printf("|歡迎進入猴子吃桃子系統(tǒng)|\n"); printf("|1-數(shù)組法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;}四、算法概要設(shè)計//采用鏈數(shù)據(jù)結(jié)構(gòu)(棧)實現(xiàn)上述求解typedefstruct{ int*top; int*base;}stack;//初始化一個棧stackInit(stack*s)猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第1頁。猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共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;}//二叉樹創(chuàng)建一個大小為DAYS(由用給出)的二叉樹,二叉樹的左孩子節(jié)點存放當天的桃子數(shù)，右節(jié)點存放數(shù)字1，即為多吃的一個桃子。typedefstructTNode{ intdata; structTNode*lchild; structTNode*rchild;}tree;//創(chuàng)建一個二叉樹treeCreatTree(tree*T)//T為指針類型{ intn=0,i=0; tree*p,*pr,*T1; T=(tree*)malloc(sizeof(TNode)); T1=T; T->data=1;//根節(jié)點的數(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的地址}猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第2頁。//算法框架圖打印共摘的桃子數(shù)量打印共摘的桃子數(shù)量判斷是否執(zhí)行完畢進入猴子吃桃子系統(tǒng)界面開始選擇要使用的方法進入該函數(shù)判斷是否執(zhí)行完畢繼續(xù)執(zhí)行N Y NY猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第3頁。猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第3頁。算法詳細設(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)) { 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ù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第4頁。#defineDAYS10//定義給定的天數(shù)猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第4頁。#defineSTACK_SIZE5//棧的容量,實際只用了一個#defineTRUE1#defineERROR0voidpeach_3(intn,inti);//用戶界面intDesk(intn){ printf("**************************************************\n"); printf("|歡迎進入猴子吃桃子系統(tǒng)|\n"); printf("|1-數(shù)組法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;}//采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(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個桃子*\n",peach[0]); printf("*********************\n");}//采用鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解typedefstruct{ int*top; int*base;}stack;//初始化一個棧stackInit(stack*s)猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第5頁。{猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共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;}//把當天的桃子數(shù)進棧voidPush(stack*s,intnum){ *s->top++=2*(num+1);}//把前一天的桃子數(shù)出棧voidPop(stack*s,int&num)//&num位地址傳遞，可以直接對參數(shù)進行修改{ num=*--s->top;}voidpeach_2(stack*s){ inti=0; intnum=0; Push(s,1);//先把最后一天的桃子數(shù)進棧 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 {猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第6頁。 n=2*(n+1);猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共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;//根節(jié)點的數(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的地址}//對二叉樹進行賦值計算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;猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第7頁。 }猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第7頁。}//二叉樹遍歷最左下角的孩子節(jié)點voidpeach_4(tree*T){ calculate(T); while(T->lchild!=NULL) { T=T->lchild; } printf("*********************\n"); printf("*二叉樹法*\n"); printf("*這群猴子共摘了%d個桃子*\n",T->data); printf("*********************\n");}六、算法的測試開始函數(shù)功能：開始函數(shù)功能：1-數(shù)組法2-鏈表法3-遞歸法4-二叉樹法5-退出選擇一個功能執(zhí)行該功能#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: 猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第8頁。peach_1();猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第8頁。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)實現(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個桃子*\n",peach[0]);printf("*********************\n");}猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第9頁。猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第9頁。voidpeach_2(stack*s){inti=0;intnum=0;Push(s,1);//先把最后一天的桃子數(shù)進棧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");猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第10頁。printf("*這群猴子共摘了%d個桃子*\n",n);猴子吃桃問題大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全文共12頁，當前為第10頁。printf("*********************\n");}else{n=2*(n+1);peach_3(n,i+1);//循環(huán)體 }}//二叉樹遍歷最左下角的孩子節(jié)點voidpeach_4(tree*T){calculate(T);while(T->lchild!=NULL){T=T->lchild;}printf("*********************\n");printf("*二叉樹法*\n");printf("*這群猴子共摘了%d個桃子*\n",T->data);printf("******************