1、第 11 課時 5.4 算法案例重點難點 重點：通過案例分析，體會算法思想，熟練算法設計，進一步理解算法的基本思想，發展有條理的思考和 表 達能力，提高邏輯思維能力。難點：在分析案例的過程中設計規范合理的算法學習要求1. 理解剩余定理的內涵2. 能利用剩余定理解決“韓信點兵一孫子問題”【課堂互動】 歷史背景：韓信是秦末漢初的著名軍事家，據說有一次漢高祖劉邦在衛士的簇擁下來到練兵場，劉邦問韓信有什么辦法，不要逐個報數，就能知道場上士兵的人數。韓信先令士兵排成 3列縱隊，結果有2人多余；接著他立刻下令將隊形改為5列縱隊，這一改，又多岀3人；隨后他又下令改為7列縱隊，這一次又剩下 2人無法成整行。韓

2、信看此情形，立刻報告共有士兵2333人。眾人都愣了，不知韓信用什么辦法清點岀準確人數的。這個故事是否屬實，已無從查考，但這個故事卻引出一個著名的數學問題，即聞名世界的“孫子問題”。這種神機妙算，最早岀現在我國算經十書之一的孫子算經中，原文是：“今有物不知其數，二二數之剩二，五五數之剩二，七七數之剩二，問物幾何？答門：二I二。”所以人們將這種問題的通用解法稱為“孫子剩余定理”。【解析】“孫子問題”相當于求關于x, y, z的不定方程組m = 3x + 2< m = 5y + 3的正整數解。=7 z + 2根據題意，m應該滿足三個條件:m被3除后余2,即Mod (m3) = 2m被5除后余3

3、,即Mod(m,5) = 3m被7除后余2,即Mod (mJ) = 2在自然數中可能存在滿足條件的數，首先讓m=2開始檢驗條件，若三個條件中有任何一個不滿足，檢驗下一個數，即 m遞增1,如此循環下去，一直到 m滿足三個條件為止。這種解決問題的方法也稱為“窮舉法”，這種方法在利用計算機解決問題時非常有效，因為計算機最擅長重復機械的操作【流程圖】【偽代碼】m*-2End WhilePrint m【思考】上述算法只能求岀最小的滿足條件的數，如果要求岀10個滿足條件的數，程序要做何修改？你能否用數學上最小公倍數的知識分析岀解決該問題的方法嗎？可以這樣考慮：5和7的公倍數中能被 3除余2的最小的公倍數是

4、 35 ; 3和7的公倍數中能被 5除余3 的最小的公倍數是 63; 3和5的公倍數中能被 7除余2的最小的公倍數是 30;因此滿足條件的其中 的一個數 就應是35+63+30,為128,若減去3、5、7的最小公倍數105得23, 23就是滿足題目要求的最 小的數。你能畫岀這種算法的流程圖嗎？【解】算法流程圖如下：經典范例例古今中外，許多人致力于圓周率的研究與計算。我國東漢的數學家劉徽利用“割圓術”計算圓的面積及圓周率”。“割圓術”被稱為千古絕技，它的原理是用圓內接正多邊形的面積去逼近圓的面積。具體計算如下：在單位圓內作正六邊形，其面積記為Aj,邊長為在此基礎上作圓內接十二邊形，面積記為A?,

5、邊長為a2,，一直做下去，記該圓的內接正6x2n-'邊形面積為 A,邊長為山于所考慮的是單位圓，計算岀的人口的值即是圓周率”的一個近似值，且 n越大，人口與圓周率疋越接近。你能否設計一個算法，計算圓周率的近似值？思路點撥:01 圖可知 an+i =-2 - -A4 - an2 , An = 3 - 2n_2an_i , aj=l,【解n算法步驟如下：【追蹤訓練】1. m是一正整數，對兩個正整數 a,b，若a-b是加的倍數，則稱模 m同余,用符號a = b(Modm)表示.則a三5(Mod27)中，a的取值可能為()A.ll B.22C.27D.322. 有一堆圍棋子，五個五個地數，最后余下2個；七個七個地數，最后余下3個；九個九個地數，最后余下4個.請設計一種算法.求出這堆棋子至少有多少個.【解】算法如下：3.（ 李白買酒 ） 無事街上走，提壺去買酒，遇店加一倍，見花喝一斗，二遇店和花，喝光壺中酒. 設計求