2023學(xué)年完整公開(kāi)課版算法案例

第一章算法初步算法案例（一）359151.在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求出18與30的最大公約數(shù)嗎？183023∴18和30的最大公約數(shù)是2×3=6.先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除,一直除到所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連乘起來(lái).2.如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)?新課引入1.輾轉(zhuǎn)相除法:求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。分析：8251與6105兩數(shù)都比較大，而且沒(méi)有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù).解：8251＝6105×1＋2146注：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。案例1輾轉(zhuǎn)相除法與更相減損術(shù)例題剖析求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。解：8251＝6105×1＋2146;則37為8251與6105的最大公約數(shù)。

以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.第一步：輸入兩個(gè)正整數(shù)m,n(m>n).第二步：計(jì)算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：若r＝0,則m,n的最大公約數(shù)等于m；否則轉(zhuǎn)到第二步.第五步：輸出最大公約數(shù)m.誘思探究（2）算法步驟（1）算法分析：所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)。你能寫(xiě)出利用輾轉(zhuǎn)相除法求最大公約數(shù)的程序嗎？開(kāi)始輸入m,nr=mMODnm=nr=0?是否n=r

輸出m結(jié)束INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND（3）程序框圖（4）程序利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).課堂練習(xí)解：20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.所以4081與20723的最大公約數(shù)為53.2.更相減損術(shù):

我國(guó)早期也有解決求最大公約數(shù)問(wèn)題的算法，就是更相減損術(shù)。

第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù)。用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，所以，98與63的最大公約數(shù)是7。98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.例題剖析2用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。課堂練習(xí)解：把84與72分別除以2得：42，3621-18=318-3=1515-3=1212-3=99-3=66-3=3所以84與72的最大公約數(shù)為12.再分別除以2得：21，18輾轉(zhuǎn)相除法與更相減損術(shù)的比較有何區(qū)別？（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主;計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.誘思探究2如何求324、243、135這三個(gè)數(shù)的最大公約數(shù)。思路分析：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。誘思探究3課堂小結(jié)

本節(jié)課學(xué)習(xí)的主要內(nèi)容：