




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、輾轉(zhuǎn)相除法與更相減損術(shù),算 法 案 例,第一課時(shí),思考:,小學(xué)學(xué)過(guò)的求兩個(gè)數(shù)的最大公約數(shù)的方法?,先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除這兩個(gè)數(shù),一直除到所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連乘起來(lái).,例:求下面兩個(gè)正整數(shù)的最大公約數(shù):,(1)求25和35的最大公約數(shù) (2)求49和63的最大公約數(shù),所以,25和35的最大公約數(shù)為5,所以,49和63的最大公約數(shù)為7,思考:除了用這種方法外還有沒(méi)有其它方法?,例:如何算出8251和6105的最大公約數(shù)?,新課講解:,一、輾轉(zhuǎn)相除法(歐幾里得算法),1、定義: 所謂輾轉(zhuǎn)相除法,就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零,則將余數(shù)和較小的
2、數(shù)構(gòu)成新的一對(duì)數(shù),繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)。,2、步驟: (以求8251和6105的最大公約數(shù)的過(guò)程為例),第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù),求得商和余數(shù)8251=61051+2146,結(jié)論: 8251和6105的公約數(shù)就是6105和2146的公約數(shù),求8251和6105的最大公約數(shù),只要求出6105和2146的公約數(shù)就可以了。,第二步 對(duì)6105和2146重復(fù)第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。,完整的過(guò)程,8251=61051+2146,6105=21462+
3、1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例: 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù),也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù),也就是225和135的最大公約數(shù),輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟,這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。,m = n q r,用程序框圖表示出右邊的過(guò)程,r=m MOD n,m = n,n = r,r=0?,是,否,思考:輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)?,思考
4、:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎?,(1)、算法步驟:,第一步:輸入兩個(gè)正整數(shù)m ,n (mn). 第二步:計(jì)算m除以n所得的余數(shù)r. 第三步:m=n,n=r. 第四步:若r0,則m,n的最大公約數(shù)等于m; 否則轉(zhuǎn)到第二步. 第五步:輸出最大公約數(shù)m.,(2)、程序框圖:,開(kāi)始,輸入m,n,r=m MOD n,m=n,r=0?,是,否,n=r,輸出m,結(jié)束,(3)、程序:,INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,二、更相減損術(shù),可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以
5、等數(shù)約之。,第一步:任意給定兩個(gè)正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡(jiǎn);若不是則執(zhí)行第二步。,第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作,直到所得的減數(shù)和差相等為止,則這個(gè)等數(shù)就是所求的最大公約數(shù)。,(1)、九章算術(shù)中的更相減損術(shù):,1、背景介紹:,(2)、現(xiàn)代數(shù)學(xué)中的更相減損術(shù):,2、定義:,所謂更相減損術(shù),就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)減去較小的數(shù),然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù),再用較大的數(shù)減去較小的數(shù),反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等,此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)。,例: 用更相減損術(shù)求98與63的最大公約數(shù).,
6、解:由于63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減,9863356335283528728721 21721 1477,所以,98和63的最大公約數(shù)等于7,3、方法:,1、用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù),練習(xí):,思路分析:先約簡(jiǎn),再求21與18的最大公約數(shù),然后乘以?xún)纱渭s簡(jiǎn)的質(zhì)因數(shù)4。,2、求324、243、135這三個(gè)數(shù)的最大公約數(shù)。,思路分析:求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù),第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。,(1)、算法步驟,第一步:輸入兩個(gè)正整數(shù)a,b; 第二步:若a不等于b ,則執(zhí)行第三步;否則轉(zhuǎn)到第五步; 第三步:把a(bǔ)-b的差賦予r; 第四步:如果br, 那么把b賦給a,把r賦給b;否則把r賦給a;返回第二步; 第五步:輸出最大公約數(shù)b.,*思考:你能根據(jù)更相減損術(shù)設(shè)計(jì)程序,求兩個(gè)正整數(shù)的最大公約數(shù)嗎?,(2)、程序框圖,(3)、程序,INPUT “a,b=“;a,b WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END,比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 (1)都是求最大公約數(shù)的方法,計(jì)算上輾轉(zhuǎn)相除法以除法為主,更相減損術(shù)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國(guó)自由飛行包行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國(guó)自動(dòng)水龍頭行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢(xún)研究報(bào)告
- 美妝品牌趨勢(shì)引領(lǐng)者:探索零廢棄美妝品牌的行業(yè)未來(lái)
- 學(xué)校營(yíng)養(yǎng)餐計(jì)劃的科學(xué)食譜教學(xué)手冊(cè)
- 2025至2030中國(guó)能源行業(yè)市場(chǎng)發(fā)展現(xiàn)狀及前景趨勢(shì)與行業(yè)深度研究及發(fā)展前景投資評(píng)估分析
- 2025至2030中國(guó)聚苯并咪唑(PBI)行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)老年生活用品行業(yè)市場(chǎng)深度調(diào)研及發(fā)展趨勢(shì)與投資價(jià)值報(bào)告
- 2025至2030中國(guó)美容口服液行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 北師大版六年級(jí)數(shù)學(xué)下冊(cè)線上復(fù)習(xí)計(jì)劃
- 2025至2030中國(guó)網(wǎng)站運(yùn)營(yíng)行業(yè)市場(chǎng)深度研究與戰(zhàn)略咨詢(xún)分析報(bào)告
- 戶(hù)外反洗錢(qián)宣傳活動(dòng)方案
- 恙蟲(chóng)病護(hù)理查房
- 腫瘤免疫治療及護(hù)理講課件
- 心理調(diào)適培訓(xùn)課件
- 新建3000P(Flops)智算超算中心項(xiàng)目可行性研究報(bào)告寫(xiě)作模板-備案審批
- 八年級(jí)數(shù)學(xué)下學(xué)期《平行四邊形》的教學(xué)反思
- 2025-2030中國(guó)交流伺服控制器行業(yè)應(yīng)用動(dòng)態(tài)及投資前景分析報(bào)告
- 紗線質(zhì)量檢測(cè)儀器與設(shè)備考核試卷
- 安全生產(chǎn)天數(shù)管理制度
- 廣東省廣州市南沙區(qū)2025年八年級(jí)下學(xué)期期末數(shù)學(xué)試題及參考答案
- 2025年廣西公需科目答案03
評(píng)論
0/150
提交評(píng)論