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

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