黑龍江省大興安嶺市漠河縣一中2020學(xué)年高中數(shù)學(xué) 第一章 算法初步 1.3.1 算法案例 輾轉(zhuǎn)相除法與更相減損術(shù)學(xué)案 新人教A版必修3（通用）

1、1.3.1算法案例 輾轉(zhuǎn)相除法與更相減損術(shù)授課日期: 姓名: 班級(jí): 學(xué)習(xí)目標(biāo)知識(shí)與技能1.理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析。2.基本能根據(jù)算法語句與程序框圖的知識(shí)設(shè)計(jì)完整的程序框圖并寫出算法程序。過程與方法在輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的學(xué)習(xí)過程中對(duì)比我們常見的約分求公因式的方法，比較它們?cè)谒惴ㄉ系膮^(qū)別，并從程序的學(xué)習(xí)中體會(huì)數(shù)學(xué)的嚴(yán)謹(jǐn)，。情態(tài)與價(jià)值通過閱讀中國古代數(shù)學(xué)中的算法案例，體會(huì)中國古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S能力，在利用算法解決數(shù)學(xué)問題的過程中培養(yǎng)理性的精神和動(dòng)手實(shí)踐的能力。學(xué)習(xí)重難點(diǎn)重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求

2、最大公約數(shù)的方法。難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。使用說明及學(xué)法指導(dǎo):1、先閱讀教材3437頁認(rèn)真思考,在理解最大公約數(shù)的基礎(chǔ)上去發(fā)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)中的數(shù)學(xué)規(guī)律，并能模仿已經(jīng)學(xué)過的程序框圖與算法語句設(shè)計(jì)出輾轉(zhuǎn)相除法與更相減損術(shù)的程序框圖與算法程序。2、把學(xué)案中自己易忘、易出錯(cuò)的知識(shí)點(diǎn)和疑難問題以及解題方法規(guī)律，及時(shí)整理在解題本，多復(fù)習(xí)記憶。3、A:自主學(xué)習(xí)；B:合作探究；C：能力提升4、小班、重點(diǎn)班完成全部，平行班至少完成A.B類題。平行班的A級(jí)學(xué)生完成80以上B完成7080C力爭(zhēng)完成60以上。知識(shí)鏈接:研究一個(gè)實(shí)際問題的算法，主要從算法步驟、程序框圖和編

3、寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪三種？在程序設(shè)計(jì)中基本的算法語句有哪五種？學(xué)習(xí)過程:A問題1.在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識(shí)，你能求出18與30的公約數(shù)嗎？A問題2.接著進(jìn)一步研究問題，我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容。B問題3.例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。（分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù)）以上我

4、們求最大公約數(shù)的方法就是 。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；第二步：若r00，則n為m，n的最大公約數(shù)；若r00，則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1；第三步：若r10，則r1為m，n的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；依次計(jì)算直至rn0，此時(shí)所得到的rn1即為所求的最大公約數(shù)。練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù)（答案：53）B問題4:該算法的程序框圖如何表示？B問題5.更相減損術(shù)我

5、國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù)。例2 用更相減損術(shù)求98與63的最大公約數(shù).練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。（答案：12）B問題6.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計(jì)

6、算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到C問題7.更相減損術(shù)計(jì)算的程序框圖及程序課堂測(cè)試A1.用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù).（1）225；135 （2）98；196 （3）72；168 （4）153；119A2.分別用輾轉(zhuǎn)相除法和更相減損術(shù)求378與90的最大公約數(shù)A3.求123和48的最大公約數(shù)C4.求三個(gè)數(shù)1734,816,1343的最大公約數(shù)課堂小結(jié)與評(píng)價(jià)學(xué)后反思07：算法案例 輾轉(zhuǎn)相

7、除法與更相減損術(shù)B問題3.例1 解：8251610512146顯然8251的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)。6105214621813214618131333181333351483331482371483740則37為8251與6105的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù)（答案：53）例2 用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：9863356335283528728721217141477所以，98與63的最大公約數(shù)是7。練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。（答案：12）C問題7.更相減損術(shù)計(jì)算的程序框圖及程序程序：INPUT “m=”;mINPUT “n=”;nIF mn THEN x=mm=nn=xEND IFr=m MOD nWHIL