蘇教版必修三第09課時《算法案例》word教案

1、文檔編碼 : CX3O7W3N1K9 HW9M5S6S10L5 ZF6V9C4A10U3總 課 題名師精編優(yōu)秀教案總課時第 9 課時算法案例分 課 題算法案例分課時第 1 課時通過明白中國古代算法案例, 體會中國古代數(shù)學對世界數(shù)學進展的教學目標貢獻重點難點 通過案例分析,體會算法思想,嫻熟算法設(shè)計例題剖析【案例 1】韓信是秦末漢初的著名軍事家,據(jù)說有一次漢高祖劉邦在衛(wèi)士的簇擁下來到練兵場,劉邦問韓信有什么方法,不要逐個報數(shù),就能知道場上士兵的人數(shù)韓信先令士兵排成 3 列縱隊,結(jié)果有 2 人余外；接著他立刻下令將隊形改為 5 列縱隊,這一改,又多出 3 人；隨后他又下令改為 7 列縱隊,這一次又

2、剩下 2 人無法成整行韓信看此情形,立刻報告共有士兵 2333 人眾人都愣了,不知韓信用什么方法清點出精確人數(shù)的這個故事是否屬實,已無從查考, 但這個故事卻引出一個著名的數(shù)學問題,即著名世界的“ 孫子問題”這種神機妙算,最早顯現(xiàn)在我國算經(jīng)十書之一的孫子算經(jīng)中,原文是：“ 今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何？答曰：二十三”所以人們將這種問題的通用解法稱為“ 孫子剩余定理” 或“ 中國剩余定理”【算法設(shè)計思想】m 3 x 2“ 孫子問題” 相當于求關(guān)于 x,y,z 的不定方程組 m 5 y 3 的整數(shù)解m 7 z 2設(shè)所求的數(shù)為 m ,依據(jù)題意,m 應(yīng)同時中意以下三

3、個條件：（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 開頭檢驗條件,如 3個條件中有任何一個不中意,就 m 遞增 1,當 m 同時中意 3 個條件時,輸出 m 【流程圖】【偽代碼】名師精編 優(yōu)秀教案【案例 2】寫出求兩個正整數(shù) a , b a b 的最大公約數(shù)的一個算法公元前 3 世紀, 歐幾里得介紹了求兩個正整數(shù) a,b a b 的最大公約數(shù)的方法,即求出一列數(shù)：a,b,r 1,r 2,r n 1,r n,0,這列數(shù)從第三項開頭,每一項都是前兩項相除所得

4、的余數(shù)（即 r n Mod r n 2,r n 1 ）,余數(shù)等于 0 的前一項 nr ,即是 a 和 b 的最大公約數(shù),這種方法稱為“ 歐幾里得輾轉(zhuǎn)相除法”【算法設(shè)計思想】歐幾里得展轉(zhuǎn)相除法求兩個正整數(shù) a,b 的最大公約數(shù)的步驟是：運算出 a b 的余數(shù)r ,如 r 0,就 b 即為 a,b 的最大公約數(shù)； 如 r 0,就把前面的除數(shù) b 作為新的被除數(shù),把余數(shù) r 作為新的除數(shù),連續(xù)運算,直到余數(shù)為 0 ,此時的除數(shù)即為 a,b 的最大公約數(shù)求 a,b a b 的最大公約數(shù)的算法為：S 1 輸入兩個正整數(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】寫出方程x3x10在區(qū)間1,1內(nèi)的一個近似解（誤差不超過0 .001）的一個算法【算法設(shè)計思想】如下圖：假如設(shè)計出方程 f x 0 在某區(qū)間 a,b 內(nèi)有一個根 x,就能用二分搜尋求得符合誤差限制 c的近似解算法步驟可表示為：S 1 取 a,b 的中點 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,運算終止,此時 x 0 x,否就轉(zhuǎn) S 【流程圖】【偽代碼】名師精編 優(yōu)秀教案鞏固練習1下面一段偽代碼的目的是_ Readm , nmOa0yx0fxfb b0While mIntxnnm ncmnIntm n Endn cWhile Printnfa注明： 案例 3 的圖2在直角坐標系中作出函數(shù)yx 2 和y4x的圖像,依據(jù)圖像判定方程2x4x的解的范疇,再用二分法求這個方程的近似解（誤差不超過0 .001）,并寫出這個算法的偽代碼,畫出流程圖課堂小結(jié)通過案例分析, 體會算法思想, 嫻熟算法設(shè)計,進一步懂得算法的基本思想,在分析案

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