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

希望對(duì)大家有所幫助，多謝您的瀏覽！昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（2011—2012學(xué)年第1學(xué)期）課程名稱：算法設(shè)計(jì)與分析開(kāi)課實(shí)驗(yàn)室：信自樓機(jī)房4442011年10月12日年級(jí)、專業(yè)、班計(jì)科092學(xué)號(hào)200910405214姓名徐興繁成績(jī)實(shí)驗(yàn)項(xiàng)目名稱求最大公約數(shù)指導(dǎo)教師吳晟教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理： A.了解口 B.基本了解口C.不了解口該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ?A.強(qiáng)口 B.中等 口 C.差 口該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求：A.達(dá)到口 B.基本達(dá)到口C.未達(dá)到口實(shí)驗(yàn)報(bào)告是否規(guī)范： A.規(guī)范口 B.基本規(guī)范口C.不規(guī)范口實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄： A.詳細(xì)口 B.一般口 C.沒(méi)有口教師簽名：年 月 日一、上機(jī)目的及內(nèi)容上機(jī)內(nèi)容求兩個(gè)自然數(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ì)的算法采用大0符號(hào)進(jìn)行時(shí)間復(fù)雜性分析；（3） 上機(jī)實(shí)現(xiàn)算法，并用計(jì)數(shù)法和計(jì)時(shí)法分別測(cè)算算法的運(yùn)行時(shí)間（4） 通過(guò)分析對(duì)比，得出自己的結(jié)論。三、 所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1臺(tái)PC及VISUALC++6.0軟件四、 實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過(guò)程）希望對(duì)大家有所幫助，多謝您的瀏覽！實(shí)驗(yàn)采用三種方法求最大公約數(shù)1、連續(xù)整數(shù)檢測(cè)法。2、歐幾里得算法3、分解質(zhì)因數(shù)算法根據(jù)實(shí)現(xiàn)提示寫(xiě)代碼并分析代碼的時(shí)間復(fù)雜度：方法一：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;}根據(jù)代碼考慮最壞情況他們的最大公約數(shù)是1,循環(huán)做了t-1次，最好情況是只做了1次，可以得出0(n)=n/2;方法二：intf2(intm,intn){intr;r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}根據(jù)代碼輾轉(zhuǎn)相除得到歐幾里得的0(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){//printf("%d",a[i]);i++;}i=2;j=0;while(i<m){if(m%i==0){j++;b[j]=i;m=m/i;}elsei++;}j++;b[j]=m;i=1;while(i<=j){//printf("%d",b[i]);i++;}intk=1;for(i=1;i<=j;i++){for(k=1;k<=u;k++){if(b[i]==a[k]){h++;c[h]=a[k];//printf("%d",c[h]);a[k]=a[k+1];break;}}}k=1;while(h>1){k=k*c[h]*c[h-1];h=h-2;}if(h==1){k=k*c[1];returnk;}elsereturnk;}根據(jù)代碼分解質(zhì)因子算法0(n)=n2+n/2為了計(jì)算每種算法運(yùn)行的次數(shù)所用的時(shí)間，我將代碼稍加改動(dòng)添加代碼如下其中計(jì)數(shù)器采用的是沒(méi)做一次循環(huán)就加1；計(jì)時(shí)器是記住開(kāi)始時(shí)間和結(jié)束時(shí)間，用結(jié)束時(shí)間減開(kāi)始時(shí)間。#include"iostream.h"#include"stdio.h"#include"stdlib.h"#include"time.h"#defineN100intw,w2,w3;//用于計(jì)數(shù)intf1(intm,intn){intt;if(m>n)t=n;elset=m;while(t){if(m%t==0&&n%t==0)break;elset=t-1;w++;}returnt;}intf2(intm,intn){intr;r=m%n;w2=1;while(r!=0){m=n;n=r;r=m%n;w2++;returnn;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;w3++;}else{i++;w3++;}}j++;a[j]=n;i=1;intu;u=j;while(i<=j){//printf("%d",a[i]);i++;w3++;}//printf("\n");i=2;j=0;while(i<m){if(m%i==0){j++;b[j]=i;m=m/i;w3++;elsew3++;}}j++;b[j]=m;i=1;while(i<=j){//printf("%d",b[i]);i++;w3++;}intk=1;for(i=1;i<=j;i++){for(k=1;k<=u;k++){if(b[i]==a[k]){w3++;希望對(duì)大家有所幫助，多謝您的瀏覽！h++;c[h]=a[k];//printf("\n%d",c[h]);a[k]=a[k+1];break;}}}k=1;while(h>1){k=k*c[h]*c[h-1];h=h-2;w3++;}if(h==1){k=k*c[1];returnk;}elsereturnk;intmain(void)intm,n;printf（“ 請(qǐng)輸入m,n:\n"）;scanf（"%d%d",&m,&n）;intk;k=f1（m,n）;printf（"方法一最大公約數(shù)為：%d\n",k）;k=f2（m,n）;printf（" 方法二最大公約數(shù)為：%d\n",k）;k=f3（m,n）;printf（" 方法三最大公約數(shù)為：%d\n",k）;printf（"\n \n"）;printf（"\n計(jì)數(shù)器顯示結(jié)果：\n\n\n"）;printf（"方法一：%d\n",w2）;printf（"方法二：%d\n",w）;printf（"方法三：%d\n",w3）;printf（"\n \n"）;floata,i;clock_tstart,finish;doubleusetime;i=0;start=clock（）;

while(i<1000000){f1(m,n);i++;}finish=clock();usetime=finish-start;printf(“ 方法一用時(shí)％.f*10八(-6)豪秒\n",i=0;start=clock();while(i<1000000){f2(m,n);i++;}finish=clock();usetime=finish-start;printf(“ 方法二用時(shí)%.f*10八(-6)豪秒\n",i=0;start=clock();usetime);usetime);while(i<1000000)usetime);usetime);f3(m,n);i++;finish=clock();usetime=finish-start;printf(“ 方法三用時(shí)％.f*10八(-6)豪秒\n",usetime);}五、實(shí)驗(yàn)過(guò)程原始記錄(測(cè)試數(shù)據(jù)、圖表、計(jì)算等)請(qǐng)給出各個(gè)操作步驟的截圖和說(shuō)明；三種算法得到結(jié)果驗(yàn)證結(jié)果：計(jì)數(shù)器：我想到的是做一次循環(huán)就加一計(jì)算算法運(yùn)行時(shí)間結(jié)果：在計(jì)算時(shí)間過(guò)程中因?yàn)橛?jì)算機(jī)的運(yùn)算速度很快，所以我利用了循環(huán)把時(shí)間精確得到10-6毫秒六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論(誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時(shí)必須用計(jì)算紙或程序運(yùn)行結(jié)果、改進(jìn)、收獲)請(qǐng)結(jié)合實(shí)驗(yàn)的結(jié)果分析算法原理；在實(shí)驗(yàn)中遇到了些什么問(wèn)題，如何解決；有什么收獲等；在本次實(shí)驗(yàn)中代碼是獨(dú)自完成的，一開(kāi)始我感覺(jué)這個(gè)代碼最多半小時(shí)就可以完成，但是第三個(gè)算法的時(shí)候我分析了好久才寫(xiě)出來(lái)，在計(jì)算三種方法運(yùn)行時(shí)間的時(shí)候，我一開(kāi)始只精確到毫秒(ms),計(jì)算結(jié)果都是零，后面我寫(xiě)了一個(gè)循環(huán)調(diào)試才發(fā)現(xiàn)是我的精確度還在不夠，所以我想到了計(jì)算算法執(zhí)行了1000000次之后所用的時(shí)間，然后再求平均每次執(zhí)行的時(shí)間。結(jié)果分析：從前面的復(fù)雜度0(n)的出歐幾里得算法的是最優(yōu)算法，連續(xù)整除法其次，最復(fù)雜的是分解質(zhì)因數(shù)算法，再?gòu)拇a運(yùn)行的計(jì)數(shù)器和計(jì)算的時(shí)間來(lái)看結(jié)果恰好和前面的復(fù)雜度得到的結(jié)果一致，所以的出結(jié)論：歐幾里得算法最