shiweijie《算法分析與設(shè)計》實驗指導(dǎo)與報告書.doc

常熟理工學(xué)院算法分析與設(shè)計實驗指導(dǎo)與報告書 _學(xué)年 第_學(xué)期專 業(yè)：_軟件工程（服務(wù)外包_）_學(xué) 號：_Y12309218_姓 名：_施偉杰_實驗地點：_N6-113_指導(dǎo)教師：_ _劉在德 _計算機科學(xué)與工程學(xué)院2011.02實驗?zāi)夸泴嶒? 求最大公約數(shù)2實驗2 斐波那契數(shù)列3實驗3 最近對問題4實驗4 堆排序5實驗5 霍納法則和二進制冪6實驗6 字符串匹配問題7實驗7 Warshall算法和Floyd算法8實驗8 最優(yōu)二叉查找樹9實驗9 Huffman編碼*10實驗10 求解非線性方程*11實驗11 投資問題*12注：（1）實驗4和實驗5為變治法應(yīng)用，二選一； （2）實驗7和實驗8為動態(tài)規(guī)劃法應(yīng)用，二選一；（3）帶*號的實驗為選做實驗，根據(jù)課時及學(xué)生實驗完成情況機動安排。實驗1 求最大公約數(shù)實驗?zāi)康模?）求兩個自然數(shù)m和n的GCD (Greatest Common Divisor)；（2）掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，但這些算法的思路不同，時間復(fù)雜性也不同。預(yù)習(xí)內(nèi)容P2 1.1 什么是算法算法是一系列解決問題的清晰指令，也就是說，對于符合一定規(guī)范的輸入，能夠在有限時間內(nèi)獲得所要求的輸出。實驗內(nèi)容（1）設(shè)計出3個版本的求最大公約數(shù)的算法；（2）采用C/C+實現(xiàn)算法，利用計數(shù)法記錄基本語句的執(zhí)行次數(shù)；（3）采用大O符號分析3種算法的時間復(fù)雜性；（4）通過分析對比，得出結(jié)論。實驗結(jié)果（可續(xù)頁）歐幾里得算法：#include #include int main() int n,r,m; printf(input two num:); scanf(%d%d,&m,&n); while(n!=0) r=m%n; m=n; n=r; printf(最大公約數(shù)為%d,m);return 0;連續(xù)整數(shù)檢測算法：#include #include int main() int n,t,m; printf(input two num:); scanf(%d%d,&m,&n); if(mn) t=n; else t=m; while(m%t)!=0 | (n%t)!=0) t=t-1; printf(最大公約數(shù)為%d,t);教師評分實驗2 斐波那契數(shù)列實驗?zāi)康模?）求斐波那契數(shù)列；（2）區(qū)分遞歸和遞推思想。預(yù)習(xí)內(nèi)容P60 2.5 例題：斐波那契數(shù)列實驗內(nèi)容（1）至少設(shè)計出3個版本的求斐波那契數(shù)列的算法；（2）采用C/C+實現(xiàn)算法；（3）采用大O符號分析3種算法的時間復(fù)雜性；（4）通過分析對比，得出結(jié)論。實驗結(jié)果（可續(xù)頁）1.遞歸計算法#include int main() long int fib61 = 0,1; int i; for(i=2;i61;i+) fibi = fibi-1+fibi-2; for(i=1;i61;i+) printf(F%d=%dt,i,fibi); return 0;2.迭代計算法#includeint f(int n);int main() int n; scanf(%d,&n); f(n);int f(int n) int i,f1=1,f2=1,f3; if(n=0) printf(輸入錯誤.n); else if(n=1|n=2) printf(1); else for(i=0;in-2;i+) f3=f1+f2; f2=f1; f1=f3; printf(%dn,f1); 3.公式法#include#includeint main() int n,f; printf(輸入n：); scanf(%d,&n); f = pow(1 + sqrt(5)/2.0),n)/sqrt(5) - pow(1 - sqrt(5)/2.0),n)/sqrt(5); printf(%d,f);教師評分實驗3 最近對問題實驗?zāi)康模?）設(shè)p1=(x1, y1)，p2=(x2, y2)，pn=(xn, yn)是平面上n個點構(gòu)成的集合S，設(shè)計算法找出集合S中距離最近的點對；（2）進一步掌握遞歸算法的設(shè)計思想以及遞歸程序的調(diào)試技術(shù)；（3）理解此觀點：分治和遞歸經(jīng)常同時應(yīng)用在算法設(shè)計中。預(yù)習(xí)內(nèi)容P113 4.6.1 最近對問題實驗內(nèi)容（1）用分治法求解最近對問題；（2）采用C/C+實現(xiàn)算法，利用計數(shù)法記錄基本語句的執(zhí)行次數(shù)；（3）分析算法的時間復(fù)雜性，并與蠻力法比較，得出結(jié)論。實驗結(jié)果（可續(xù)頁）教師評分實驗4 堆排序?qū)嶒災(zāi)康模?）實現(xiàn)堆的創(chuàng)建和堆排序；（2）理解變治法的思想。預(yù)習(xí)內(nèi)容P169 6.4 堆和堆排序?qū)嶒瀮?nèi)容（1）采用C/C+實現(xiàn)堆創(chuàng)建算法；（2）采用C/C+實現(xiàn)堆排序算法；（3）分析堆排序算法的時間復(fù)雜度，并與合并排序、快速排序比較，得出結(jié)論。實驗結(jié)果（可續(xù)頁）教師評分實驗5 霍納法則和二進制冪實驗?zāi)康模?）實現(xiàn)計算多項式的霍納法則；（2）實現(xiàn)從左至右和從右至左二進制冪算法；（3）理解變治法的思想。預(yù)習(xí)內(nèi)容P176 6.5 霍納法則和二進制冪實驗內(nèi)容（1）采用C/C+實現(xiàn)計算多項式的霍納法則；（2）采用C/C+實現(xiàn)計算an的從左至右和從右至左二進制冪算法；（3）分析霍納法則的時間復(fù)雜度，并與蠻力法比較，得出結(jié)論。實驗結(jié)果（可續(xù)頁）教師評分實驗6 字符串匹配問題實驗?zāi)康模?）給定一段文本，在該文本中查找并定位任意給定字符串；（2）深刻理解并掌握時空權(quán)衡的設(shè)計思想。預(yù)習(xí)內(nèi)容P194 7.2 字符串匹配中的輸入增強技術(shù)實驗內(nèi)容（1）采用C/C+實現(xiàn)BM算法的簡化算法：Horspool算法；（2）利用計數(shù)法記錄基本語句的執(zhí)行次數(shù)；（3）分析Horspool算法的時間復(fù)雜度，并與蠻力法比較，得出結(jié)論。實驗結(jié)果（可續(xù)頁）教師評分實驗7 Warshall算法和Floyd算法實驗?zāi)康模?）實現(xiàn)計算有向圖傳遞閉包的warshall算法；（2）利用Floyd算法計算圖的完全最短路徑；（3）深刻理解并掌握動態(tài)規(guī)劃法的設(shè)計思想。預(yù)習(xí)內(nèi)容P216 8.2 Warshall算法和Floyd算法實驗內(nèi)容（1）采用C/C+實現(xiàn)算法，利用計數(shù)法記錄基本語句的執(zhí)行次數(shù)；（2）采用大O符號分析2種算法的時間復(fù)雜性；（3）通過對2種算法的分析對比，找出的它們的相似處。實驗結(jié)果（可續(xù)頁）教師評分實驗8 最優(yōu)二叉查找樹實驗?zāi)康模?）實現(xiàn)最優(yōu)二叉查找樹的動態(tài)規(guī)劃算法；（2）深刻理解并掌握動態(tài)規(guī)劃法的設(shè)計思想。預(yù)習(xí)內(nèi)容P223 8.3 最優(yōu)二叉查找樹實驗內(nèi)容（1）采用C/C+實現(xiàn)最優(yōu)二叉查找樹的動態(tài)規(guī)劃算法；（2）根據(jù)實現(xiàn)的代碼給出至少含5個鍵的最優(yōu)二叉樹的主表和根表，并根據(jù)根表畫出最優(yōu)二叉查找樹；（3）分析算法的時間復(fù)雜度。實驗結(jié)果（可續(xù)頁）教師評分實驗9 Huffman編碼*實驗?zāi)康模?）設(shè)需要編碼的字符集為d1,d2, dn，出現(xiàn)的概率為w1,w2,wn,應(yīng)用Huffman樹構(gòu)造最短的變長編碼方案；（2）了解前綴編碼的概念，理解數(shù)據(jù)壓縮的基本方法；（3）掌握貪心法的設(shè)計思想并熟練運用。預(yù)習(xí)內(nèi)容P250 9.4 哈夫曼樹實驗內(nèi)容（1）設(shè)計貪心算法求解Huffman編碼方案；（2）采用C/C+實現(xiàn)算法；（3）分析算法的時間復(fù)雜性。實驗結(jié)果（可續(xù)頁）教師評分實驗10 求解非線性方程*實驗?zāi)康模?）采用平分法、試位法和牛頓法求解非線性方程；（2）理解近似算法求解某些問題的思路。預(yù)習(xí)內(nèi)容P342 12.4 解非線性方程的算法實驗內(nèi)容（1）采用C/C+實現(xiàn)求方程近似解的平分法、試位法和牛頓法；（2）分析三種算法的時間復(fù)雜度，比較三種算法的優(yōu)缺點。實驗結(jié)果（可續(xù)頁）教師評分實驗11 投資問題*實驗?zāi)康模?）有