1、課 程 設 計課程設計名稱： 猴子吃桃問題 專 業 班 級 ： 學 生 姓 名 ： 學 號 ： 指 導 教 師 ： 課程設計時間： 計算機專業課程設計任務書學生姓名專業班級學號題 目猴子吃桃問題課題性質其它課題來源自擬課題指導教師同組姓名主要內容有一群猴子摘了一堆桃子，他們每天吃當前桃子的一半且多一個，到了第10天就只余下1個桃子，用多種方法求出原來這群猴子共摘了多少個桃子。使用鏈表數據結構實現猴子吃桃問題的求解；使用遞歸實現猴子吃桃問題的求解。任務要求 1研究應用遞歸算法2應用數據結構基礎知識進行實際問題求解與分析；3編程實現算法4具有良好的界面，操作方便靈活、簡潔高效。5按要求撰寫課程設計

2、報告和設計總結。參考文獻1c程序設計（第二版），譚浩強，北京，清華大學出版社，1999.2visual c+實用教程（第一版），張榮梅、梁曉林，冶金工業出版社，2004.3c+實用教程（第一版），楊明軍、董亞卓、汪黎，人民郵電出版社，2002.4數據結構（c語言版），嚴蔚敏，吳偉民，清華大學出版社，1997。 審查意見指導教師簽字：教研室主任簽字： 年 月 日 說明：本表由指導教師填寫，由教研室主任審核后下達給選題學生，裝訂在設計（論文）首頁1 需求分析int sum_fan(int n,int i) 子函數sum_fun，參數n和i接受主函數的參數 x和dayn = sum_fan(n+1)

3、*2,-i); 每一次都用(n+1)*2)的值去調用子函數本身sum = sum_fan(x,day); 調用子函數sum_fan,并把返回得結果賦給sum“前期工作”：構想源代碼中各個步驟，為編寫源程序準備。構思函數整體框架；1.首先定義好main函數；2.調用函數類型；3.編寫源程序；“后期工作”：敲定程序后，檢查程序是否健全。1.上機輸入源程序；2.對源程序進行編譯;3.對源程序進行調試；4.對源程序進行運行；2 概要設計首先，設第一天摘了x個桃子。然后，列出算術表達式：(x/2-1)/2-1)/2-1)/2-1.）=1，一共有9個除以2減一。接著, 從第九天分析，第9天的桃子是（1+1

4、）*2，第8天是(1+1)*2+1)*2,.一直到第一天。我嘗試著用遞歸來思考。可以發現每一天的桃子得數量都是用前一天桃子的數量加上1之后再乘以2。于是可以把式子換成(n+1)*2 ，然后可以把具體問題留給在子函數處理，用(n+1)*2的結果再去調用子函數本身。這樣就可以實現遞歸的嵌套了，最后再用主函數去調用子函數。3 運行環境（軟、硬件環境）window nt/2003/xp4 開發工具和編程語言開發工具：vc+編程語言：c/c+5 詳細設計#include#include#define null 0typedef struct linknode int data; struct linkn

5、ode *next;/鏈表指針node;node *head; /頭結點int day;void main() int n;pp:do printf(t *n); printf(t *猴子吃桃問題的實現方法*n); printf(t *n);printf(t 1 數組實現n); printf(t 2 遞歸實現n); printf(t 3 鏈表實現n); printf(t 4 退出程序n); printf(t *n); printf(t請選擇(1-4): bb); scanf(%d,&n); if(n4) printf(重新輸入1或2或3n); goto pp;else switch(n) ca

6、se 1: printf(使用數組的方法); array();break; case 2: printf(使用遞歸的方法); digui();break; case 3: printf(使用鏈表的方法); creat(); print(); break; case 4: exit(0); while(n=1&n=0;i-)arri-1=2*(arri+1);printf(第%d天還剩桃子%dn,i+1,arri);return 0;int digui()int fun(int);int count;count=fun(1);printf(count=%dn,count);int fun(int

7、 day)if(day=11)return 1;elsereturn (fun(day+1)+1)*2;int creat()/創建鏈表 node *p,*s; int peaches=1;/第十天時只剩下一個桃子 day=11; head=(node*)malloc(sizeof(node); p=head;while(day0) s=(node*)malloc(sizeof(node);/分配存屬空間 s-data=peaches;/用來存放結點數據 p-next=s; /把結點插入鏈表中 p=s; peaches=(peaches+1)*2;/第一天的桃子數是第二天桃子數加后的2倍； d

8、ay-; p-next=null; p=head; head=head-next;/使頭指針指向頭結點 free(p); /釋放指針p return 0;int print()/輸出從這十天每天的桃子數 int a; node *p; p=head;day=11;while(p&day0) printf(第%d天的桃子數:%d個n,day,p-data); p=p-next; day-;return 0;6 調試分析在這段代碼的編寫過程中我遇到了一些問題。我的問題有兩個：來源：(/s/blog_43b943ab01009mf9.html) - 關于猴

9、子吃桃子得問題（遞歸算法）_王磊_新第一，在遞歸調用子函數本身時，沒有找到一個方法去控制它調用的次數。第二，沒有想到要用一個變量去保存它每一次調用本身后得結果，以至于無法返回到主函數解決第一個問題:設置一個變量day = 9 然后用放在調用子函數的第二個參數里面去控制子函數調用本身的次數。第二個問題的解決方法:在子函數里面用n 去保存遞歸算法返回的值。7 測試結果（小三黑體）程序運行結果如圖1所示圖1 程序運行結果1圖2 程序運行結果2圖3 程序運行結果3圖4 程序運行結果4參考文獻1.邊肇祺，模式識別（第二版），北京：清華大學出版社,1988，25352. 李永忠，幾種小波變換的圖像處理技術，西北民族學院學報（自然科學版），2001.6,22（3），15183c程序設計（第二版），譚浩強，北京，清華大學出版社，1999.4visual c+實用教程（第一版），張榮梅、梁曉林，冶金工業出版社，2004.5c+實用教程（第一版），楊明軍、董亞卓、汪黎，人民郵電出版社，2002.6數據結構（c語言版），嚴蔚敏，吳偉民，清華大學出版社，1997。 心得體會通過該課程設計，全面系統的理解了解了編譯原理程序構造的 一般原理和一般原理和基本實現方法。把死板的課本知識變的生動有趣，激發了學習的積極性。把學過的計算機編程原理的知識強化，能夠把課堂上