1、第二課時第二課時復習回顧復習回顧1. 算法的概念算法的概念在數學中在數學中, 算法是解決某一類問題的一系列步驟或程序算法是解決某一類問題的一系列步驟或程序, 只要按照這些步驟執行只要按照這些步驟執行, 都能使問題得到解決都能使問題得到解決.2. 算法的特征算法的特征（1）確定性）確定性:算法的每一步應該是確定的算法的每一步應該是確定的, 能有效地執行且得能有效地執行且得到確定的結果到確定的結果, 而不應當模棱兩可而不應當模棱兩可.（2）順序性與正確性）順序性與正確性:算法從初始步驟開始算法從初始步驟開始, 分為若干明確的分為若干明確的步驟步驟, 前一步是后一步的前提前一步是后一步的前提, 只有

2、執行完前一步只有執行完前一步, 才能執行下才能執行下一步一步, 并且每一步都準確無誤并且每一步都準確無誤, 才能解決問題才能解決問題.（3）不唯一性）不唯一性:求解某一個問題的算法不一定是唯一的求解某一個問題的算法不一定是唯一的, 對于對于一個問題可以有不同的解法一個問題可以有不同的解法.（4）有限性）有限性:算法的步驟序列是有限的算法的步驟序列是有限的, 一個算法必須能夠在一個算法必須能夠在執行有限步之后結束執行有限步之后結束, 不能無限循環不能無限循環.3. 問題討論問題討論一個人帶著三只狼和三只羊過河一個人帶著三只狼和三只羊過河, 只有一條船只有一條船, 同船可容納同船可容納一個人和兩支

3、動物一個人和兩支動物, 沒有人在的時候沒有人在的時候, 如果狼的數量不少于羊的如果狼的數量不少于羊的數量狼就會吃羊數量狼就會吃羊. 該人如何將動物轉移過河該人如何將動物轉移過河?請你寫出解決問題請你寫出解決問題的步驟的步驟.參考答案參考答案算法步驟算法步驟:1.人帶兩只狼過河人帶兩只狼過河, 并自己返回并自己返回.2.人帶一只狼過河人帶一只狼過河, 自己返回自己返回.3.人帶兩只羊過河人帶兩只羊過河, 并帶兩只狼返回并帶兩只狼返回.4.人帶一只羊過河人帶一只羊過河, 自己返回自己返回.5.人帶兩只狼過河人帶兩只狼過河.1算法的基本思想算法的基本思想(2)一、具體算法案例分析一、具體算法案例分析

4、韓信像韓信像例例1. “韓信點兵韓信點兵”問題問題韓信是漢高祖劉邦手下的大將韓信是漢高祖劉邦手下的大將, 他英勇善他英勇善戰戰, 智謀超群智謀超群, 為建立漢朝立下汗馬功勞為建立漢朝立下汗馬功勞. 據說據說他在點兵的時候他在點兵的時候, 為了保住軍事機密為了保住軍事機密, 不讓敵不讓敵人知道自己部隊的實力人知道自己部隊的實力, 采用下述點兵方法采用下述點兵方法:先令士兵從先令士兵從13報數報數, 結果最后一個士兵報結果最后一個士兵報2; 再令士兵從再令士兵從15報數報數, 結果最后一個士兵報結果最后一個士兵報3; 又令士兵從又令士兵從17報數報數, 結果最后一個士兵報結果最后一個士兵報4. 這

5、樣這樣, 韓信很快就算出了自己部隊士兵的總人韓信很快就算出了自己部隊士兵的總人數數. 請設計一個算法請設計一個算法, 求出士兵求出士兵至少至少有多少人有多少人.?解解算法步驟如下算法步驟如下: 先令士兵從先令士兵從13報數，結果最后一個士兵報報數，結果最后一個士兵報2；再令士兵從；再令士兵從15報數，結果最后一個士兵報報數，結果最后一個士兵報3；又令士兵從；又令士兵從17報數，結果最報數，結果最后一個士兵報后一個士兵報4.請設計一個算法，求出士兵至少有多少人？請設計一個算法，求出士兵至少有多少人？1.首先確定最小的滿足除以首先確定最小的滿足除以3余余2的正整數：的正整數：2；2.依次加依次加3

6、得到所有除以得到所有除以3余余2的正整數：的正整數：2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 3.在上列數中確定最小的滿足除以在上列數中確定最小的滿足除以5余余3的數：的數：8；4.然后依次加上然后依次加上15，得到：，得到：8, 23, 38, 53, 5.在第在第4步得到的一列數中找出滿足除以步得到的一列數中找出滿足除以7余余4的最小數：的最小數：53, 這這 就是所求的數就是所求的數.這這5個步驟稱為解決個步驟稱為解決“韓信點兵韓信點兵”問題的一個算法問題的一個算法.解法二解法二 算法

7、步驟如下：算法步驟如下：1.首先確定最小的滿足除以首先確定最小的滿足除以7余余4的正整數：的正整數：4；2.依次加依次加7就得到所有除以就得到所有除以7余余4的正整數：的正整數：4, 11, 18, 25, 32, 39, 46, 53, 60, 3.在第在第2步得到的一列數中確定最小的除以步得到的一列數中確定最小的除以5余余3的數：的數：18；4.然后依次加上然后依次加上35, 得到：得到：18, 53, 88, 5.在第在第4步得到的一列數中找出最小的滿足除以步得到的一列數中找出最小的滿足除以3余余2的正整數：的正整數： 53.概括：同一個問題，可能有多種算法概括：同一個問題，可能有多種算

8、法. 先令士兵從先令士兵從13報數，結果最后一個士兵報報數，結果最后一個士兵報2；再令士兵從；再令士兵從15報數，結果最后一個士兵報報數，結果最后一個士兵報3；又令士兵從；又令士兵從17報數，結果最報數，結果最后一個士兵報后一個士兵報4.請設計一個算法，求出士兵至少有多少人？請設計一個算法，求出士兵至少有多少人？思思考以下問題的算法：考以下問題的算法：一位商人有一位商人有9 9枚銀元，其中有枚銀元，其中有1 1枚略輕的是假銀元。你枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？能用天平（不用砝碼）將假銀元找出來嗎？解解: 1.: 1.把銀元分成把銀元分成3 3組，每組組，每組3 3枚

9、。枚。 2 2先將兩組分別放在天平的兩邊。如果天先將兩組分別放在天平的兩邊。如果天平不平衡，那邊假銀元就放在輕的那一組；平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的如果天平左右平衡，則假銀元就在末稱的第第3 3組里。組里。3 3取出含假銀元的那一組，從中任取兩枚取出含假銀元的那一組，從中任取兩枚放在天平的兩邊。如果左右不平衡，則輕放在天平的兩邊。如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元。，則末稱的那一枚就是假銀元。 一位商人有一位商人有9枚銀元枚銀元, 其中有其中有1枚略輕的是假銀枚略輕

10、的是假銀元元, 你能用天平（不用砝碼）將假銀元找出來嗎？你能用天平（不用砝碼）將假銀元找出來嗎？解解 算法步驟如下：算法步驟如下：1.任取任取2枚銀元分分別放在天平的兩邊枚銀元分分別放在天平的兩邊. 如果天平左右不平衡如果天平左右不平衡, 則輕的一邊就是假銀圓則輕的一邊就是假銀圓; 如果天平平衡如果天平平衡, 則進行第則進行第2步步.2.取下右邊的銀圓取下右邊的銀圓, 放在一邊放在一邊, 然后把剩余的然后把剩余的7枚銀圓依次放在枚銀圓依次放在右邊進行稱量右邊進行稱量, 直到天平不平衡直到天平不平衡, 偏輕的那一枚就是假銀圓偏輕的那一枚就是假銀圓.例例2. “真假銀元真假銀元”問題問題思考思考:

11、這種算法最少要稱這種算法最少要稱_次次, 最多要稱最多要稱_次次.17 一位商人有一位商人有9枚銀元枚銀元, 其中有其中有1枚略輕的是假銀枚略輕的是假銀元元, 你能用天平（不用砝碼）將假銀元找出來嗎？你能用天平（不用砝碼）將假銀元找出來嗎？解解 算法步驟如下：算法步驟如下：1.將銀元分成將銀元分成3組，每組組，每組3枚；枚；2.先將兩組分別放在天平的兩邊先將兩組分別放在天平的兩邊, 如果天平不平衡如果天平不平衡, 那么假銀那么假銀元就在輕的那一組元就在輕的那一組; 如果天平左右平衡如果天平左右平衡, 則假銀元就在未稱的則假銀元就在未稱的那一組；那一組；3.取出含假銀元的那一組取出含假銀元的那一

12、組, 從中任取兩枚銀元放在天平的兩邊從中任取兩枚銀元放在天平的兩邊, 如果左右不平衡如果左右不平衡, 則輕的那一邊是假銀元則輕的那一邊是假銀元; 如果天平兩邊平衡如果天平兩邊平衡, 則未稱的那一枚是假銀元則未稱的那一枚是假銀元.概括概括: 算法有優劣之分算法有優劣之分, 在實際問題中在實際問題中, 找出好的算法是一項重找出好的算法是一項重要的工作要的工作.例例2. “真假銀元真假銀元”問題問題思考思考:這種算法只要稱這種算法只要稱_次次.22.二分法求方程二分法求方程 f(x)=0的近似解的基本思想是：的近似解的基本思想是： 將方程的有解區間平分為兩個小區間將方程的有解區間平分為兩個小區間,

13、然后判斷解在哪個小然后判斷解在哪個小區間區間; 繼續把有解的區間平分并進行判斷繼續把有解的區間平分并進行判斷, 直到求出滿足精度要直到求出滿足精度要求的近似解求的近似解.二、最優策略二、最優策略-二分法二分法1.當且僅當當且僅當_方程方程 f(x)=0在區間在區間a, b上有解上有解x=x0 xyoaby=f(x)x0( )( )0f af b2ba 其算法步驟如下（要求近似解精確到其算法步驟如下（要求近似解精確到10-n):1.確定有解區間確定有解區間a, b(f(a)f(b)0).2.取取a, b的中點的中點 .abx23.計算函數計算函數 f(x)在中點處的函數值在中點處的函數值 .()

14、abf24.判斷函數值判斷函數值 是否為零：是否為零：()abf2（1）若為若為0, 就是方程的解就是方程的解, 問題就得到解決；問題就得到解決； abx2（2）若不為）若不為0, 則分下列兩種情形：則分下列兩種情形：若若 , 則確定新的有解區間為則確定新的有解區間為 ;( )()abf af 02( ,)aba2 若若 , 則確定新的有解區間為則確定新的有解區間為 .( )()abf af 02(, )abb2 5.判斷新的有解區間的長度是否大于精度：判斷新的有解區間的長度是否大于精度：（1）若新的有解區間長度大于精度）若新的有解區間長度大于精度, 則在新的有解區間的基礎上重復上述步則在新的

15、有解區間的基礎上重復上述步驟驟;（2）如果新的有解區間長度小于或等于精度）如果新的有解區間長度小于或等于精度, 則這個有解區間中的任意一個則這個有解區間中的任意一個數均為方程的滿足精度的近似值數均為方程的滿足精度的近似值.xyoaby=f(x)x0例例3. .求方程求方程 在在0,10,1上的近似解上的近似解, ,精到精到0.1.0.1.3210 xx 解解算法步驟如下：算法步驟如下：1.1.因為因為 f(0)=-1, f(1)=1, f(0)f(1)0, 則區間則區間0, 1為有解區間為有解區間;2. .取取0,10,1的區間中點的區間中點0.5;3.計算計算 f(0.5)=-0.625;4

16、.由于由于 f(0.5)f(1)0, 可得新的有解區間可得新的有解區間0.5, 1,5.取取0.5, 1的區間中點的區間中點0.75;6.計算計算 f(0.75)=-0.015 625;7.因為因為 f(0.75)f(1)0, 可得新的有解區間可得新的有解區間0.75, 1,8.取取0.75, 1的區間中點的區間中點0.875;9.計算計算 f(0.875)=0.435 546 875;10.因為因為 f(0.75)f(0.875)0, 可得新的有解區間可得新的有解區間0.75, 0.875,11.取取0.75, 0.875的區間中點的區間中點0.812 5;12.計算計算 f(0.812 5

17、)=0.196 533 203 125;13.因為因為 f(0.75)f(0.812 5)0, 可得新的有解區間可得新的有解區間0.75, 0.812 5,區間區間0.75, 0.812 5中的任一數值中的任一數值, 都可以作都可以作為方程的近似解為方程的近似解.0.8125-0.75=0.062 50.1,概括：二分法主要用于一元非線性方程的近似解概括：二分法主要用于一元非線性方程的近似解.設設( ).321f xxx. ;10 50 50 1. ;10 750 250 1. ;0 8750 750 1250 1三、課堂練習三、課堂練習1.有一個圍棋子有一個圍棋子, 5個個5個地數個地數, 最后余下兩個最后余下兩個; 7個個7個地數個地數, 最后最后余下余下3個個; 9個個9個地數個地數, 最后余下最后余下4個個. 請設計一種算法請設計一種算法, 求出這把求出這把棋子至少有多少個棋子至少有多少個.2.一個大油瓶裝一個大油瓶裝8kg油油. 還有兩