1、文檔編碼 : CX3O7W3N1K9 HW9M5S6S10L5 ZF6V9C4A10U3總 課 題名師精編優(yōu)秀教案總課時(shí)第 9 課時(shí)算法案例分 課 題算法案例分課時(shí)第 1 課時(shí)通過(guò)明白中國(guó)古代算法案例, 體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)學(xué)進(jìn)展的教學(xué)目標(biāo)貢獻(xiàn)重點(diǎn)難點(diǎn) 通過(guò)案例分析,體會(huì)算法思想,嫻熟算法設(shè)計(jì)例題剖析【案例 1】韓信是秦末漢初的著名軍事家,據(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、剩下 2 人無(wú)法成整行韓信看此情形,立刻報(bào)告共有士兵 2333 人眾人都愣了,不知韓信用什么方法清點(diǎn)出精確人數(shù)的這個(gè)故事是否屬實(shí),已無(wú)從查考, 但這個(gè)故事卻引出一個(gè)著名的數(shù)學(xué)問(wèn)題,即著名世界的“ 孫子問(wèn)題”這種神機(jī)妙算,最早顯現(xiàn)在我國(guó)算經(jīng)十書(shū)之一的孫子算經(jīng)中,原文是：“ 今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問(wèn)物幾何？答曰：二十三”所以人們將這種問(wèn)題的通用解法稱為“ 孫子剩余定理” 或“ 中國(guó)剩余定理”【算法設(shè)計(jì)思想】m 3 x 2“ 孫子問(wèn)題” 相當(dāng)于求關(guān)于 x,y,z 的不定方程組 m 5 y 3 的整數(shù)解m 7 z 2設(shè)所求的數(shù)為 m ,依據(jù)題意,m 應(yīng)同時(shí)中意以下三

3、個(gè)條件：（1） m被 3 除后余 2 ,即 Mod m,3 2；（2） m被 5 除后余 3 ,即 Mod m,5 3；（3） m被 7 除后余 2 ,即 Mod m,7 2；第一,從 m 2 開(kāi)頭檢驗(yàn)條件,如 3個(gè)條件中有任何一個(gè)不中意,就 m 遞增 1,當(dāng) m 同時(shí)中意 3 個(gè)條件時(shí),輸出 m 【流程圖】【偽代碼】名師精編 優(yōu)秀教案【案例 2】寫(xiě)出求兩個(gè)正整數(shù) a , b a b 的最大公約數(shù)的一個(gè)算法公元前 3 世紀(jì), 歐幾里得介紹了求兩個(gè)正整數(shù) a,b a b 的最大公約數(shù)的方法,即求出一列數(shù)：a,b,r 1,r 2,r n 1,r n,0,這列數(shù)從第三項(xiàng)開(kāi)頭,每一項(xiàng)都是前兩項(xiàng)相除所得

4、的余數(shù)（即 r n Mod r n 2,r n 1 ）,余數(shù)等于 0 的前一項(xiàng) nr ,即是 a 和 b 的最大公約數(shù),這種方法稱為“ 歐幾里得輾轉(zhuǎn)相除法”【算法設(shè)計(jì)思想】歐幾里得展轉(zhuǎn)相除法求兩個(gè)正整數(shù) a,b 的最大公約數(shù)的步驟是：運(yùn)算出 a b 的余數(shù)r ,如 r 0,就 b 即為 a,b 的最大公約數(shù)； 如 r 0,就把前面的除數(shù) b 作為新的被除數(shù),把余數(shù) r 作為新的除數(shù),連續(xù)運(yùn)算,直到余數(shù)為 0 ,此時(shí)的除數(shù)即為 a,b 的最大公約數(shù)求 a,b a b 的最大公約數(shù)的算法為：S 1 輸入兩個(gè)正整數(shù) a,b；S 2 假如 Mod a,b 0,那么轉(zhuǎn) S ,否就轉(zhuǎn) S 6；S 3 r

5、Mod a,b ；S 4 a b；S 5 b r,轉(zhuǎn) S 2；S 6 輸出 b 【流程圖】【偽代碼】【案例 3】寫(xiě)出方程x3x10在區(qū)間1,1內(nèi)的一個(gè)近似解（誤差不超過(guò)0 .001）的一個(gè)算法【算法設(shè)計(jì)思想】如下圖：假如設(shè)計(jì)出方程 f x 0 在某區(qū)間 a,b 內(nèi)有一個(gè)根 x,就能用二分搜尋求得符合誤差限制 c的近似解算法步驟可表示為：S 1 取 a,b 的中點(diǎn) x 0 1 a b ,將區(qū)間一分為二；2S 2 如 f x 0,就 0 x 就是方程的根,否就判定根 x 在 x 的左側(cè)仍是右側(cè)；如 f a f x 0 0,就 x x 0b ,以 x 代替 a ；如 f a f x 0 0,就 x

6、a , x 0 ,以 x 代替 b ；S 3 如 a b c,運(yùn)算終止,此時(shí) x 0 x,否就轉(zhuǎn) S 【流程圖】【偽代碼】名師精編 優(yōu)秀教案鞏固練習(xí)1下面一段偽代碼的目的是_ Readm , nmOa0yx0fxfb b0While mIntxnnm ncmnIntm n Endn cWhile Printnfa注明： 案例 3 的圖2在直角坐標(biāo)系中作出函數(shù)yx 2 和y4x的圖像,依據(jù)圖像判定方程2x4x的解的范疇,再用二分法求這個(gè)方程的近似解（誤差不超過(guò)0 .001）,并寫(xiě)出這個(gè)算法的偽代碼,畫(huà)出流程圖課堂小結(jié)通過(guò)案例分析, 體會(huì)算法思想, 嫻熟算法設(shè)計(jì),進(jìn)一步懂得算法的基本思想,在分析案

7、 例的過(guò)程中設(shè)計(jì)規(guī)范合理的算法名師精編 優(yōu)秀教案課后訓(xùn)練一基礎(chǔ)題班級(jí)：高二（）班姓名： _ 1一種放射性物質(zhì)不斷變化為其它物質(zhì),每經(jīng)過(guò)一年剩留下來(lái)的物質(zhì)的質(zhì)量約為原先,那么,約經(jīng)過(guò)多少年,剩留的質(zhì)量是原先的一半？試寫(xiě)出運(yùn)用二分法運(yùn)算這個(gè)近似值的偽代碼2設(shè)計(jì)一個(gè)算法,運(yùn)算兩個(gè)正整數(shù)a,b的最小公倍數(shù)二 提高題3判定某年份是否為閏年,要看此年份數(shù)能否被 4 整除如不能被 4 整除就是平年,2 月是 28 天；如能被 4 整除但不能被 100 整除,就該年是閏年,2 月是 29 天；如能被 4 整除又能被 100 整除, 仍要看能否被 400 整除, 如能就為閏年,否就為平年畫(huà)出上述算法的流程圖,并寫(xiě)出偽代碼4我國(guó)古代勞動(dòng)人民對(duì)不定方程的爭(zhēng)論作出過(guò)重要貢獻(xiàn),其中張丘建算經(jīng)中的“ 百雞問(wèn)題” 就是一個(gè)很有影響力的不定方程問(wèn)題,今有雞翁一值錢(qián)五,雞母一值錢(qián)三,雞雛三值錢(qián)一,凡百錢(qián)買(mǎi)百只,問(wèn)雞翁、雞母、雞雛各幾何其意思是：一只公雞的價(jià)格是 5 錢(qián),一只母雞的價(jià)格是 3 錢(qián),三只小雞的價(jià)格是 1錢(qián),想用 100 錢(qián)買(mǎi)100 只雞,問(wèn)公雞、母雞、小雞個(gè)買(mǎi)幾只設(shè) x,y,z 分別代表公雞、母雞、小雞的只數(shù),我們可以大致確定 x,y,z 的取值范疇：如 100 錢(qián)全買(mǎi)公雞,就最多可買(mǎi)