算法-最大公約數(shù)的三種算法

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告(20112012 學(xué)年 第 1 學(xué)期)課程名稱(chēng)：算法設(shè)計(jì)與分析開(kāi)課實(shí)驗(yàn)室：信自樓機(jī)房444 2011年10月12日年級(jí)、專(zhuān)業(yè)、班計(jì)科143學(xué)號(hào)201410405301姓名惠改彬成績(jī)實(shí)驗(yàn)項(xiàng)目名稱(chēng)求最大公約數(shù)指導(dǎo)教師吳晟教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理：該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ涸撏瑢W(xué)的實(shí)驗(yàn)是否達(dá)到要求： 實(shí)驗(yàn)報(bào)告是否規(guī)范： 實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄：A. 了解口B.基本了解口C.M、了解口A.強(qiáng) 口B.中等口C.差口A.達(dá)到口B.基本達(dá)到口C.未達(dá)到口A.規(guī)范口B.基本規(guī)范口C.不規(guī)范口A.詳細(xì)口B.一口C.沒(méi)有口教師簽名：年月日一、上機(jī)目的及內(nèi)容.上機(jī)內(nèi)容求兩個(gè)

2、自然數(shù) m和n的最大公約數(shù)。.上機(jī)目的(1)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)，實(shí)現(xiàn)課程間的平滑過(guò)渡；(2)掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗(yàn)分析方法；(3)理解這樣一個(gè)觀點(diǎn)：不同的算法能夠解決相同的問(wèn)題，這些算法的解題思路不同，復(fù)雜程度不 同，解題效率也不同。、實(shí)驗(yàn)原理及基本技術(shù)路線圖(方框原理圖或程序流程圖)(1)至少設(shè)計(jì)出三個(gè)版本的求最大公約數(shù)算法；(2)對(duì)所設(shè)計(jì)的算法采用大 O符號(hào)進(jìn)行時(shí)間復(fù)雜性分析；(3)上機(jī)實(shí)現(xiàn)算法，并用計(jì)數(shù)法和計(jì)時(shí)法分別測(cè)算算法的運(yùn)行時(shí)間;(4)通過(guò)分析對(duì)比，得出自己的結(jié)論。三、所用儀器、材料(設(shè)備名稱(chēng)、型號(hào)、規(guī)格等或使用軟件)1 臺(tái) PC 及 VISUAL C+6.0 軟件

3、四、實(shí)驗(yàn)方法、步驟(或：程序代碼或操作過(guò)程)實(shí)驗(yàn)采用三種方法求最大公約數(shù)源代碼#include#include #include #include #include int xiangchu(int m,int n);int xiangjian(int m,int n);int qiongju(int m,int n);int duanchu(int m,int n);void main()double t1,t2,t3,t4,t5,t6;int m,n;int i=0;double usetime1,usetime2,usetime3;time_t start, end;printf(請(qǐng)輸入

4、兩個(gè)數(shù):);scanf(%d%d,&m,&n);printf(相除法求最大公約數(shù)：dn,xiangchu(m,n);t1=clock();while(i1000000)(xiangchu(m,n);i+；)t2=clock();usetimel = t2-t1;printf(It takes %.f*10A(-6)n,usetime1);printf(相減法求最大公約數(shù)：dn,xiangjian(m,n);t3=clock();while(i1000000)(xiangchu(m,n);i+;)t4=clock();usetime2 = t4-t3;printf(It takes %.f*10

5、A(-6)n,usetime2);printf(短除法求最大公約數(shù):%dn,duanchu(m,n);t5=clock();while(in)m-=n;elsen-=m;)return n;)int duanchu(int m,int n)/ 短除法 (int i,factor=1;for(i=2;i=m & i=n;i+)(while (m%i=0 & n%i=0)(factor=factor*i;m=m/i;n=n/i;)return factor;五、實(shí)驗(yàn)過(guò)程原始記錄（測(cè)試數(shù)據(jù)、圖表、計(jì)算等）” ,D:Mkr05oft Vrsual Stu di MMy Project 認(rèn)篝法分忻2 Debug、算法分析2 ,匕乂 史fi青輸入兩金數(shù):12 25It takes 156*10心目減法求最大公約數(shù)豈11 takes 0*10AC-6恒除法求最大公約數(shù);1It takes 0*10AC-6ppess any key to continue六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時(shí)必須用計(jì)算紙或程序運(yùn)行結(jié)果、改進(jìn)、收獲）該次實(shí)驗(yàn)讓我知道了求最大公約的不同種算法，除了以上三種，還有分解質(zhì)因法和連續(xù)整數(shù)檢測(cè)法