版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
邊城高級中學
張秀洲1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)1.通過閱讀中國古代中的更相減損術(shù)算法案例,體會中國數(shù)學對世界數(shù)學發(fā)展的貢獻;2.知道輾轉(zhuǎn)相除法和更相減損術(shù),能用輾轉(zhuǎn)相除法和更相減損術(shù)求兩個正整數(shù)的最大公約數(shù).自學教材P34-P37解決下列問題一、能用輾轉(zhuǎn)相除法和更相減損術(shù)求兩個正整數(shù)的最大公約數(shù).二、《學海導航》P25-P26“雙層練習”“范例剖析”三、教材P45第1題例:求下面兩個正整數(shù)的最大公約數(shù):(1)求25和35的最大公約數(shù)(2)求49和63的最大公約數(shù)25(1)5535749(2)77639所以,25和35的最大公約數(shù)為5所以,49和63的最大公約數(shù)為7思考:除了用這種方法外還有沒有其它方法?例:如何算出8251和6105的最大公約數(shù)?一、輾轉(zhuǎn)相除法(歐幾里得算法)1、定義:
所謂輾轉(zhuǎn)相除法,就是對于給定的兩個數(shù),用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù),繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。
2、步驟:(以求8251和6105的最大公約數(shù)的過程為例)第一步用兩數(shù)中較大的數(shù)除以較小的數(shù),求得商和余數(shù)
8251=6105×1+2146結(jié)論:8251和6105的公約數(shù)就是6105和2146的公約數(shù),求8251和6105的最大公約數(shù),只要求出6105和2146的公約數(shù)就可以了。第二步對6105和2146重復(fù)第一步的做法6105=2146×2+1813
同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例:用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù),也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù),也就是225和135的最大公約數(shù)思考1:從上面的兩個例子中可以看出計算的規(guī)律是什么?S1:用大數(shù)除以小數(shù)S2:除數(shù)變成被除數(shù),余數(shù)變成除數(shù)S3:重復(fù)S1,直到余數(shù)為0
輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟,這實際上是一個循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q
+r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否思考:你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎?(1)、算法步驟:第一步:輸入兩個正整數(shù)m,n(m>n).第二步:計算m除以n所得的余數(shù)r.第三步:m=n,n=r.第四步:若r=0,則m,n的最大公約數(shù)等于m;否則轉(zhuǎn)到第二步.第五步:輸出最大公約數(shù)m.開始輸入m,n求m除以n的余數(shù)rm=nn=rr=0?是輸出m結(jié)束否(2)、程序框圖:開始輸入m,n求m除以n的余數(shù)rm=nn=rr=0?是輸出m結(jié)束否INPUTm,nDOr=m
MODnm=nn=rLOOPUNTILr=0PRINTmEND(3)、程序:思考:如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法,則用輾轉(zhuǎn)相除法求兩個正整數(shù)m,n的最大公約數(shù)的程序框圖和程序分別如何表示?開始輸入m,n求m除以n的余數(shù)rm=nn>0?否輸出m結(jié)束是n=rINPUTm,nWHILE
n>0r=mMODnm=nn=rWENDPRINTmEND二、更相減損術(shù)可半者半之,不可半者,副置分母、子之數(shù),以少減多,更相減損,求其等也,以等數(shù)約之。第一步:任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡;若不是則執(zhí)行第二步。第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所求的最大公約數(shù)。(1)、《九章算術(shù)》中的更相減損術(shù):1、背景介紹:(2)、現(xiàn)代數(shù)學中的更相減損術(shù):2、定義:所謂更相減損術(shù),就是對于給定的兩個數(shù),用較大的數(shù)減去較小的數(shù),然后將差和較小的數(shù)構(gòu)成新的一對數(shù),再用較大的數(shù)減去較小的數(shù),反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等,此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。例:用更相減損術(shù)求98與63的最大公約數(shù).解:由于63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減98-63=35
63-35=28
35-28=7
28-7=2121-7=2114-7=7所以,98和63的最大公約數(shù)等于73、方法:(1)、算法步驟第一步:輸入兩個正整數(shù)a,b(a>b);第二步:若a不等于b,則執(zhí)行第三步;否則轉(zhuǎn)到第五步;第三步:把a-b的差賦予r;第四步:如果b>r,那么把b賦給a,把r賦給b;否則把r賦給a,執(zhí)行第二步;第五步:輸出最大公約數(shù)b.思考:你能根據(jù)更相減損術(shù)設(shè)計程序,求兩個正整數(shù)的最大公約數(shù)嗎?(2)、程序框圖開始輸入m,nn>k?m=n是輸出m結(jié)束m≠n?k=m-n是否n=km=k否(3)、程序開始輸入m,nn>k?m=n是輸出m結(jié)束m≠n?k=m-n是否n=km=k否INPUTm,nWHILE
m<>nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND【例1】分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法:168=93×1+75,93=75×1+18,75=18×4+3,18=3×6.更相減損術(shù):168-93=75,
93-75=18,
75-18=57,
57-18=39,
39-18=21,
21-18=3,
18-3=15,
15-3=12,
12-3=9,
9-3=6,
6-3=3.因為325=130×2+65,130=65×2,所以325與130的最大公約數(shù)是65.
因為270=65×4+10,65=10×6+5,10=5×2,所以65與270最大公約數(shù)是5.故325,130,270三個數(shù)的最大公約數(shù)是5.【例2】求325,130,270三個數(shù)的最大公約數(shù).三、教材P45第1題提煉精華總結(jié)收獲,暢談體會※對自己說,你有什么收獲?※對同學說,你有什么提示?※對老師說,你有什么疑惑?比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)都是求最大公約數(shù)的方法,計算上輾轉(zhuǎn)相除法以除法為主,更相減損術(shù)以減法為主,計算次數(shù)上輾轉(zhuǎn)相除法計算次
溫馨提示
- 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025版淋浴房定制設(shè)計與安裝全流程服務(wù)合同3篇
- 河南省周口市鄲城縣2024-2025學年九年級上學期期末考試英語試題(含答案含聽力原文無音頻)
- 2025版土地承包經(jīng)營權(quán)入股合作合同示范文本6篇
- 宗教音樂與音像制品的和諧共生考核試卷
- 二零二五年度物流裝備租賃合同模板
- “超級全能生”全國卷26省聯(lián)考高考語文試題(甲卷)(含答案)
- 二零二五年度木地板品牌授權(quán)區(qū)域代理合同4篇
- 2025年企業(yè)信息保密協(xié)議格式
- 2025年學校體育活動協(xié)議
- 2025年學校食堂租賃協(xié)議
- 2024年社區(qū)警務(wù)規(guī)范考試題庫
- 2024年食用牛脂項目可行性研究報告
- 消防安全隱患等級
- 溫室氣體(二氧化碳和甲烷)走航監(jiān)測技術(shù)規(guī)范
- 部編版一年級語文下冊第一單元大單元教學設(shè)計
- 《保單檢視專題》課件
- 北京地鐵13號線
- 2023山東春季高考數(shù)學真題(含答案)
- 職業(yè)衛(wèi)生法律法規(guī)和標準培訓課件
- 高二下學期英語閱讀提升練習(二)
- 民事訴訟證據(jù)清單模板
評論
0/150
提交評論