數(shù)學必修三：14《算法案例》ppt課件

1、數(shù)學數(shù)學必修必修3（蘇教版）（蘇教版）第第1章算法初步章算法初步14算法案例算法案例情景切入情景切入 韓信是秦末漢初的著名軍事家據(jù)說有一次漢高祖韓信是秦末漢初的著名軍事家據(jù)說有一次漢高祖劉邦在衛(wèi)士的簇擁下來到練兵場劉邦在衛(wèi)士的簇擁下來到練兵場，劉邦問韓信有什么方劉邦問韓信有什么方法法，不要逐個報數(shù)不要逐個報數(shù)，就能知道場上的士兵的人數(shù)就能知道場上的士兵的人數(shù) 韓信先令士兵排成韓信先令士兵排成3列縱隊列縱隊，結果有結果有2人多余；接著人多余；接著立即下令將隊形成為立即下令將隊形成為5列縱隊列縱隊，這一改這一改，又多出又多出3人；隨人；隨后他又下令改為后他又下令改為7列縱隊列縱隊，這次又剩下這次又

2、剩下2人無法成整行人無法成整行 在場的人都哈哈大笑在場的人都哈哈大笑，以為韓信不能清點出準確，以為韓信不能清點出準確的人數(shù)，不料笑聲剛落，韓信高聲報告共有士兵的人數(shù)，不料笑聲剛落，韓信高聲報告共有士兵2 333人眾人聽了一愣人眾人聽了一愣，不知道韓信用什么方法這么快就能不知道韓信用什么方法這么快就能得出正確的結果的同學們得出正確的結果的同學們，你知道嗎？你知道嗎？1理解輾轉相除法與更相減損術求最大公約數(shù)的方法理解輾轉相除法與更相減損術求最大公約數(shù)的方法2理解中國剩余定理在數(shù)學中的應用理解中國剩余定理在數(shù)學中的應用3理解二分法求方程的近似解的算法理解二分法求方程的近似解的算法 欄目鏈接欄目鏈接自

3、自 主主學學 習習1孫子剩余定理即孫子剩余定理即_，在近代數(shù)學和電子，在近代數(shù)學和電子計算機程序設計中有著廣泛的應用計算機程序設計中有著廣泛的應用2公元前公元前3世紀，歐幾里得在世紀，歐幾里得在原本原本中介紹的求兩個正中介紹的求兩個正整數(shù)的最大公約數(shù)的方法，稱為整數(shù)的最大公約數(shù)的方法，稱為_363與與231的最大公約數(shù)是的最大公約數(shù)是_中國剩余定理中國剩余定理歐幾里得輾轉相除法歐幾里得輾轉相除法21 欄目鏈接欄目鏈接 欄目鏈接欄目鏈接一、中國剩余定理要要 點點導導 航航 中國剩余定理，也稱為孫子剩余定理該定中國剩余定理，也稱為孫子剩余定理該定理在近代數(shù)學和電子計算機程序設計中有著廣泛的理在近代

4、數(shù)學和電子計算機程序設計中有著廣泛的應用應用 (1)剩余問題剩余問題 在整數(shù)除法里，一個數(shù)分別除以幾個數(shù)，得到在整數(shù)除法里，一個數(shù)分別除以幾個數(shù)，得到整數(shù)商后，均有剩余；已知各除數(shù)及其對應的余數(shù)，整數(shù)商后，均有剩余；已知各除數(shù)及其對應的余數(shù)，從而要求出適合條件的這個被除數(shù)的問題，叫做剩從而要求出適合條件的這個被除數(shù)的問題，叫做剩余問題余問題 欄目鏈接欄目鏈接要要 點點導導 航航 (2)兩個性質兩個性質 性質性質1：幾個數(shù)相加，如果只有一個加數(shù)不能被：幾個數(shù)相加，如果只有一個加數(shù)不能被數(shù)數(shù)a整除，而其他加數(shù)均能被數(shù)整除，而其他加數(shù)均能被數(shù)a整除，那么它們的和整除，那么它們的和就不能被數(shù)就不能被數(shù)

5、a整除整除 如：如：10能被能被5整除，整除，15能被能被5整除，但整除，但7不能被不能被5整整除，所以除，所以(10157)不能被不能被5整除整除 性質性質2：二數(shù)不能整除，若被除數(shù)擴大：二數(shù)不能整除，若被除數(shù)擴大(或縮小或縮小)了了幾倍，而除數(shù)不變，則其余數(shù)也同時擴大幾倍，而除數(shù)不變，則其余數(shù)也同時擴大(或縮小或縮小)相相同的倍數(shù)同的倍數(shù)(余數(shù)必小于除數(shù)余數(shù)必小于除數(shù)) 欄目鏈接欄目鏈接要要 點點導導 航航 如：如：22731(224)71214(4)要余要余2，則，則222762；(229)728197(2)(要余要余5，則，則2257155) (3)中國剩余定理中國剩余定理 中國數(shù)學史

6、書上記載：在兩千多年前的我國古代算書中國數(shù)學史書上記載：在兩千多年前的我國古代算書孫子算經孫子算經中，有這樣一個問題中，有這樣一個問題(稱為稱為“物不知數(shù)物不知數(shù)”問問題題)及其解法及其解法： 欄目鏈接欄目鏈接要要 點點導導 航航 今有物不知其數(shù)，三三數(shù)之剩二；五五數(shù)之剩三；今有物不知其數(shù)，三三數(shù)之剩二；五五數(shù)之剩三；七七數(shù)之剩七七數(shù)之剩二二問物幾何？問物幾何？ 答曰：二十三答曰：二十三 術曰：術曰：“三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置六十三；七七數(shù)之剩二，置三十并之，得二百三十三，置六十三；七七數(shù)之剩二，置三十并之，得二百三十三，以二百一十減之

7、即得以二百一十減之即得” “ “術術”即解法書中還介紹了上述問題中余數(shù)為一的即解法書中還介紹了上述問題中余數(shù)為一的一般解法：凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，一般解法：凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，則置二十一；七七數(shù)之剩一，則置十五；一百六以上，以則置二十一；七七數(shù)之剩一，則置十五；一百六以上，以一百五減之即得一百五減之即得 欄目鏈接欄目鏈接要要 點點導導 航航 在明朝程大位著在明朝程大位著算術統(tǒng)宗算術統(tǒng)宗一書中，把上述一書中，把上述問題的基本解法，用詩句概括為問題的基本解法，用詩句概括為： 三人同行七十稀，五樹梅花廿一枝，七子團圓正三人同行七十稀，五樹梅花廿一枝，七子團圓正半

8、月，除百減五便得知半月，除百減五便得知 依定理譯成算式為：依定理譯成算式為： 702213152233，233105223. 這就是享譽中外的這就是享譽中外的“中國剩余定理中國剩余定理” (4)“物不知數(shù)物不知數(shù)”問題的算法分析與算法的流程問題的算法分析與算法的流程圖與偽代碼表示，請直接參見教材相關部分圖與偽代碼表示，請直接參見教材相關部分 欄目鏈接欄目鏈接要要 點點導導 航航 1輾轉相除法輾轉相除法 公元前公元前3世紀歐幾里得在世紀歐幾里得在原本原本中提出的：中提出的：“設設有不相等的二數(shù)，從大數(shù)中連續(xù)減去小數(shù)直到余數(shù)小于小有不相等的二數(shù)，從大數(shù)中連續(xù)減去小數(shù)直到余數(shù)小于小數(shù)，再從小數(shù)中連續(xù)

9、減去余數(shù)直到小于余數(shù)，這樣一直下數(shù)，再從小數(shù)中連續(xù)減去余數(shù)直到小于余數(shù)，這樣一直下去，若余數(shù)總是量不盡其前一個數(shù)，直到最后的余數(shù)為一去，若余數(shù)總是量不盡其前一個數(shù)，直到最后的余數(shù)為一個單位，則該二數(shù)互質個單位，則該二數(shù)互質”二、求兩個正整數(shù)的最大公約數(shù)的算法二、求兩個正整數(shù)的最大公約數(shù)的算法 欄目鏈接欄目鏈接要要 點點導導 航航 輾轉相除法就是把給定的兩個數(shù)，用較大的數(shù)除以輾轉相除法就是把給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)，繼續(xù)上較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)，繼續(xù)上面的除法，直到余數(shù)為零，此時的除數(shù)就是所求的最大公面的除法，直到余數(shù)為零，此時的

10、除數(shù)就是所求的最大公約數(shù)約數(shù) 從算法思想我們可以看出，輾轉相除法的基本步驟從算法思想我們可以看出，輾轉相除法的基本步驟是用較大的數(shù)是用較大的數(shù)(用用a表示表示)除以較小的數(shù)除以較小的數(shù)(用用b表示表示)，得到：，得到：anbr(0rb) 由于這是一個反復執(zhí)行的步驟，且執(zhí)行的次數(shù)由余由于這是一個反復執(zhí)行的步驟，且執(zhí)行的次數(shù)由余數(shù)數(shù)r是否等于是否等于0決定，所以我們可以把它看作一個循環(huán)體，決定，所以我們可以把它看作一個循環(huán)體，用循環(huán)結構就可以實現(xiàn)其算法用循環(huán)結構就可以實現(xiàn)其算法 欄目鏈接欄目鏈接要要 點點導導 航航 2更相減損術更相減損術用更相減損術求兩個正整數(shù)的最大公約數(shù)的過程與算法設用更相減損

11、術求兩個正整數(shù)的最大公約數(shù)的過程與算法設計：對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，計：對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，接著將得到的差與較小的數(shù)比較，用這兩個數(shù)中的較大的接著將得到的差與較小的數(shù)比較，用這兩個數(shù)中的較大的數(shù)減去較小的數(shù)，繼續(xù)上述的操作數(shù)減去較小的數(shù)，繼續(xù)上述的操作(大數(shù)減小數(shù)大數(shù)減小數(shù))，直到產，直到產生一對相等的數(shù)為止，那么這個數(shù)生一對相等的數(shù)為止，那么這個數(shù)(等數(shù)等數(shù))就是所求的最大就是所求的最大公約數(shù)這是因為每次操作后所得的兩數(shù)與前兩數(shù)具有相公約數(shù)這是因為每次操作后所得的兩數(shù)與前兩數(shù)具有相同的最大公約數(shù)，而兩數(shù)的值逐漸減小，經過有限步操作同的最大公約數(shù)

12、，而兩數(shù)的值逐漸減小，經過有限步操作后一定可得相等的兩數(shù)后一定可得相等的兩數(shù) 欄目鏈接欄目鏈接要要 點點導導 航航 3“更相減損術更相減損術”與與“輾轉相除法輾轉相除法”的異同點的異同點 “ “更相減損術更相減損術”與與“輾轉相除法輾轉相除法”這兩種算法分別這兩種算法分別來源于東西方古代數(shù)學名著，但二者的算理確是相似的，來源于東西方古代數(shù)學名著，但二者的算理確是相似的，有異曲同工之妙主要區(qū)別在于輾轉相除法進行的是除法有異曲同工之妙主要區(qū)別在于輾轉相除法進行的是除法運算，即輾轉相除；而更相減損術進行的是減法運算，即運算，即輾轉相除；而更相減損術進行的是減法運算，即輾轉相減，但實質都是一個不斷的遞

13、歸過程輾轉相減，但實質都是一個不斷的遞歸過程 輾轉相除法的理論依據(jù)是：由輾轉相除法的理論依據(jù)是：由anbr(ab)ranb得得a，b與與b，r有相同的公約數(shù)；更相減損術的理論有相同的公約數(shù)；更相減損術的理論依據(jù)是：由依據(jù)是：由abr(ab)abr得得a，b與與b，r 欄目鏈接欄目鏈接要要 點點導導 航航有相同的公約數(shù)所以，它們有相同的理論依據(jù)，有相同的公約數(shù)所以，它們有相同的理論依據(jù)，只不過一個用除法，另一個用減法罷了只不過一個用除法，另一個用減法罷了 欄目鏈接欄目鏈接要要 點點導導 航航三、二分法三、二分法 欄目鏈接欄目鏈接 欄目鏈接欄目鏈接典典 例例剖剖 析析分析：分析： 例例1我國我國算

14、經十書算經十書之一之一孫子算經孫子算經中有這中有這樣一個問題：樣一個問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二問物幾何？數(shù)之剩三，七七數(shù)之剩二問物幾何？”你能用程序解你能用程序解決這個問題嗎？決這個問題嗎？ 這個問題的通用解法稱為這個問題的通用解法稱為“孫子剩余定孫子剩余定理理”或或“中國剩余定理中國剩余定理”著名的著名的“韓信點兵問韓信點兵問題題”即為此例的應用即為此例的應用 欄目鏈接欄目鏈接 欄目鏈接欄目鏈接因此因此，可以讓可以讓m m從從2 2開始檢驗開始檢驗，若三個條件中有任若三個條件中有任何一個不成立何一個不成立，則則m m遞增

15、遞增1 1，一直到一直到m m同時滿足三個同時滿足三個條件為止條件為止 欄目鏈接欄目鏈接解析：解析： 欄目鏈接欄目鏈接流程圖如下圖所示：流程圖如下圖所示：偽代碼如下：偽代碼如下：m2Whilemod(m，3)2 or mod(m，5)3 or mod(m，7)2 mm1End WhilePrint m 欄目鏈接欄目鏈接典典 例例剖剖 析析u變式訓練變式訓練 1有一堆桃子不知數(shù)目，猴子第一天吃掉一半，有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一個，第二天照此辦法，吃掉剩覺得不過癮，又多吃了一個，第二天照此辦法，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上剩下下桃子的一半另

16、加一個，天天如此，到第十天早上剩下一個桃子，問這堆桃子有多少個？一個桃子，問這堆桃子有多少個？ 欄目鏈接欄目鏈接典典 例例剖剖 析析 第十天桃子數(shù)：第十天桃子數(shù)：S101(個個)；第九天桃子數(shù)：第九天桃子數(shù)：S9(11)24(個個)；第八天桃子數(shù)：第八天桃子數(shù)：S8(14)210(個個)；第一天桃子數(shù)：第一天桃子數(shù)：S1(S21)2(個個)所以遞推關系是所以遞推關系是S101，Sn(Sn11)2，n1，2，9.故可用循環(huán)結構設計算法故可用循環(huán)結構設計算法解析：解析：流程圖如右上圖所示流程圖如右上圖所示答案：答案： 欄目鏈接欄目鏈接典典 例例剖剖 析析 例例2寫出求兩個正整數(shù)寫出求兩個正整數(shù)a，

17、b(ab)的最大公約數(shù)的的最大公約數(shù)的一個算法，并畫出流程圖，寫出相應的偽代碼一個算法，并畫出流程圖，寫出相應的偽代碼 利用輾轉相除法利用輾轉相除法，求出數(shù)列求出數(shù)列a a，b b，r r1 1，r r2 2，r rn n，0 0，這列數(shù)從第三項開始每項都是前兩這列數(shù)從第三項開始每項都是前兩項相除項相除( (小的除大的小的除大的) )所得的余數(shù)所得的余數(shù)，余數(shù)余數(shù)0 0的前一個的前一個r rn n即為即為a a和和b b的最大公約數(shù)的最大公約數(shù)分析：分析： 欄目鏈接欄目鏈接典典 例例剖剖 析析算法如下：算法如下：S1輸入兩個正整數(shù)輸入兩個正整數(shù)a，b(ab)；S2rab的余數(shù)；的余數(shù)；S3ab

18、，br；S4如果如果r0，轉轉S2；S5輸出最大公約數(shù)輸出最大公約數(shù)b.解析：解析： 欄目鏈接欄目鏈接典典 例例剖剖 析析偽代碼如下：偽代碼如下：Read a，bWhile mod(a，b)0rmod(a，b)abbrEnd WhilePrint b 欄目鏈接欄目鏈接流程圖如下圖所示：流程圖如下圖所示：典典 例例剖剖 析析規(guī)律總結：規(guī)律總結： 輾轉相除法是解決求最大公約數(shù)的通法輾轉相除法是解決求最大公約數(shù)的通法，也是解決求兩個正整數(shù)最小公倍數(shù)的通法也是解決求兩個正整數(shù)最小公倍數(shù)的通法，可以輸入不，可以輸入不同的同的a a、b b值值，先求兩數(shù)的最大公約數(shù)先求兩數(shù)的最大公約數(shù)典典 例例剖剖 析析

19、u變式訓練變式訓練 2下述偽代碼輸出的結果是下述偽代碼輸出的結果是_a375b85While Mod(a，b)0rMod(a，b)abbrEnd WhilePrint b 欄目鏈接欄目鏈接典典 例例剖剖 析析 偽代碼是求偽代碼是求375和和85的最大公約數(shù)的最大公約數(shù)37585435，8535215，351525，15530，375與與85的最大公約數(shù)是的最大公約數(shù)是5.解析：解析：5答案：答案： 欄目鏈接欄目鏈接典典 例例剖剖 析析 例例3 現(xiàn)有長度為現(xiàn)有長度為360 cm和和780 cm兩種規(guī)格的鋼筋兩種規(guī)格的鋼筋若干，要焊接一批正方體模型，問怎樣才能保證正方若干，要焊接一批正方體模型，問

20、怎樣才能保證正方體體積最大且不浪費？編寫算法流程圖，并寫出相應體體積最大且不浪費？編寫算法流程圖，并寫出相應的偽代碼的偽代碼 正方體的所有棱長都相等正方體的所有棱長都相等，故必須將鋼筋剪故必須將鋼筋剪裁成長度相等的鋼筋條裁成長度相等的鋼筋條，又必須不浪費又必須不浪費，這就說明必這就說明必須剪后無剩余須剪后無剩余，于是為了保證正方體的體積最大于是為了保證正方體的體積最大，剪剪的鋼筋的最大長度為的鋼筋的最大長度為360 cm360 cm和和780 cm780 cm的最大公約數(shù)的最大公約數(shù)，可用更相減損術求最大公約數(shù)可用更相減損術求最大公約數(shù)分析：分析： 欄目鏈接欄目鏈接典典 例例剖剖 析析 根據(jù)更

21、相減損術求根據(jù)更相減損術求780和和360的最大公約數(shù)的步的最大公約數(shù)的步驟如下：驟如下： 780360420， 42036060， 36060300， 30060240， 24060180， 18060120， 1206060， 60600.解析：解析： 欄目鏈接欄目鏈接典典 例例剖剖 析析則則60即為即為360和和780的最大公約數(shù)的最大公約數(shù)流程圖如下圖所示：流程圖如下圖所示： 欄目鏈接欄目鏈接典典 例例剖剖 析析偽代碼如下：偽代碼如下：Reada，bWhileabrabIfbrThen ab brElsearEnd IfEnd WhilePrintb 欄目鏈接欄目鏈接典典 例例剖剖 析

22、析 (1) (1)更相減損術的基本步驟是用較大的數(shù)更相減損術的基本步驟是用較大的數(shù)( (用用a a表示表示) )減去較小的數(shù)減去較小的數(shù)( (用用b b表示表示) )，每次操作后所得的兩，每次操作后所得的兩數(shù)與前兩數(shù)具有相同的最大公約數(shù)，而兩數(shù)的值逐漸減數(shù)與前兩數(shù)具有相同的最大公約數(shù)，而兩數(shù)的值逐漸減小，經過有限步操作后，總能得到相等的兩個數(shù)，即求小，經過有限步操作后，總能得到相等的兩個數(shù)，即求得兩數(shù)的最大公約數(shù)得兩數(shù)的最大公約數(shù)規(guī)律總結：規(guī)律總結： 欄目鏈接欄目鏈接典典 例例剖剖 析析 (2)輾轉相除法進行的是除法運算輾轉相除法進行的是除法運算，執(zhí)行次數(shù)由執(zhí)行次數(shù)由余數(shù)是否為余數(shù)是否為0決定

23、決定，更相減損術進行的是減法運算更相減損術進行的是減法運算，執(zhí)執(zhí)行次數(shù)由差數(shù)與較小的數(shù)是否相等決定行次數(shù)由差數(shù)與較小的數(shù)是否相等決定，二者實質都是二者實質都是一個不斷遞歸的過程一個不斷遞歸的過程，是一個反復執(zhí)行的步驟是一個反復執(zhí)行的步驟，因而用因而用循環(huán)結構就可實現(xiàn)其算法循環(huán)結構就可實現(xiàn)其算法 欄目鏈接欄目鏈接典典 例例剖剖 析析 3運行下面的偽代碼，運行下面的偽代碼，當輸入當輸入78和和36時，輸出的結果是時，輸出的結果是_u變式訓練變式訓練Reada，bWhileabIf ab ThenaabElsebbaEnd If End WhilePrint a 欄目鏈接欄目鏈接典典 例例剖剖 析析

24、 偽代碼是求偽代碼是求78與與36的最大公約數(shù)的最大公約數(shù)(78，36)(42，36)(6，36)(6，30)(6，24)(6，18)(6，12)(6，6)，所以所以78和和36的最的最大公約數(shù)為大公約數(shù)為6.解析：解析：6答案：答案： 欄目鏈接欄目鏈接典典 例例剖剖 析析 例例4 已知函數(shù)已知函數(shù)f(x)x25，寫出求方程，寫出求方程f(x)0在在2，3上的近似解上的近似解(精確到精確到0.001)的算法偽代碼，并畫的算法偽代碼，并畫出流程圖出流程圖 由題目可獲取以下主要信息：由題目可獲取以下主要信息：( (1)已知函數(shù)已知函數(shù)f(x)x25；(2)求方程求方程f(x)0在在2，3上的近似解；上的近似解；分析：分析： 欄目鏈接欄目鏈接典典 例例剖剖 析析(3)(3)精確到精確到0.001.0.001.解答本題可先回憶一下二分法求近似根的步驟解答本題可先回憶一下二分法求近似根的步驟，由步驟畫出流程圖由步驟畫出流程圖，然后再寫出算法的偽代碼然后再寫出算法的偽代碼 流程圖如下圖所示：流程圖如下圖所示：解析：解析： 欄目鏈接欄目鏈接典典 例例剖剖 析析 欄目鏈接欄目鏈接典典 例例剖剖 析析x12x23Dox0f(x1)x5f(x0)x5If f(x0)0Then Exit DoIf f(x1)f(x0)0The