141算法案例韓信點(diǎn)兵學(xué)案蘇教版必修3

1、第 11 課時(shí) 5.4 算法案例重點(diǎn)難點(diǎn) 重點(diǎn)：通過(guò)案例分析，體會(huì)算法思想，熟練算法設(shè)計(jì)，進(jìn)一步理解算法的基本思想，發(fā)展有條理的思考和 表 達(dá)能力，提高邏輯思維能力。難點(diǎn)：在分析案例的過(guò)程中設(shè)計(jì)規(guī)范合理的算法學(xué)習(xí)要求1. 理解剩余定理的內(nèi)涵2. 能利用剩余定理解決“韓信點(diǎn)兵一孫子問(wèn)題”【課堂互動(dòng)】 歷史背景：韓信是秦末漢初的著名軍事家，據(jù)說(shuō)有一次漢高祖劉邦在衛(wèi)士的簇?fù)硐聛?lái)到練兵場(chǎng)，劉邦問(wèn)韓信有什么辦法，不要逐個(gè)報(bào)數(shù)，就能知道場(chǎng)上士兵的人數(shù)。韓信先令士兵排成 3列縱隊(duì)，結(jié)果有2人多余；接著他立刻下令將隊(duì)形改為5列縱隊(duì)，這一改，又多岀3人；隨后他又下令改為7列縱隊(duì)，這一次又剩下 2人無(wú)法成整行。韓

2、信看此情形，立刻報(bào)告共有士兵2333人。眾人都愣了，不知韓信用什么辦法清點(diǎn)岀準(zhǔn)確人數(shù)的。這個(gè)故事是否屬實(shí)，已無(wú)從查考，但這個(gè)故事卻引出一個(gè)著名的數(shù)學(xué)問(wèn)題，即聞名世界的“孫子問(wèn)題”。這種神機(jī)妙算，最早岀現(xiàn)在我國(guó)算經(jīng)十書之一的孫子算經(jīng)中，原文是：“今有物不知其數(shù)，二二數(shù)之剩二，五五數(shù)之剩二，七七數(shù)之剩二，問(wèn)物幾何？答門：二I二?！彼匀藗儗⑦@種問(wèn)題的通用解法稱為“孫子剩余定理”?！窘馕觥俊皩O子問(wèn)題”相當(dāng)于求關(guān)于x, y, z的不定方程組m = 3x + 2< m = 5y + 3的正整數(shù)解。=7 z + 2根據(jù)題意，m應(yīng)該滿足三個(gè)條件:m被3除后余2,即Mod (m3) = 2m被5除后余3

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

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

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