2019-2020年高中數學《1.3 算法案例》教案1 新人教A版必修3.doc

《2019-2020年高中數學《1.3 算法案例》教案1 新人教A版必修3.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中數學《1.3 算法案例》教案1 新人教A版必修3.doc（7頁珍藏版）》請在裝配圖網上搜索。

2019-2020年高中數學《1.3 算法案例》教案1 新人教A版必修3 教學分析 在學生學習了算法的初步知識，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結合典型算法案例，讓學生經歷設計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數學表達能力. 三維目標 1．理解算法案例的算法步驟和程序框圖. 2．引導學生得出自己設計的算法程序. 3. 體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數學表達能力. 重點難點 教學重點：引導學生得出自己設計的算法步驟、程序框圖和算法程序. 教學難點：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數學表達能力. 課時安排 3課時 教學過程 第1課時 案例1 輾轉相除法與更相減損術 導入新課 思路1（情境導入） 大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的.在小學，我們學過求兩個正整數的最大公約數的方法：先用兩個數公有的質因數連續(xù)去除，一直除到所得的商是互質數為止，然后把所有的除數連乘起來. 當兩個數公有的質因數較大時（如8 251與6 105），使用上述方法求最大公約數就比較困難.下面我們介紹兩種不同的算法——輾轉相除法與更相減損術,由此可以體會東、西方文化的差異. 思路2（直接導入） 前面我們學習了算法步驟、程序框圖和算法語句.今天我們將通過輾轉相除法與更相減損術來進一步體會算法的思想. 推進新課 新知探究 提出問題 （1）怎樣用短除法求最大公約數？ （2）怎樣用窮舉法（也叫枚舉法）求最大公約數？ （3）怎樣用輾轉相除法求最大公約數？ （4）怎樣用更相減損術求最大公約數？ 討論結果： （1）短除法 求兩個正整數的最大公約數的步驟：先用兩個數公有的質因數連續(xù)去除，一直除到所得的商是兩個互質數為止，然后把所有的除數連乘起來. （2）窮舉法（也叫枚舉法） 窮舉法求兩個正整數的最大公約數的解題步驟：從兩個數中較小數開始由大到小列舉，直到找到公約數立即中斷列舉，得到的公約數便是最大公約數. （3）輾轉相除法 輾轉相除法求兩個數的最大公約數，其算法步驟可以描述如下： 第一步，給定兩個正整數m，n. 第二步，求余數r：計算m除以n，將所得余數存放到變量r中. 第三步，更新被除數和余數：m=n，n=r. 第四步，判斷余數r是否為0.若余數為0，則輸出結果；否則轉向第二步繼續(xù)循環(huán)執(zhí)行. 如此循環(huán)，直到得到結果為止. 這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法. （4）更相減損術 我國早期也有解決求最大公約數問題的算法，就是更相減損術. 《九章算術》是中國古代的數學專著，其中的“更相減損術”也可以用來求兩個數的最大公約數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也.以等數約之.”翻譯為現代語言如下： 第一步，任意給定兩個正整數，判斷它們是否都是偶數，若是，用2約簡；若不是，執(zhí)行第二步. 第二步，以較大的數減去較小的數，接著把所得的差與較小的數比較，并以大數減小數，繼續(xù)這個操作，直到所得的數相等為止，則這個數（等數）或這個數與約簡的數的乘積就是所求的最大公約數. 應用示例 例1 用輾轉相除法求8 251與6 105的最大公約數,寫出算法分析，畫出程序框圖，寫出算法程序. 解：用兩數中較大的數除以較小的數，求得商和余數：8 251=6 1051+2 146. 由此可得，6 105與2 146的公約數也是8 251與6 105的公約數，反過來，8 251與6 105的公約數也是6 105與2 146的公約數，所以它們的最大公約數相等. 對6 105與2 146重復上述步驟：6 105=2 1462+1 813. 同理，2 146與1 813的最大公約數也是6 105與2 146的最大公約數.繼續(xù)重復上述步驟： 2 146=1 8131+333， 1 813=3335+148， 333=1482+37， 148=374. 最后的除數37是148和37的最大公約數，也就是8 251與6 105的最大公約數. 這就是輾轉相除法.由除法的性質可以知道，對于任意兩個正整數，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉相除法求出兩個正整數的最大公約數. 算法分析：從上面的例子可以看出，輾轉相除法中包含重復操作的步驟，因此可以用循環(huán)結構來構造算法. 算法步驟如下： 第一步，給定兩個正整數m，n. 第二步，計算m除以n所得的余數為r. 第三步，m=n，n=r. 第四步，若r=0，則m，n的最大公約數等于m；否則，返回第二步. 程序框圖如下圖： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 點評：從教學實踐看，有些學生不能理解算法中的轉化過程，例如：求8 251與6 105的最大公約數,為什么可以轉化為求6 105與2 146的公約數.因為8 251=6 1051+2 146， 可以化為8 251-6 1051=2 164，所以公約數能夠整除等式兩邊的數，即6 105與2 146的公約數也是8 251與6 105的公約數. 變式訓練 你能用當型循環(huán)結構構造算法，求兩個正整數的最大公約數嗎？試畫出程序框圖和程序. 解：當型循環(huán)結構的程序框圖如下圖： 程序： INPUT m，n r=1 WHILE r＞0 r=m MOD n m=n n=r WEND PRINT m END 例2 用更相減損術求98與63的最大公約數. 解：由于63不是偶數，把98和63以大數減小數，并輾轉相減，如下圖所示. 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公約數等于7. 點評：更相減損術與輾轉相除法的比較：盡管兩種算法分別于東、西方古代數學名著，但是二者的算理卻是相似的，有異曲同工之妙．主要區(qū)別在于輾轉相除法進行的是除法運算，即輾轉相除；而更相減損術進行的是減法運算，即輾轉相減，但是實質都是一個不斷的遞歸過程． 變式訓練 用輾轉相除法或者更相減損術求三個數324,243,135的最大公約數. 解：324=2431＋81， 243=813＋0， 則324與243的最大公約數為81. 又135=811＋54，81=541＋27， 54=272＋0， 則 81 與 135的最大公約數為27. 所以,三個數324、243、135的最大公約數為27. 另法：324－243=81,243－81=162,162－81=81，則324與243的最大公約數為81. 135－81=54,81－54=27,54－27=27，則81與135的最大公約數為27. 所以，三個數324、243.135的最大公約數為27. 例3 （1）用輾轉相除法求123和48的最大公約數. （2）用更相減損術求80和36的最大公約數. 解：（1）輾轉相除法求最大公約數的過程如下： 123＝248＋27， 48＝127＋21， 27＝121＋6， 21＝36＋3， 6＝23+0， 最后6能被3整除，得123和48的最大公約數為3. （2）我們將80作為大數，36作為小數，因為80和36都是偶數，要除公因數2. 802=40，362=18. 40和18都是偶數，要除公因數2. 402=20，182=9. 下面來求20與9的最大公約數， 20－9=11， 11－9=2， 9－2=7， 7－2=5， 5－2=3， 3－2=1， 2－1=1， 可得80和36的最大公約數為221=4. 點評：對比兩種方法控制好算法的結束，輾轉相除法是到達余數為0，更相減損術是到達減數和差相等. 變式訓練 分別用輾轉相除法和更相減損術求1 734，816的最大公約數． 解：輾轉相除法： 1 734=8162+102，816=1028（余0）， ∴1 734與816的最大公約數是102． 更相減損術：因為兩數皆為偶數，首先除以2得到867，408，再求867與408的最大公約數． 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. ∴1 734與816的最大公約數是512=102． 利用更相減損術可另解： 1 734－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. ∴1 734與816的最大公約數是102． 知能訓練 求319，377，116的最大公約數． 解：377=3191+58， 319=585+29， 58=292. ∴377與319的最大公約數為29，再求29與116的最大公約數． 116=294. ∴29與116的最大公約數為29. ∴377，319，116的最大公約數為29. 拓展提升 試寫出利用更相減損術求兩個正整數的最大公約數的程序． 解：更相減損術程序： INPUT “m，n=”；m，n WHILE m<>n IF m>n THEN ｍ＝m-n ELSE m=n-m END IF WEND PRINT m END 課堂小結 （1）用輾轉相除法求最大公約數. （2）用更相減損術求最大公約數. 思想方法：遞歸思想. 作業(yè) 分別用輾轉相除法和更相減損術求261，319的最大公約數. 分析：本題主要考查輾轉相除法和更相減損術及其應用．使用輾轉相除法可依據m=nq+r，反復執(zhí)行，直到r=0為止；用更相減損術就是根據m-n=r，反復執(zhí)行，直到n=r為止． 解：輾轉相除法： 319=2611+58, 261=584+29, 58=292. ∴319與261的最大公約數是29． 更相減損術： 319-261=58, 261-58=203, 203-58=145, 145-58=87, 87-58=29, 58-29=29, ∴319與261的最大公約數是29． 設計感想 數學不僅是一門科學，也是一種文化，本節(jié)的引入從東、西方文化的不同開始，逐步向學生滲透數學文化.從知識方面主要學習用兩種方法求兩個正整數的最大公約數，從思想方法方面，主要學習遞歸思想.本節(jié)設置精彩例題，不僅讓學生學到知識，而且讓學生進一步體會算法的思想，培養(yǎng)學生的愛國主義情操．