參證材料--算法設計實驗標準版

1、.四 川 理 工 學 院課 程 設 計 書 學院 理學院 專業(yè) 信息與計算科學09級2班 題目 求最大公約數 學生 楊雪娥 09071030238 譚 蕓 09071030236 楊玉俊 09071030224 甄 坤 09071030231 楊宏飛 09071030223 王 晨 09071030217 呂俊村 09071030215 實驗項目求最大公約數一、 實驗題目鍵盤輸入兩個任意的自然數m和n，編出一種方案求出m和n的最大公約數二、 實驗目的（1） 復習數據結構課程的相關知識，實現課程間的平滑過渡；（2） 掌握并應用算法的數學分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解

2、決相同的問題，這些算法的解題思路不同，復雜程度不同，解題效率不同。三、 實驗要求( 1 ) 至少設計出3個版本的求最大公約數的算法；( 2 ) 對所設計的算法采用大O符號進行時間復雜性分析；( 3 ) 上機實現算法，并用計數法和計時法分別測算算法的運行時間；( 4 ) 通過分析對比，得出自己的結論。四、問題分析設m和n是兩個自然數，m和n的最大公約數記為gcd(m,n),是能夠同時被m和n整除的最大整數。對此問題我們采取三種方案進行求解：1.第一種方案（1）連續(xù)整數檢測偽代碼：1. t=minm,n;2. m除以t，如果余數為0，則執(zhí)行步驟3，否則，執(zhí)行第四步；3. n除以t，如果余數為0，返

3、回t的值作為結果，否則，執(zhí)行第四步；4. t=t-1,轉第四步；例如，要計算gcd(66,12)，首先令t=12，因為66除以12余數不為0，將t減1，而12除以11余數不為0，再將t減1，重復上述過程，直到t=6，此時12除以6的余數為0并且66除以6的余數為0，則gcd(66,12)=6。2.第二種方案（1）歐幾里得算法偽代碼：1. r=m%n；2. 循環(huán)直到r=0；2.1 m=n；2.2 n=r;2.3 r=m%n；3. 輸出 n；例如，要計算gcd(66,12)，因為66除以12的余數為6，再將12除以6，余數為0，則gcd(66,12)=6。3.第三種方案（1）分解質因數偽代碼1.

4、將m分解質因數；2. 將n分解質因數；3. 提取m和n中的公共質因數；4. 將m和n中的公共質因數相乘，乘積作為結果輸出；例如，要計算gcd(66,12), 首先分解質因數66=2*3*11,12=2*2*3，然后提取二者的公共質因數2*3，則gcd(66,12)=2*3=6。五、程序流程圖連續(xù)整數檢測算法流程圖如圖1所示歐幾里得算法流程圖如圖2所示六、源程序連續(xù)整數檢測：#include int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;return t; void mai

5、n() int a,b; coutab; couta和b的最大公約數是： ; coutf1(a,b)endl;歐幾里得算法：#includeint f2(int m,int n)int r;r=m%n;while(r!=0)m=n; n=r; r=m%n;return n;void main() int a,b; coutab; couta和b的最大公約數是： ; coutf2(a,b)endl;分解質因數法：#includeint f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;else

6、i+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+;i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;void main() int a,b; coutab; couta和b的最大公約數是： ; coutCommonFactor

7、(a,b)n)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;return t;根據代碼考慮最壞情況他們的最大公約數是1，循環(huán)做了t-1次，最好情況是只做了1次，可以得出O（n）=n/2;（2） 歐幾里得算法的時間復雜度 int f2(int m,int n)int r;r=m%n;while(r!=0)m=n; n=r; r=m%n;return n;根據代碼輾轉相除得到歐幾里得的O(n)= log n（3） 分解質因數法的時間復雜度 int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;w

8、hile(in)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(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;根據代碼分解質因子算法O(n)=n2+n/2九、算法計

9、時和計數分析為了計算每種算法運行的次數所用的時間，將代碼稍加改動添加代碼如下：其中計數器采用的是沒做一次循環(huán)就加1；計時器是記住開始時間和結束時間，用結束時間減開始時間。#includeiostream.h#includestdio.h#includestdlib.h#includetime.h#define N 100int w,w2,w3;/用于計數int f1(int m,int n)int t;if(mn)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;

10、r=m%n;w2=1;while(r!=0)m=n; n=r; r=m%n;w2+;return n;int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)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(im)if(m%i=0)j+;bj=i;m=m/i;w3+;else i+;w3+;j+;bj=m;i=1;while(i=j) /pri

11、ntf(%d ,bi); i+; w3+;int k=1;for(i=1;i=j;i+)for(k=1;k1)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(%d%d,&m,&n);int k;k=f1(m,n); printf( 方法一最大公約數為： %dn,k);k=f2(m,n);printf( 方法二最大公約數為： %dn,k);k=f3(m,n);printf( 方法三最大公約數為： %dn,k);printf(n-n)

12、;printf(n計數器顯示結果：nnn); printf(方法一： %d n,w2); printf(方法二： %d n,w); printf(方法三： %d n,w3);printf(n-n);float a,i; clock_t start,finish; double usetime;i=0; start= clock(); while (i1000000)f1(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法一用時%.f*10(-6) 豪秒n, usetime);i=0; start= clock(); while (

13、i1000000)f2(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法二用時%.f*10(-6) 豪秒n, usetime); i=0; start= clock(); while (i1000000)f3(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法三用時%.f*10(-6) 豪秒n, usetime); 十、實驗過程原始記錄( 測試數據、圖表、計算等)三種算法得到結果驗證結果：計數器：我想到的是做一次循環(huán)就加一計算算法運行時間結果：在計算時間過程中因為計

14、算機的運算速度很快，所以我利用了循環(huán)把時間精確得到10-6毫秒十一、實驗結果、分析和結論（誤差分析與數據處理、成果總結等。其中，繪制曲線圖時必須用計算紙或程序運行結果、改進、收獲）在本次實驗中代碼是我們組共同完成的，一開始我們感覺這個代碼最多半小時就可以完成，但是第三個算法的時候我們分析了好久才寫出來，在計算三種方法運行時間的時候，我們一開始只精確到毫秒（ms），計算結果都是零，后面我們寫了一個循環(huán)調試才發(fā)現是我們的精確度還在不夠，所以我們想到了計算算法執(zhí)行了1000000次之后所用的時間，然后再求平均每次執(zhí)行的時間。結果分析：從前面的復雜度O(n)的出歐幾里得算法的是最優(yōu)算法，連續(xù)整除法其次，最復雜的是分解質因數算法，再從代碼運行的計數器和計算的時間來看結果恰好和前面的復雜度得到的結果一致，所以的出結論：歐幾里得算法