算法分析與設計課程設計實驗報告求最大公約數實驗報告實驗（含源程序）

1、昆明理工大學信息工程與自動化學院學生實驗報告（ 2011 2012 學年 第 1 學期 ）課程名稱：算法分析與設計 開課實驗室：信自樓機房445 2011 年10月 12日年級、專業(yè)、班計科092學號200910405201姓名劉召成績實驗項目名稱求最大公約數指導教師 張晶教師評語該同學是否了解實驗原理：a.了解b.基本了解c.不了解該同學的實驗能力：a.強 b.中等 c.差 該同學的實驗是否達到要求：a.達到b.基本達到c.未達到實驗報告是否規(guī)范：a.規(guī)范b.基本規(guī)范c.不規(guī)范實驗過程是否詳細記錄：a.詳細b.一般 c.沒有 教師簽名： 年 月 日一、上機目的及內容上機內容求兩個自然數m和n

2、的最大公約數。上機目的（1）復習數據結構課程的相關知識，實現課程間的平滑過渡；（2）掌握并應用算法的數學分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復雜程度不同，解題效率也不同。二、實驗原理及基本技術路線圖（方框原理圖或程序流程圖）（1）至少設計出三個版本的求最大公約數算法；所設計的3個版本分別是：連續(xù)整數檢測算法、歐幾里得算法和分解質因數算法。這3 個算法的流程圖分別如下所示：（2） 對所設計的算法采用大o符號進行時間復雜性分析；在連續(xù)整數檢測算法中，由于其最壞的情況是m與n除以t均不為0，直到t接近于0為止，此時所需時間接近m和n的較小

3、者的值；在歐幾里得算法中，最壞的情況是每次所得的都比n略小一點；但此時，它的數據還是以n倍遞減；在分解質因數算法中，關鍵是分解質因數的時間復雜度和將所得質因數相乘合并的時間復雜度；在對m和n分解質因數時，最壞的情況是m和n的質因數都還是m和n；分解m和n用的時間復雜度是： ；對于所得到的質因數求出它們的公共質因數時最壞的情況是有較多的質因數，且兩組質因數之間沒有公共質因數，此時時間復雜度是兩組質因數數目之平方；然而，對于所得到的質因數數量極為有限，因此對于最壞情況下的m和n的分解質因數，所得到的質因數的數量就更少，此時可以把對于質因數合并得公共質因數的時間復雜度忽略不計；最壞的時間復雜度是：（

4、3） 上機實現算法，并用計數法和計時法分別測算算法的運行時間；在我的電腦測試所得到的部分數據表格：連續(xù)整數檢測時間（秒）歐幾里得時間（秒）分解質因數時間（秒）最大公約數673153380921974453701298.50032162139311656621917842814657010.9200.0011302111111177779777773284650.09900.016111111111777771113684845470.93400.15423137137137137133544513714.26708.8731234137137317311234567891.53504.0421

5、346546133132197454137911.45300.0616545874874654687874345354548454.199056.386287987465468998654658480.821013.7182545487434354313213556.937048.904154446846464645365534546350.7700.032564646546546546546446132544550.21200.0051544646846553356353253.932024.06155154654654235112436428.01303.86925546464664654

6、64687313212135143.06200.23135454546363369321329432738.99600.1323平均使用時間19.040625010.03更多測試數據請參見附錄：數據測試清單！也可運行程序： 兩個正整數最大公約數求解簡易系統(32位).exe自己進行數據測試。（4） 通過分析對比，得出自己的結論。通過以上可以得知，歐幾里得算法的性能最優(yōu)，而分解質因數算法和連續(xù)整數檢測算法的效率差不多，但是，當兩個數據相差很大時，連續(xù)整數檢測算法可能會比分解質因數算法占優(yōu)勢；當兩個數所得到的最大質因數都較小時，分解質因數算法可能比連續(xù)整數檢測算法占優(yōu)勢。三、所用儀器、材料（設備名

7、稱、型號、規(guī)格等或使用軟件）1臺pc及visual studio 2005軟件四、實驗方法、步驟（或：程序代碼或操作過程）/ 兩個正整數最大公約數求解簡易系統.cpp : 定義控制臺應用程序的入口點。/*該系統是為了計算兩個正整數的最大公約數*該系統是在visual studio 2005環(huán)境下編輯的，并通過visual studio 2005環(huán)境下編譯與運行*該版本使用了boost函數庫中的timer.hpp庫函數，關于boost函數庫可以參考網絡上的boost社區(qū)*該程序制作人劉召*該系統創(chuàng)建時間是2011年10月12日*/#include stdafx.h#include#include

8、#include#include#include#include using namespace std;using namespace boost;long long smallernumber(long long i,long long j)return ij?i:j;long long cheking(long long m,long long n,long long t)if(m%t)-t;return cheking(m,n,t);if(n%t)-t;return cheking(m,n,t);return t;void gcdintegerchecking(long long m,

9、long long n,long long *p)long long t=smallernumber(n,m); *p=cheking(m,n,t);void gcdoujilide(long long m,long long n,long long *p)long long t=m,s=n;long long r=m%n;while(r!=0)m=n;n=r;r=m%n;*p=n;void zhiyinshupanduan(long long i,list& list)long long x=(long long)(i/2),j=i;for(long long g=2;g=x;g+)whil

10、e(i%g=0)list.push_back(g);i/=g;x=(long long)(i/2);if(i!=1)list.push_back(i);void gcdfenjiezhiyinshu(long long m,long long n,long long *p,list*list1,list*list2,list*plist)long long count=1;zhiyinshupanduan(m,*list1);zhiyinshupanduan(n,*list2);list:iterator it,rt,yt,gt=(*list2).begin();for(it=(*list1)

11、.begin();it!=(*list1).end();it+)long long a=1,b=1;yt=it;yt+;while(yt!=(*list1).end()&*yt=*it)yt+;a+;it+;for(rt=gt;rt!=(*list2).end();rt+)if(*it=*rt)gt=rt;gt+;while(gt!=(*list2).end()&*gt=*rt)gt+;b+;for(long long h=0;hpush_back(*it);break;*p=count;void menu1()coutendlt1用連續(xù)整數檢測算法進行運算!t;cout2用歐幾里得算法進行運

12、算!endl;coutt3用分解質因數算法進行運算!t;cout4結束對這兩個數的運算！endl;cout$：flush;void input(long long& m,long long& n)coutendl$：;cinm;cout$：;cinn;void menu()coutendlt1進行下一對整數最大公約數運算！t;cout2退出本系統！endl;cout$：flush;void welcome()coutnttt歡迎使用求解兩個正整數最大公約數的簡易系統nendl;couttttt學 校：昆明理工大學endl;couttttt學 院：信息工程與自動化學院endl;couttttt專

13、 業(yè)：計算機科學與技術endl;couttttt指導老師：張晶endl;couttttt制作人：劉召endl;couttttt學 號：endl;coutttttqq 郵箱：endl;void exitsystem()coutn你已經成功退出本系統！n謝謝你的使用！再見！endl;void showzhiyinshu(long long j,list&list)if(list.size()coutendl整數j共有l(wèi)ist.size()個質數，它們分別是：endl;elsecoutendl整數j沒有質數！endl;list:iterator it;for(it=list.begin();it!=

14、list.end();it+)cout*itt;coutendl;list.clear();void showcommonnumber(long long m,long long n,list&plist)if(plist.size()coutendl整數m和n共有plist.size()個公共質數，它們分別是：endl;elsecoutendl整數m和n沒有公共質數！endl;list:iterator it;for(it=plist.begin();it!=plist.end();it+)cout*itt;coutk;coutendl;list list1,list2,plist;syst

15、em(color 2b);while(k0&k4)switch(k)case 1:timecountor.restart();gcdintegerchecking(m,n,&p);cout連續(xù)整數檢測算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;cout經連續(xù)整數檢測算法運算所得m和n的最大公約數是：pendl;break;case 2:timecountor.restart();gcdoujilide(m,n,&p);cout歐幾里得算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;cout經歐幾里得算法運算

16、所得m和n的最大公約數是：pendl;break;case 3:timecountor.restart();gcdfenjiezhiyinshu(m,n,&p,&list1,&list2,&plist);cout分解質因數算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;showzhiyinshu(m,list1);showzhiyinshu(n,list2);showcommonnumber(m,n,plist);cout經分解質因數算法運算所得m和n的最大公約數是：pk;coutk;coutn你本次用時共time.elapsed()秒$：346546

17、1331321請輸入你所要運算的第二個整數$：974541379 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：11.453秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得3465461331321和974541379的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得3465461331321和9745413

18、79的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：0.06秒(最高精確度毫秒級)整數3465461331321共有4個質數，它們分別是：3 11 18149 5786213整數974541379共有3個質數，它們分別是：7 43 3237679整數3465461331321和974541379沒有公共質數！經分解質因數算法運算所得3465461331321和974541379的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解

19、質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：6731533809請輸入你所要運算的第二個整數$：219744537012 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：98.5秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得6731533809和219744537012的最大公約數是：3216213 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算!

20、 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得6731533809和219744537012的最大公約數是：3216213 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：0秒(最高精確度毫秒級)整數6731533809共有11個質數，它們分別是：3 3 3 7 7 7 11 13 13 1723整數219744537012共有13個質數，它們分別是：2 2 3 3 3 7 7 11

21、13 1719 29 31整數6731533809和219744537012共有8個公共質數，它們分別是：3 3 3 7 7 11 13 17經分解質因數算法運算所得6731533809和219744537012的最大公約數是：3216213 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：931165662請輸入你所要運算的第二個整數$：19178428146570 1用連續(xù)整數檢測算法進行運算! 2用歐幾

22、里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：10.92秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得931165662和19178428146570的最大公約數是：1302 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得931165662和19178428146570的最大公約數是：1302 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解

23、質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：0.001秒(最高精確度毫秒級)整數931165662共有7個質數，它們分別是：2 3 7 31 73 97 101整數19178428146570共有10個質數，它們分別是：2 3 3 5 7 11 11 31 919 8831整數931165662和19178428146570共有4個公共質數，它們分別是：2 3 7 31經分解質因數算法運算所得931165662和19178428146570的最大公約數是：1302 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行

24、運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：1111111777797777請輸入你所要運算的第二個整數$：7328465 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：0.099秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得1111111777797777和7328465的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法

25、進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得1111111777797777和7328465的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：0.016秒(最高精確度毫秒級)整數1111111777797777共有6個質數，它們分別是：3 3 7 223 93251 848123整數7328465共有2個質數，它們分別是：5 1465693整數1111111777797777和7328

26、465沒有公共質數！經分解質因數算法運算所得1111111777797777和7328465的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：11111111777771113請輸入你所要運算的第二個整數$：68484547 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：0.9

27、34秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得11111111777771113和68484547的最大公約數是：23 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得11111111777771113和68484547的最大公約數是：23 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：0.154秒(最高精確度毫秒級)整數

28、11111111777771113共有4個質數，它們分別是：23 1033 20233 23113679整數68484547共有3個質數，它們分別是：23 79 37691整數11111111777771113和68484547共有1個公共質數，它們分別是：23經分解質因數算法運算所得11111111777771113和68484547的最大公約數是：23 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：13

29、713713713713請輸入你所要運算的第二個整數$：354451371 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：4.267秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得13713713713713和354451371的最大公約數是：3 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得13713713713713和3

30、54451371的最大公約數是：3 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：8.87秒(最高精確度毫秒級)整數13713713713713共有4個質數，它們分別是：3 13 263 1337010209整數354451371共有3個質數，它們分別是：3 5419 21803整數13713713713713和354451371共有1個公共質數，它們分別是：3經分解質因數算法運算所得13713713713713和354451371的最大公約數是：3 1用連續(xù)整數檢測算法進行運算!

31、 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：123413713731731請輸入你所要運算的第二個整數$：123456789 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：1.535秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得123413713731731和123456789的最大公約數是：1 1用連續(xù)整數檢測算法進

32、行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得123413713731731和123456789的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：4.042秒(最高精確度毫秒級)整數123413713731731共有2個質數，它們分別是：202343 609923317整數123456789共有4個質數，它們分別是：3 3 3607

33、 3803整數123413713731731和123456789沒有公共質數！經分解質因數算法運算所得123413713731731和123456789的最大公約數是：1 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：6545874874654687874請輸入你所要運算的第二個整數$：3453545484 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這

34、兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：54.199秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得6545874874654687874和3453545484的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得6545874874654687874和3453545484的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！

35、請輸入你的選擇$：3分解質因數算法所用時間為：56.386秒(最高精確度毫秒級)整數6545874874654687874共有6個質數，它們分別是：2 23 37 41 11657 8047064651整數3453545484共有7個質數，它們分別是：2 2 3 3 3 3 10659091整數6545874874654687874和3453545484共有1個公共質數，它們分別是：2經分解質因數算法運算所得6545874874654687874和3453545484的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的

36、運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本系統！請輸入你的選擇$：1請輸入你所要運算的第一個整數$：87987465468998請輸入你所要運算的第二個整數$：65465848 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：1連續(xù)整數檢測算法所用時間為：0.821秒(最高精確度毫秒級)經連續(xù)整數檢測算法運算所得87987465468998和65465848的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的

37、運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經歐幾里得算法運算所得87987465468998和65465848的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：3分解質因數算法所用時間為：13.718秒(最高精確度毫秒級)整數87987465468998共有4個質數，它們分別是：2 43 503 2034016031整數65465848共有6個質數，它們分別是：2 2 2 7 41 28513整數87987465468998和65465848共有1個公共質數，它們分別是：2經分解質因數算法運算所得87987465468998和65465848的最大公約數是：2 1用連續(xù)整數檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質因數算法進行運算! 4結束對這兩個數的運算！請輸入你的選擇$：4 1進行下一對整數最大公約數運算！ 2退出本