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

1、理工大學信息工程與自動化學院學生實驗報告（2011 2012學年第 1 學期）課程名稱：算法設計與分析開課實驗室：信自樓機房444 2011年10月12日年級、專業(yè)、班計科092學號4徐興繁成績實驗項目名稱求最大公約數(shù)指導教師吳晟教該同學是否了解實驗原理：A. 了解口B.基本了解口C.不了解口師該同學的實驗能力：A.強B.中等C.差該冋學的實驗是否達到要求：A.達到口B.基本達到口C.未達到口評實驗報告是否規(guī)：A.規(guī)口B.基本規(guī)口C.不規(guī)口實驗過程是否詳細記錄：A.詳細口B. 一般C.沒有口語教師簽名：年月日一、上機目的及容1. 上機容求兩個自然數(shù) m和n的最大公約數(shù)。2. 上機目的（1）復習

2、數(shù)據(jù)結(jié)構課程的相關知識，實現(xiàn)課程間的平滑過渡；（2）掌握并應用算法的數(shù)學分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復雜程度不 同，解題效率也不同。、實驗原理及基本技術路線圖（方框原理圖或程序流程圖）（1）至少設計出三個版本的求最大公約數(shù)算法；（2）對所設計的算法采用大 0符號進行時間復雜性分析；（3）上機實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間;（4）通過分析對比，得出自己的結(jié)論。三、所用儀器、材料（設備名稱、型號、規(guī)格等或使用軟件）1 臺 PC 及 VISUAL C+6.0 軟件四、實驗方法、步驟（或：程序代碼或操作過程）實驗

3、采用三種方法求最大公約數(shù)1、連續(xù)整數(shù)檢測法。2、歐幾里得算法3、分解質(zhì)因數(shù)算法根據(jù)實現(xiàn)提示寫代碼并分析代碼的時間復雜度：方法一：int f1(int m,int n) int t; if(m>n)t=n; else t=m; while(t) if(m%t=0&&n%t=0)break; else t=t-1;return t;根據(jù)代碼考慮最壞情況他們的最大公約數(shù)是1，循環(huán)做了 t-1 次，最好情況是只做了 1 次，可以得出O( n)=n/2;方法二： int f2(int m,int n)int r;r=m%n;while(r!=0)m=n;n=r;r=m%n;retu

4、rn n;根據(jù)代碼輾轉(zhuǎn)相除得到歐幾里得的 O(n)= log n方法三：int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(i<n)if(n%i=0)j+;aj=i;n=n/i;else i+;j+;aj=n;i=1;int u;u=j;while(i<=j)/printf("%d ",ai);i+;i=2;j=0;while(i<m)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i<=j)/printf("%d ",bi)

5、;i+;int k=1;for(i=1;i<=j;i+)for(k=1;k<=u;k+)if(bi=ak)h+; ch=ak;/printf("%d ",ch); ak=ak+1;break;k=1;while(h>1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;根據(jù)代碼分解質(zhì)因子算法 O(n)=n 2+n/2 為了計算每種算法運行的次數(shù)所用的時間，我將代碼稍加改動添加代碼如下 其中計數(shù)器采用的是沒做一次循環(huán)就加1；計時器是記住開始時間和結(jié)束時間，用結(jié)束時間減開始時間。#include&qu

6、ot;iostream.h"#include"stdio.h"#include"stdlib.h"#include"time.h"#define N 100int w,w2,w3;/ 用于計數(shù)int f1(int m,int n)int t;if(m>n)t=n;else t=m;while(t)if(m%t=0&&n%t=0)break;else t=t-1;w+;return t;int f2(int m,int n)int r;r=m%n;w2=1;while(r!=0)m=n;n=r;r=m%n

7、;w2+;return n;int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(i<n)if(n%i=0) j+; aj=i; n=n/i; w3+;else i+; w3+;j+;aj=n;i=1;int u;u=j;while(i<=j)/printf("%d ",ai);i+;w3+;/printf("n");i=2;j=0;while(i<m)if(m%i=0) j+; bj=i; m=m/i; w3+;else i+; w3+;j+;bj=m;i=1;while(i<

8、;=j)/printf("%d ",bi); i+;w3+;int k=1;for(i=1;i<=j;i+)for(k=1;k<=u;k+)if(bi=ak)w3+;h+;ch=ak;/printf("n%d ",ch); ak=ak+1;break;k=1;while(h>1) k=k*ch*ch-1; h=h-2; w3+; if(h=1) k=k*c1; return k;else return k;int main(void)int m,n;printf(" 請輸入 m,n :n"); scanf("

9、;%d%d",&m,&n);int k;k=f1(m,n);printf("方法一最大公約數(shù)為： %dn",k);k=f2(m,n);printf("方法二最大公約數(shù)為： %dn",k);k=f3(m,n);printf(" 方法三最大公約數(shù)為： %dn",k); printf("nn");printf("n 計數(shù)器顯示結(jié)果： nnn");printf("方法一：%d n",w2); printf(" 方法二： %d n",w);

10、printf(" 方法三：%d n",w3);printf("nn");float a,i;clock_t start,finish;double usetime;i=0;start= clock(); while (i<1000000) f1(m,n); i+; finish=clock(); usetime= finish-start;printf("方法一用時 %.f*10A(-6)豪秒n",i=0;start= clock();while (i<1000000)f2(m,n); i+; finish=clock()

11、;usetime= finish-start;printf("方法二用時 %.f*10A(-6) 豪秒n",i=0;start= clock();while (i<1000000)f3(m,n); i+; finish=clock();usetime= finish-start;printf("方法三用時 %.f*10A(-6) 豪秒n",usetime);usetime);usetime);五、實驗過程原始記錄（測試數(shù)據(jù)、圖表、計算等） 請給出各個操作步驟的截圖和說明；三種算法得到結(jié)果驗證結(jié)果：c、*D:、編程D©by求星大公昨數(shù)1-

12、eze請輸入:66 12方迭一曇大公約數(shù)為：* 方住二臺大公約數(shù)為：£ 分陳質(zhì)因子：2 2 32 3 11 召共質(zhì)因子2 3方法三最大公約數(shù)為=6計數(shù)器：我想到的是做一次循環(huán)就加一計算算法運行時間結(jié)果：在計算時間過程中因為計算機的運算速度很快，所以我利用 了循環(huán)把時間精確得到10-6毫秒rD: '編程VJebu就最大公均數(shù)1- exe*>1九九九 約釣約 :背公公 n大大大 無一二三 請方方方2計數(shù)器顯示結(jié)果:62一二三 方方方法三：23266*10<-6>63*L0AC-6>50B*10A<-6>六、實驗結(jié)果、分析和結(jié)論(誤差分析與數(shù)據(jù)處

13、理、成果總結(jié)等。其中，繪制曲線圖時必 須用計算紙或程序運行結(jié)果、改進、收獲)請結(jié)合實驗的結(jié)果分析算法原理；在實驗中遇到了些什么問題，如何解決；有什么收獲等；在本次實驗中代碼是獨自完成的，一開始我感覺這個代碼最多半小時就可以完成，但是第三個算法的時候我分析了好久才寫出來，在計算三種方法運行時間的時候，我一開始只精確到毫秒(ms)，計算結(jié)果都是零，后面我寫了一個循環(huán)調(diào)試才發(fā)現(xiàn)是我的精確度還在不夠，所以我想到了計算算法執(zhí)行了 1000000次之后所用的時間，然后再求平均每次執(zhí)行的時間。結(jié)果分析：從前面的復雜度O(n)的出歐幾里得算法的是最優(yōu)算法，連續(xù)整除法其次，最復雜的是分解質(zhì)因數(shù)算法，再從代碼運行的計數(shù)器和計算的時間來