




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、算算 法法 案案 例例(第一課時(shí)第一課時(shí))1、求兩個(gè)正整數(shù)的最大公約數(shù)、求兩個(gè)正整數(shù)的最大公約數(shù)(1)求)求25和和35的最大公約數(shù)的最大公約數(shù)(2)求)求49和和63的最大公約數(shù)的最大公約數(shù)2、求、求8251和和6105的最大公約數(shù)的最大公約數(shù) 25(1) 5535749(2) 77639所以,所以,25和和35的最大公約數(shù)為的最大公約數(shù)為5所以,所以,49和和63的最大公約數(shù)為的最大公約數(shù)為7輾轉(zhuǎn)相除法(歐幾里得算法)輾轉(zhuǎn)相除法(歐幾里得算法)觀察用輾轉(zhuǎn)相除法求觀察用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過程的最大公約數(shù)的過程 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù),求得商和余
2、數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù),求得商和余數(shù)8251=61051+2146結(jié)論:結(jié)論: 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù),求的公約數(shù),求8251和和6105的最大公約數(shù),只要求出的最大公約數(shù),只要求出6105和和2146的公約數(shù)就可以了。的公約數(shù)就可以了。第二步第二步 對(duì)對(duì)6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過程完整的過程8251=61051+2146 6105=21462+1813 2146=
3、18131+3331813=3335+148333=1482+37148=374+0例例2 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351+90135=901+4590=452顯然顯然37是是148和和37的最大公約的最大公約數(shù),也就是數(shù),也就是8251和和6105的最的最大公約數(shù)大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù),也就是的最大公約數(shù),也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1:從上面的兩個(gè)例子可以看出計(jì):從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么?算的規(guī)律是什么? S1:用大數(shù)除以小數(shù):用大數(shù)除以小數(shù)S2:除數(shù)變成被除數(shù),余
4、數(shù)變成除數(shù):除數(shù)變成被除數(shù),余數(shù)變成除數(shù)S3:重復(fù):重復(fù)S1,直到余數(shù)為,直到余數(shù)為0開始開始輸入兩個(gè)正整數(shù)輸入兩個(gè)正整數(shù)n,mr= m MOD nr=0?m=nn=r輸出最大公約數(shù)輸出最大公約數(shù)m結(jié)束結(jié)束否否是是第一步第一步,給定兩個(gè)正整數(shù)給定兩個(gè)正整數(shù)m,n.第二步第二步,計(jì)算計(jì)算m除以的余數(shù)除以的余數(shù)r.第三步第三步,m=n,n=r.第四步第四步,若若r=0,則則m,n的最大公的最大公約數(shù)等于約數(shù)等于m;否則否則,返回第二步返回第二步.算法步驟算法步驟:思考思考?你能把輾轉(zhuǎn)相除法編你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎成一個(gè)計(jì)算機(jī)程序嗎?程序框圖程序框圖程序程序INPUT m, nDO r
5、=m mod n m=n n=rLOOP UNTIL r=0PRINT mEND 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟,這實(shí)際上是停止的步驟,這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。一個(gè)循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否九章算術(shù)九章算術(shù)更相減損術(shù)更相減損術(shù) 算理:算理:可半者半之,不可半者,副置分母、子之?dāng)?shù),以少
6、減多,更相減可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之。損,求其等也,以等數(shù)約之。第一步:第一步:任意給頂兩個(gè)正整數(shù);判斷他們是否都是偶數(shù)。若是,則用任意給頂兩個(gè)正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡(jiǎn);若不是則執(zhí)行第二步。約簡(jiǎn);若不是則執(zhí)行第二步。第二步:第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作,直到所得的減數(shù)和差相等為止,則這個(gè)以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作,直到所得的減數(shù)和差相等為止,則這個(gè)等數(shù)就是所求的最大公約數(shù)。等數(shù)就是所求的最大公約數(shù)。例例3 用更相減損術(shù)求用更相減損術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)解:由于解:由于63不是偶數(shù),把
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 杭州商品策劃管理辦法
- 中小學(xué)課堂教學(xué)質(zhì)量評(píng)估標(biāo)準(zhǔn)與實(shí)施辦法
- 海底熱液區(qū)生態(tài)修復(fù)-洞察及研究
- 低糖低GI食品與飲料市場(chǎng)現(xiàn)狀及未來趨勢(shì)研究
- 基于區(qū)塊鏈的整形外科手術(shù)供應(yīng)鏈管理研究-洞察及研究
- 前端開發(fā)技術(shù)的實(shí)戰(zhàn)案例分析教學(xué)體系構(gòu)建
- 高壓變電站建設(shè):設(shè)備安裝施工方案及實(shí)施細(xì)節(jié)探討
- 全球化背景下企業(yè)資源配置效率研究
- 營(yíng)業(yè)線施工安全:確保作業(yè)安全的全面措施
- 循環(huán)經(jīng)濟(jì)視域下再制造產(chǎn)業(yè)集群的競(jìng)爭(zhēng)力評(píng)價(jià)體系研究
- 工程造價(jià)咨詢服務(wù)方案(技術(shù)方案)
- DB44-T 1948-2016 移動(dòng)通信固定終端天線
- 2023廣西公需科目真題(關(guān)于人才工作的重要論述)
- 管道非開挖修復(fù)方案
- 熔鑄作業(yè)指導(dǎo)書
- 車站旅客地道施工方案
- 《小米公司融資問題研究10000字(論文)》
- YS/T 3019-2013氰化堆浸提金工藝安全生產(chǎn)技術(shù)規(guī)范
- GB/T 18745-2006地理標(biāo)志產(chǎn)品武夷巖茶
- GB/T 13323-2009光學(xué)制圖
- GB 28755-2012簡(jiǎn)易升降機(jī)安全規(guī)程
評(píng)論
0/150
提交評(píng)論