最大公約數的三種算法 復雜度分析 時間計算

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