輾轉相除法市公開課一等獎省賽課微課金獎課件_第1頁
輾轉相除法市公開課一等獎省賽課微課金獎課件_第2頁
輾轉相除法市公開課一等獎省賽課微課金獎課件_第3頁
輾轉相除法市公開課一等獎省賽課微課金獎課件_第4頁
輾轉相除法市公開課一等獎省賽課微課金獎課件_第5頁
已閱讀5頁,還剩14頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

輾轉相除法與第1頁知識探究(一):輾轉相除法思索1:18與30最大條約數(shù)是多少?你是怎樣得到?先用兩個數(shù)公有質因數(shù)連續(xù)去除,一直除到所得商是互質數(shù)為止,然后把全部除數(shù)連乘起來即為最大條約數(shù).第2頁思索2:對于8251與6105這兩個數(shù),因為其公有質因數(shù)較大,利用上述方法求最大條約數(shù)就比較困難.注意到8251=6105×1+2146,那么8251與6105這兩個數(shù)條約數(shù)和6105與2146條約數(shù)有什么關系?第3頁思索3:又6105=2146×2+1813,同理,6105與2146條約數(shù)和2146與1813條約數(shù)相等.重復上述操作,你能得到8251與6105這兩個數(shù)最大條約數(shù)嗎?2146=1813×1+333,148=37×4+0.333=148×2+37,1813=333×5+148,8251=6105×1+2146,6105=2146×2+1813,第4頁

輾轉相除法是一個重復執(zhí)行直到余數(shù)等于0停頓步驟,這實際上是一個循環(huán)結構。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?是否思考4:輾轉相除法中的關鍵步驟是哪種邏輯結構?第5頁思索5:上述求兩個正整數(shù)最大條約數(shù)方法稱為輾轉相除法或歐幾里得算法.普通地,用輾轉相除法求兩個正整數(shù)m,n最大條約數(shù),能夠用什么邏輯結構來結構算法?其算法步驟怎樣設計?第一步,給定兩個正整數(shù)m,n(m>n).第二步,計算m除以n所得余數(shù)r.第三步,m=n,n=r.第四步,若r=0,則m,n最大條約數(shù)等 于m;不然,返回第二步.

第6頁思索6:該算法程序框圖怎樣表示?開始輸入m,n求m除以n余數(shù)rm=nn=rr=0?是輸出m結束否第7頁思索7:該程序框圖對應程序怎樣表述?INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND開始輸入m,n求m除以n余數(shù)rm=nn=rr=0?是輸出m結束否第8頁思索8:假如用當型循環(huán)結構結構算法,則用輾轉相除法求兩個正整數(shù)m,n最大條約數(shù)程序框圖和程序分別怎樣表示?第9頁開始輸入m,n求m除以n余數(shù)rm=nr>0?否輸出m結束是n=rINPUTm,nWHILEr>0r=mMODnm=nn=rWENDPRINTmEND第10頁練習1:利用輾轉相除法求兩數(shù)4081與20723最大條約數(shù).(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.第11頁更相減損術“更相減損術”(也是求兩個正整數(shù)最大條約數(shù)算法)步驟:第一步:任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡;若不是則執(zhí)行第二步。第二步:以較大數(shù)減較小數(shù),接著把所得差與較小數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得減數(shù)和差相等為止,則這個等數(shù)或這個數(shù)與約簡數(shù)乘積就是所求最大條約數(shù)。第12頁例、用更相減損術求98與63最大條約數(shù)(自己按照步驟求解)解:因為63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉相減。所以,98和63最大條約數(shù)等于7。98-63=35

63-35=2835-28=728-7=2121-7=1414-7=7第13頁更相減損是一個重復執(zhí)行直到減數(shù)等于差時停頓步驟,這實際也是一個循環(huán)結構

思索:更相減損直到何時結束?利用是哪種算法結構?第14頁程序:INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND開始輸入:a,b輸出:a×2i結束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?YNNNYi=0i=i+1第15頁

例2分別用輾轉相除法和更相減損術求168與93最大條約數(shù).輾轉相除法:168=93×1+75, 93=75×1+18, 75=18×4+3, 18=3×6.第16頁更相減損術: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.第17頁例3:用輾轉相除法和更相減損術求210與714最大條約數(shù).第18頁比較輾轉相除法與更相減損術區(qū)分(1)都是求最大條約數(shù)方

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論