高中數學第11課時5.4算法案例學案新人教A版必修3

第11課時 5.4 算法案例 重點難點 重點：通過案例分析，體會算法思想，熟練算法設計，進一步理解算法的基本思想，發(fā)展有條理的思考和表達能力，提高邏輯思維能力。 難點：在分析案例的過程中設計規(guī)范合理的算法學習要求 1．理解剩余定理的內涵 2．能利用剩余定理解決“韓信點兵—孫子問題” 【課堂互動】 歷史背景： 韓信是秦末漢初的著名軍事家，據說有一次漢高祖劉邦在衛(wèi)士的簇擁下來到練兵場，劉邦問韓信有什么辦法，不要逐個報數，就能知道場上士兵的人數。 韓信先令士兵排成3列縱隊，結果有2人多余；接著他立刻下令將隊形改為5列縱隊，這一改，又多出3人；隨后他又下令改為7列縱隊，這一次又剩下2人無法成整行。韓信看此情形，立刻報告共有士兵2333人。 眾人都愣了，不知韓信用什么辦法清點出準確人數的。 這個故事是否屬實，已無從查考，但這個故事卻引出一個著名的數學問題，即聞名世界的“孫子問題”。 這種神機妙算，最早出現在我國《算經十書》之一的《孫子算經》中，原文是：“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？答曰：二十三。” 所以人們將這種問題的通用解法稱為“孫子剩余定理”。 【解析】 “孫子問題”相當于求關于x，y，z的不定方程組 的正整數解。 根據題意，m應該滿足三個條件： （1）m被3除后余2，即 （2）m被5除后余3，即 （3）m被7除后余2，即 在自然數中可能存在滿足條件的數，首先讓m=2開始檢驗條件，若三個條件中有任何一個不滿足，則檢驗下一個數，即m遞增1，如此循環(huán)下去，一直到m滿足三個條件為止。 這種解決問題的方法也稱為“窮舉法”，這種方法在利用計算機解決問題時非常有效，因為計算機最擅長重復機械的操作。 【流程圖】 N Y m←m+1 結束 輸出m 開始 1 m←2 【偽代碼】 m←2 End While Print m 【思考】 上述算法只能求出最小的滿足條件的數，如果要求出10個滿足條件的數，程序要做何修改？ 你能否用數學上最小公倍數的知識分析出解決該問題的方法嗎？ 可以這樣考慮：5和7的公倍數中能被3除余2的最小的公倍數是35；3和7的公倍數中能被5除余3的最小的公倍數是63；3和5的公倍數中能被7除余2的最小的公倍數是30；因此滿足條件的其中的一個數就應是35+63+30，為128，若減去3、5、7的最小公倍數105得23，23就是滿足題目要求的最小的數。 你能畫出這種算法的流程圖嗎？ 【解】算法流程圖如下: 輸出 且 且 開始 結束 經典范例 例 古今中外，許多人致力于圓周率的研究與計算。我國東漢的數學家劉徽利用“割圓術”計算圓的面積及圓周率?！案顖A術”被稱為千古絕技，它的原理是用圓內接正多邊形的面積去逼近圓的面積。具體計算如下： 在單位圓內作正六邊形，其面積記為A1，邊長為a1，在此基礎上作圓內接十二邊形，面積記為A2，邊長為a2,……，一直做下去，記該圓的內接正邊形面積為，邊長為。由于所考慮的是單位圓，計算出的的值即是圓周率的一個近似值，且越大，與圓周率越接近。你能否設計一個算法，計算圓周率的近似值？ 思路點撥:畫圖可知，，， 【解】算法步驟如下： 【追蹤訓練】 1. 是一正整數,對兩個正整數,若是的倍數,則稱模同余,用符號表示.則中,的取值可能為 ( 　 ) A.11 B.22 C.27 D.32 2.有一堆圍棋子,五個五個地數,最后余下2個；七個七個地數,最后余下3個；九個九個地數,最后余下4個.請設計一種算法,求出這堆棋子至少有多少個. 【解】 算法如下: 3.（李白買酒)無事街上走，提壺去買酒，遇店加一倍，見花喝一斗，三遇店和花，喝光壺中酒．設計求酒壺中原有多少酒的一個算法并寫出偽代碼． 【解】 算法如下: 4.求方程(其中為自然數)的所有小于100的的正整數解. 【解】 算法如下: 4 用心 愛心 專心