猴子吃桃子問(wèn)題.docx

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 班級(jí)： 姓名： 學(xué)號(hào)： 日期：201113目 錄1 問(wèn)題描述12 需求分析13 概要設(shè)計(jì)231函數(shù)應(yīng)用232模塊劃分24 詳細(xì)設(shè)計(jì)35 測(cè)試分析106 課程設(shè)計(jì)總結(jié)111. 問(wèn)題描述猴子吃桃子問(wèn)題 有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。 要求：1) 采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解2) 采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解3) 采用遞歸實(shí)現(xiàn)上述求解2 需求分析1） 根據(jù)問(wèn)題已知第十天剩余桃子數(shù)，求總共桃子數(shù)，我們先列出方程可知，有后往前推可知道每天剩余桃子數(shù) ，這樣來(lái)求解。2） 棧鏈比較困難，需要跟遞歸聯(lián)系，遞歸實(shí)現(xiàn)在說(shuō)。3） 遞歸實(shí)現(xiàn)可以有數(shù)組上體現(xiàn)f(n)=2f(n+1)+2,跟數(shù)組的道理查不多，而棧鏈實(shí)現(xiàn)也需要這個(gè)方程，所以整個(gè)程序是相通的。3概要設(shè)計(jì)1） 函數(shù)應(yīng)用除了主函數(shù)以外大部分都是算法函數(shù)，還有棧的輸入與輸出函數(shù)：void main()Push(&S,&e)Pop(&S,&e)2）模塊劃分本程序包括四個(gè)模塊：( 1 ) 主程序模塊void main()初始化；數(shù)組求解；遞歸求解；棧鏈求解；( 2 ) 棧模塊實(shí)現(xiàn)棧的抽象數(shù)據(jù)類(lèi)型( 3 ) 數(shù)組模塊實(shí)現(xiàn)數(shù)組的運(yùn)用( 4 ) 遞歸模塊實(shí)現(xiàn)遞歸的運(yùn)用4 詳細(xì)設(shè)計(jì)#includestdio.h#includestdlib.h#define N 20typedef struct node int datax; int datay; struct node *next;Node;typedef Node *LinkStack; LinkStack Push(LinkStack s,int a, int b)Node *p;p=(LinkStack)malloc(sizeof(Node);p-datax=a;p-datay=b;p-next=s;s=p;return s;LinkStack Pop(LinkStack s) LinkStack p;if(s=NULL)printf(棧已空n);return NULL;p=s;s=s-next;free(p);return s;void Zhanlian(int n)int f;LinkStack s=NULL;for(n=1;ndatax*f+s-datay;s=Pop(s);printf(%dn,f);elses=Push(s,2,2);void suzhu()int i,aN;a10=1;for(i=9;i=1;i-)ai=2*ai+1+2;printf(%dn,a1);int fun(int n)if(n=10)return 1;elsereturn(2*fun(n+1)+2);/*主函數(shù)*/void main()int sum;printf(數(shù)組實(shí)現(xiàn):);suzhu();printf(棧鏈實(shí)現(xiàn):);Zhanlian(1);printf(遞歸實(shí)現(xiàn):);sum=fun(1);printf(%dn,sum);5 測(cè)試分析測(cè)試數(shù)據(jù)及結(jié)果如下圖 ：6 課程設(shè)計(jì)總結(jié)總的來(lái)說(shuō)這次課程設(shè)計(jì)還是學(xué)到了一些東西，可能還有很多不足的地方，但希望在以后是學(xué)習(xí)中補(bǔ)足?？偨Y(jié)了一下在這次課程設(shè)計(jì)中學(xué)到的東西，一方面除了進(jìn)一步鞏固了平常上課所學(xué)到，和以前學(xué)到的東西外。另一方面就是自己的不足了，有時(shí)一些以前學(xué)過(guò)的東西自己不會(huì)用，用了反而使程序更復(fù)雜，所以一開(kāi)始的程序很復(fù)雜，但是在查過(guò)資料后改進(jìn)才有了這個(gè)程