




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
最大公約數(shù)的三種算法復(fù)雜度分析時間計(jì)算最大公約數(shù)的三種算法復(fù)雜度分析時間計(jì)算最大公約數(shù)的三種算法復(fù)雜度分析時間計(jì)算最大公約數(shù)的三種算法復(fù)雜度分析時間計(jì)算編制僅供參考審核批準(zhǔn)生效日期地址:電話:傳真:郵編:昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告(2011—2012學(xué)年第1學(xué)期)課程名稱:算法設(shè)計(jì)與分析開課實(shí)驗(yàn)室:信自樓機(jī)房4442011年10月12日年級、專業(yè)、班計(jì)科092學(xué)號5214姓名徐興繁成績實(shí)驗(yàn)項(xiàng)目名稱求最大公約數(shù)指導(dǎo)教師吳晟教師評語該同學(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)過程是否詳細(xì)記錄: A.詳細(xì)□ B.一般□ C.沒有□教師簽名:年月日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容求兩個自然數(shù)m和n的最大公約數(shù)。2.上機(jī)目的(1)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識,實(shí)現(xiàn)課程間的平滑過渡;(2)掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗(yàn)分析方法;(3)理解這樣一個觀點(diǎn):不同的算法能夠解決相同的問題,這些算法的解題思路不同,復(fù)雜程度不同,解題效率也不同。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖(方框原理圖或程序流程圖)(1)至少設(shè)計(jì)出三個版本的求最大公約數(shù)算法;(2)對所設(shè)計(jì)的算法采用大O符號進(jìn)行時間復(fù)雜性分析;(3)上機(jī)實(shí)現(xiàn)算法,并用計(jì)數(shù)法和計(jì)時法分別測算算法的運(yùn)行時間;(4)通過分析對比,得出自己的結(jié)論。三、所用儀器、材料(設(shè)備名稱、型號、規(guī)格等或使用軟件)1臺PC及VISUALC++軟件四、實(shí)驗(yàn)方法、步驟(或:程序代碼或操作過程) 實(shí)驗(yàn)采用三種方法求最大公約數(shù)1、連續(xù)整數(shù)檢測法。2、歐幾里得算法3、分解質(zhì)因數(shù)算法根據(jù)實(shí)現(xiàn)提示寫代碼并分析代碼的時間復(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次,可以得出O(n)=n/2;方法二:intf2(intm,intn){ intr; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } returnn;}根據(jù)代碼輾轉(zhuǎn)相除得到歐幾里得的O(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) { *10^(-6)豪秒\n",usetime); i=0;start=clock();while(i<1000000) { f2(m,n); i++; } finish=clock(); usetime=finish-start; printf("方法二用時%.f*10^(-6)豪秒\n",usetime); i=0;start=clock();while(i<1000000) { f3(m,n); i++; } finish=clock(); usetime=finish-start; printf("方法三用時%.f*10^(-6)豪秒\n",usetime);}五、實(shí)驗(yàn)過程原始記錄(測試數(shù)據(jù)、圖表、計(jì)算等)請給出各個操作步驟的截圖和說明;三種算法得到結(jié)果驗(yàn)證結(jié)果:計(jì)數(shù)器:我想到的是做一次循環(huán)就加一計(jì)算算法運(yùn)行時間結(jié)果:在計(jì)算時間過程中因?yàn)橛?jì)算機(jī)的運(yùn)算速度很快,所以我利用了循環(huán)把時間精確得到10-6毫秒六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論(誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中,繪制曲線圖時必須用計(jì)算紙或程序運(yùn)行結(jié)果、改進(jìn)、收獲)請結(jié)合實(shí)驗(yàn)的結(jié)果分析算法原理;在實(shí)驗(yàn)中遇到了些什么問題,如何解決;有什么收獲等;在本次實(shí)驗(yàn)中代碼是獨(dú)自完成的,一開始我感覺這個代碼最多半小時就可以完成,但是第三個算法的時候我分析了好久才寫出來,在計(jì)算三種方法運(yùn)行時間的時候,我一開始只精確到毫秒(ms),計(jì)算結(jié)果都是零,后面我寫了一個循環(huán)調(diào)試才發(fā)現(xiàn)是我的精確度還在不夠,所以我想到了計(jì)算算法執(zhí)行了1000000次之后所用的時間,然后再求平均每次執(zhí)行的時間。結(jié)果分析:從前面的復(fù)雜度O(n)的出歐幾里得算法的是最優(yōu)算法,連續(xù)整除法其次,最復(fù)雜的是分解質(zhì)因數(shù)算法,再從代碼運(yùn)行的計(jì)數(shù)器和計(jì)算的時間來看結(jié)果恰好和前面的復(fù)雜度得到的結(jié)果一致,所以的出結(jié)論:歐幾里得算法最優(yōu)。從這次實(shí)驗(yàn)的結(jié)果我了解到了算法的優(yōu)與劣的差別,雖然得到的是同樣的結(jié)果,但是需要的時間和
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度國際快遞運(yùn)輸與時效跟蹤服務(wù)合同
- 2025年度屋頂租賃合同附屋頂廣告權(quán)益共享協(xié)議
- 2025年度時尚女鞋品牌全國代理權(quán)購買合同樣本
- 培養(yǎng)學(xué)生團(tuán)隊(duì)合作能力的美術(shù)教學(xué)計(jì)劃
- 激活團(tuán)隊(duì)潛力的成功經(jīng)驗(yàn)計(jì)劃
- 學(xué)校年度班級工作計(jì)劃表目
- 區(qū)域倉庫布局的設(shè)計(jì)原則計(jì)劃
- 2025年港物運(yùn)輸項(xiàng)目合作計(jì)劃書
- 主管的職業(yè)素養(yǎng)與榜樣作用計(jì)劃
- 2025年激光轉(zhuǎn)速測量儀項(xiàng)目建議書
- 扶梯人行道檢驗(yàn)驗(yàn)收作業(yè)指導(dǎo)書
- GB/T 20308-2020產(chǎn)品幾何技術(shù)規(guī)范(GPS)矩陣模型
- 男孩女孩動起來健康運(yùn)動知識PPT模板
- 體育原理課件
- 鐵路道岔知識課件
- 自考公共關(guān)系學(xué)課件
- 森林害蟲防治方法課件
- 各種el34名膽電子管評測
- 超分子化學(xué)-杯芳烴課件
- 北郵工程數(shù)學(xué)期末試卷B卷
- 超長結(jié)構(gòu)及大體積混凝土專項(xiàng)施工方案
評論
0/150
提交評論