1.3-2更相減損術(精)_第1頁
1.3-2更相減損術(精)_第2頁
免費預覽已結束，剩余6頁可下載查看

下載本文檔

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

文檔簡介

1、1.3算法案例第二課時知識探究(二)：更相減損術思考 1：設兩個正整數 mn,若 m-n=k,貝!Jm與n的最大公約數和n與k的最大公約數 有什么關系？反復利用這個原理，可求 得 98與 63 的最大公約數為多少？98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.思考 2:上述求兩個正整數的最大公約數 的方法稱為更相減損術一般地，用更相 減損術求兩個正整數 m, n 的最大公約數， 可以用什么邏輯結構來構造算法？其算 法步驟如何設計？第一步，給定兩個正整數n (mn).第二步，計算m-n所得的差k.第三步，比較n與k的大小，其中大者用說 示，小者

2、用n表示.第四步，若m=m則m, n的最大公約數等于m;否則，返回第二步.思考 3:該算法的程序框圖如何表示?INPUT m, nWHILE monk=m-nIF nk THENm=n n=k ELSE .END IF WENDPRINT mEND“更相減損術”n/m=k k=m-n思考 4:該程序框圖對應的程序如何表述?開始在中國古代數學專著九章算術中記述為：可半者半之，不可半者，副置分母、子 之數，以少減多，更相減損，求其等也， 以等數約之.理論遷移例 1 分別用輾轉相除法和更相減損 術求 168 與 93 的最大公約數.輾轉相除法：168=93X1+75, 93=75X1+18,75=1

3、8X4+3,18=3X6.更相減損術: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,例 2 求 325, 130, 270 三個數的最大 公約數.因為 325=130X2+65, 130=65X2, 所以325 與 130 的最大公約數是 65.因為 270=65X4+10, 65=10X6+5,10=5X2,所以 65 與 270 最大公約數是 5.故 325, 130, 270 三個數的最大公約 數是 5.小結作業1輾轉相除法，就是對于給定的兩個正整 數，用較大的數除以較小的數，若余數不為 零，則將余數和較小的數構成新的一對數， 繼續上面的除法，直到大數被小數除盡為止， 這時的較小的數即為原來兩個數的最大公約 數.2.更相減損術，就是對于給定的兩個正 整數，用較大的數減去較小的數，然后將差 和較小的數構成新的一對數，繼續上面的減 法，直到差

溫馨提示

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

評論

0/150

提交評論