《輾轉(zhuǎn)相除法與更相減損術(shù)》

1．3算法案例1．3.1輾轉(zhuǎn)相除法與更相減損術(shù)

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接輾轉(zhuǎn)相除法求最大公約數(shù)求228與1995的最大公約數(shù)．分析：因為兩數(shù)沒有明顯的公約數(shù)，可以考慮用輾轉(zhuǎn)相除法．解析：1995＝8×228＋171，228＝1×171＋57，171＝3×57，所以228與1995最大公約數(shù)為57.答案：57?跟蹤訓(xùn)練1．用輾轉(zhuǎn)相除法求得459和357的最大公約數(shù)是(

)A．3B．9C．17D．51D

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接更相減損術(shù)求最大公約數(shù)用更相減損術(shù)求98與63的最大公約數(shù)．解析：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98與63的最大公約數(shù)是7.?跟蹤訓(xùn)練2．用更相減損術(shù)求225與135的最大公約數(shù)為(

)A．45B．5C．9D．15A

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接比較輾轉(zhuǎn)相除法與更相減損術(shù)用輾轉(zhuǎn)相除法求下面兩數(shù)的最大公約數(shù)，并用更相減損術(shù)檢驗?zāi)愕慕Y(jié)果：(1)80，36；(2)294，84.分析：使用輾轉(zhuǎn)相除法，我們可依據(jù)a＝nb＋r這個式子，反復(fù)執(zhí)行，直到r＝0為止．用更相減損術(shù)就是根據(jù)r＝a－b這個式子，反復(fù)執(zhí)行．

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接解析：(1)80＝36×2＋8，36＝8×4＋4，8＝4×2＋0，即80與36的最大公約數(shù)是4.驗證：80－36＝44，44－36＝8，36－8＝28，28－8＝20，20－8＝12，12－8＝4，8－4＝4.∴80與36的最大公約數(shù)為4.

(2)294＝84×3＋42，84＝42×2，即294與84的最大公約數(shù)是42.驗證：∵294與84都是偶數(shù)可同時除以2，即取147與42的最大公約數(shù)后再乘2.147－42＝105，105－42＝63，63－42＝21，42－21＝21，∴294與84的最大公約數(shù)為21×2＝42.點評：由該題可以看出，輾轉(zhuǎn)相除法求最大公約數(shù)步驟較少，而更相減損術(shù)運算簡易，解題時要靈活運用．

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接?跟蹤訓(xùn)練3．用更相減損術(shù)求98與64的最大公約數(shù)．解析：由于64是偶數(shù)，減半為32，把98和32以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98－32＝66，66－32＝34，34－32＝2，32－2＝30，30－2＝28，…，4－2＝2，所以，98與64的最大公約數(shù)是2.

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接輾轉(zhuǎn)相除法的程序框圖與程序?qū)懗鲚氜D(zhuǎn)相除法的程序框圖及程序．解析：r＝mMODn表示m除以n的余數(shù)為r，例如：3＝15MOD6.程序框圖：

學習目標

預(yù)習導(dǎo)學

典例精析

欄目鏈接程序：點評：借助程序框圖準確理解程序的本質(zhì)．

學習目標

預(yù)習導(dǎo)