算法的基本思想第二课时

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 b 2ba 其算法步骤如下（要求近似解精确到其算法步骤如下（要求近似解精确到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;

16、4.由于由于 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

17、5)=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油油. 还有两