教學(xué)設(shè)計 算法案例

算法案例整體設(shè)計教學(xué)分析在學(xué)生學(xué)習(xí)了算法的初步知識，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結(jié)合典型算法案例，讓學(xué)生經(jīng)歷設(shè)計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達能力.三維目標(biāo)1．理解算法案例的算法步驟和程序框圖.2．引導(dǎo)學(xué)生得出自己設(shè)計的算法程序.3.體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達能力.重點難點教學(xué)重點：引導(dǎo)學(xué)生得出自己設(shè)計的算法步驟、程序框圖和算法程序.教學(xué)難點：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達能力.課時安排3課時教學(xué)過程第1課時案例1輾轉(zhuǎn)相除法與更相減損術(shù)導(dǎo)入新課思路1（情境導(dǎo)入）大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的.在小學(xué)，我們學(xué)過求兩個正整數(shù)的最大公約數(shù)的方法：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.當(dāng)兩個數(shù)公有的質(zhì)因數(shù)較大時（如8251與6105），使用上述方法求最大公約數(shù)就比較困難.下面我們介紹兩種不同的算法——輾轉(zhuǎn)相除法與更相減損術(shù),由此可以體會東、西方文化的差異.思路2（直接導(dǎo)入）前面我們學(xué)習(xí)了算法步驟、程序框圖和算法語句.今天我們將通過輾轉(zhuǎn)相除法與更相減損術(shù)來進一步體會算法的思想.推進新課新知探究提出問題（1）怎樣用短除法求最大公約數(shù)？（2）怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？（3）怎樣用輾轉(zhuǎn)相除法求最大公約數(shù)？（4）怎樣用更相減損術(shù)求最大公約數(shù)？討論結(jié)果：（1）短除法求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.（2）窮舉法（也叫枚舉法）窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù).（3）輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法步驟可以描述如下：第一步，給定兩個正整數(shù)m，n.第二步，求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中.第三步，更新被除數(shù)和余數(shù)：m=n，n=r.第四步，判斷余數(shù)r是否為0.若余數(shù)為0，則輸出結(jié)果；否則轉(zhuǎn)向第二步繼續(xù)循環(huán)執(zhí)行.如此循環(huán)，直到得到結(jié)果為止.這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法.（4）更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù).《九章算術(shù)》是中國古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”翻譯為現(xiàn)代語言如下：第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步.第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).應(yīng)用示例例1用輾轉(zhuǎn)相除法求8251與6105的最大公約數(shù),寫出算法分析，畫出程序框圖，寫出算法程序.解：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)：8251=6105×1+2146.由此可得，6105與2146的公約數(shù)也是8251與6105的公約數(shù)，反過來，8251與6105的公約數(shù)也是6105與2146的公約數(shù)，所以它們的最大公約數(shù)相等.對6105與2146重復(fù)上述步驟：6105=2146×2+1813.同理，2146與1813的最大公約數(shù)也是6105與2146的最大公約數(shù).繼續(xù)重復(fù)上述步驟：2146=1813×1+333，1813=333×5+148，333=148×2+37，148=37×4.最后的除數(shù)37是148和37的最大公約數(shù)，也就是8251與6105的最大公約數(shù).這就是輾轉(zhuǎn)相除法.由除法的性質(zhì)可以知道，對于任意兩個正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除法求出兩個正整數(shù)的最大公約數(shù).算法分析：從上面的例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步驟，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法.算法步驟如下：第一步，給定兩個正整數(shù)m，n.第二步，計算m除以n所得的余數(shù)為r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.程序框圖如下圖：程序：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND點評：從教學(xué)實踐看，有些學(xué)生不能理解算法中的轉(zhuǎn)化過程，例如：求8251與6105的最大公約數(shù),為什么可以轉(zhuǎn)化為求6105與2146的公約數(shù).因為8251=6105×1+2146，可以化為8251-6105×1=2164，所以公約數(shù)能夠整除等式兩邊的數(shù)，即6105與2146的公約數(shù)也是8251與6105的公約數(shù).變式訓(xùn)練你能用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個正整數(shù)的最大公約數(shù)嗎？試畫出程序框圖和程序.解：當(dāng)型循環(huán)結(jié)構(gòu)的程序框圖如下圖：程序：INPUTm，nr=1WHILEr＞0r=mMODnm=nn=rWENDPRINTmEND例2用更相減損術(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.點評：更相減損術(shù)與輾轉(zhuǎn)相除法的比較：盡管兩種算法分別來源于東、西方古代數(shù)學(xué)名著，但是二者的算理卻是相似的，有異曲同工之妙．主要區(qū)別在于輾轉(zhuǎn)相除法進行的是除法運算，即輾轉(zhuǎn)相除；而更相減損術(shù)進行的是減法運算，即輾轉(zhuǎn)相減，但是實質(zhì)都是一個不斷的遞歸過程．變式訓(xùn)練用輾轉(zhuǎn)相除法或者更相減損術(shù)求三個數(shù)324,243,135的最大公約數(shù).解：324=243×1＋81，243=81×3＋0，則324與243的最大公約數(shù)為81.又135=81×1＋54，81=54×1＋27，54=27×2＋0，則81與135的最大公約數(shù)為27.所以,三個數(shù)324、243、135的最大公約數(shù)為27.另法：324－243=81,243－81=162,162－81=81，則324與243的最大公約數(shù)為81.135－81=54,81－54=27,54－27=27，則81與135的最大公約數(shù)為27.所以，三個數(shù)324、243.135的最大公約數(shù)為27.例3（1）用輾轉(zhuǎn)相除法求123和48的最大公約數(shù).（2）用更相減損術(shù)求80和36的最大公約數(shù).解：（1）輾轉(zhuǎn)相除法求最大公約數(shù)的過程如下：123＝2×48＋27，48＝1×27＋21，27＝1×21＋6，21＝3×6＋3，6＝2×3+0，最后6能被3整除，得123和48的最大公約數(shù)為3.（2）我們將80作為大數(shù)，36作為小數(shù)，因為80和36都是偶數(shù)，要除公因數(shù)2.80÷2=40，36÷2=18.40和18都是偶數(shù)，要除公因數(shù)2.40÷2=20，18÷2=9.下面來求20與9的最大公約數(shù)，20－9=11，11－9=2，9－2=7，7－2=5，5－2=3，3－2=1，2－1=1，可得80和36的最大公約數(shù)為22×1=4.點評：對比兩種方法控制好算法的結(jié)束，輾轉(zhuǎn)相除法是到達余數(shù)為0，更相減損術(shù)是到達減數(shù)和差相等.變式訓(xùn)練分別用輾轉(zhuǎn)相除法和更相減損術(shù)求1734，816的最大公約數(shù)．解：輾轉(zhuǎn)相除法：1734=816×2+102，816=102×8（余0），∴1734與816的最大公約數(shù)是102．更相減損術(shù)：因為兩數(shù)皆為偶數(shù)，首先除以2得到867，408，再求867與408的最大公約數(shù)．867-408=459，459-408=51，408-51=357，357-51=306，306-51=255，255-51=204，204-51=153，153-51=102，102-51=51.∴1734與816的最大公約數(shù)是51×2=102．利用更相減損術(shù)可另解：1734－816＝918，918－816＝102，816－102＝714，714－102＝612，612－102＝510，510－102＝408，408－102＝306，306－102＝204，204－102＝102.∴1734與816的最大公約數(shù)是102．知能訓(xùn)練求319，377，116的最大公約數(shù)．解：377=319×1+58，319=58×5+29，58=29×2.∴377與319的最大公約數(shù)為29，再求29與116的最大公約數(shù)．116=29×4.∴29與116的最大公約數(shù)為29.∴377，319，116的最大公約數(shù)為29.拓展提升試寫出利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的程序．解：更相減損術(shù)程序：INPUT“m，n=”；m，nWHILEm<>nIFm>nTHENｍ＝m-nELSEm=n-mENDIFWENDPRINTmEND課堂小結(jié)（1）用輾轉(zhuǎn)相除法求最大公約數(shù).（2）用更相減損術(shù)求最大公約數(shù).思想方法：遞歸思想.作業(yè)分別用輾轉(zhuǎn)相除法和更相減損術(shù)求261，319的最大公約數(shù).分析：本題主要考查輾轉(zhuǎn)相除法和更相減損術(shù)及其應(yīng)用．使用輾轉(zhuǎn)相除法可依據(jù)m=nq+r，反復(fù)執(zhí)行，直到r=0為止；用更相減損術(shù)就是根據(jù)m-n=r，反復(fù)執(zhí)行，直到n=r為止．解：輾轉(zhuǎn)相除法：319=261×1+58,261=58×4+29,58=29×2.∴319與261的最大公約數(shù)是29．更相減損術(shù)：319-