最大公約數(shù)的三種算法 復(fù)雜度分析 時間計算

最大公約數(shù)的三種算法復(fù)雜度分析時間計算最大公約數(shù)的三種算法復(fù)雜度分析時間計算最大公約數(shù)的三種算法復(fù)雜度分析時間計算最大公約數(shù)的三種算法復(fù)雜度分析時間計算編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（2011—2012學(xué)年第1學(xué)期）課程名稱：算法設(shè)計與分析開課實驗室：信自樓機(jī)房4442011年10月12日年級、專業(yè)、班計科092學(xué)號5214姓名徐興繁成績實驗項目名稱求最大公約數(shù)指導(dǎo)教師吳晟教師評語該同學(xué)是否了解實驗原理： A.了解□ B.基本了解□ C.不了解□該同學(xué)的實驗?zāi)芰Γ? A.強(qiáng)□ B.中等□ C.差□該同學(xué)的實驗是否達(dá)到要求： A.達(dá)到□ B.基本達(dá)到□ C.未達(dá)到□實驗報告是否規(guī)范： A.規(guī)范□ B.基本規(guī)范□ C.不規(guī)范□實驗過程是否詳細(xì)記錄： A.詳細(xì)□ B.一般□ C.沒有□教師簽名：年月日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容求兩個自然數(shù)m和n的最大公約數(shù)。2.上機(jī)目的（1）復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識，實現(xiàn)課程間的平滑過渡；（2）掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復(fù)雜程度不同，解題效率也不同。二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）至少設(shè)計出三個版本的求最大公約數(shù)算法；（2）對所設(shè)計的算法采用大O符號進(jìn)行時間復(fù)雜性分析；（3）上機(jī)實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間；（4）通過分析對比，得出自己的結(jié)論。三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）1臺PC及VISUALC++軟件四、實驗方法、步驟（或：程序代碼或操作過程） 實驗采用三種方法求最大公約數(shù)1、連續(xù)整數(shù)檢測法。2、歐幾里得算法3、分解質(zhì)因數(shù)算法根據(jù)實現(xiàn)提示寫代碼并分析代碼的時間復(fù)雜度：方法一：intf1(intm,intn){ intt; if(m>n)t=n; elset=m; while(t) { if(m%t==0&&n%t==0)break; elset=t-1; } returnt;}根據(jù)代碼考慮最壞情況他們的最大公約數(shù)是1，循環(huán)做了t-1次，最好情況是只做了1次，可以得出O（n）=n/2;方法二：intf2(intm,intn){ intr; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } returnn;}根據(jù)代碼輾轉(zhuǎn)相除得到歐幾里得的O(n)=logn方法三：intf3(intm,intn){ inti=2,j=0,h=0; inta[N],b[N],c[N]; while(i<n) { if(n%i==0) { j++; a[j]=i; n=n/i; } elsei++; } j++; a[j]=n; i=1; intu; u=j; while(i<=j) { *10^(-6)豪秒\n",usetime); i=0;start=clock();while(i<1000000) { f2(m,n); i++; } finish=clock(); usetime=finish-start; printf("方法二用時%.f*10^(-6)豪秒\n",usetime); i=0;start=clock();while(i<1000000) { f3(m,n); i++; } finish=clock(); usetime=finish-start; printf("方法三用時%.f*10^(-6)豪秒\n",usetime);}五、實驗過程原始記錄(測試數(shù)據(jù)、圖表、計算等)請給出各個操作步驟的截圖和說明；三種算法得到結(jié)果驗證結(jié)果：計數(shù)器：我想到的是做一次循環(huán)就加一計算算法運行時間結(jié)果：在計算時間過程中因為計算機(jī)的運算速度很快，所以我利用了循環(huán)把時間精確得到10-6毫秒六、實驗結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時必須用計算紙或程序運行結(jié)果、改進(jìn)、收獲）請結(jié)合實驗的結(jié)果分析算法原理；在實驗中遇到了些什么問題，如何解決；有什么收獲等；在本次實驗中代碼是獨自完成的，一開始我感覺這個代碼最多半小時就可以完成，但是第三個算法的時候我分析了好久才寫出來，在計算三種方法運行時間的時候，我一開始只精確到毫秒（ms），計算結(jié)果都是零，后面我寫了一個循環(huán)調(diào)試才發(fā)現(xiàn)是我的精確度還在不夠，所以我想到了計算算法執(zhí)行了1000000次之后所用的時間，然后再求平均每次執(zhí)行的時間。結(jié)果分析：從前面的復(fù)雜度O(n)的出歐幾里得算法的是最優(yōu)算法，連續(xù)整除法其次，最復(fù)雜的是分解質(zhì)因數(shù)算法，再從代碼運行的計數(shù)器和計算的時間來看結(jié)果恰好和前面的復(fù)雜度得到的結(jié)果一致，所以的出結(jié)論：歐幾里得算法最優(yōu)。從這次實驗的結(jié)果我了解到了算法的優(yōu)與劣的差別，雖然得到的是同樣的結(jié)果，但是需要的時間和