数学必修三：14《算法案例》ppt课件

1、数学数学必修必修3（苏教版）（苏教版）第第1章算法初步章算法初步14算法案例算法案例情景切入情景切入 韩信是秦末汉初的著名军事家据说有一次汉高祖韩信是秦末汉初的著名军事家据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方刘邦问韩信有什么方法法，不要逐个报数不要逐个报数，就能知道场上的士兵的人数就能知道场上的士兵的人数 韩信先令士兵排成韩信先令士兵排成3列纵队列纵队，结果有结果有2人多余；接着人多余；接着立即下令将队形成为立即下令将队形成为5列纵队列纵队，这一改这一改，又多出又多出3人；随人；随后他又下令改为后他又下令改为7列纵队列纵队，这次又剩下这次又

2、剩下2人无法成整行人无法成整行 在场的人都哈哈大笑在场的人都哈哈大笑，以为韩信不能清点出准确，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵的人数，不料笑声刚落，韩信高声报告共有士兵2 333人众人听了一愣人众人听了一愣，不知道韩信用什么方法这么快就能不知道韩信用什么方法这么快就能得出正确的结果的同学们得出正确的结果的同学们，你知道吗？你知道吗？1理解辗转相除法与更相减损术求最大公约数的方法理解辗转相除法与更相减损术求最大公约数的方法2理解中国剩余定理在数学中的应用理解中国剩余定理在数学中的应用3理解二分法求方程的近似解的算法理解二分法求方程的近似解的算法 栏目链接栏目链接自

3、自 主主学学 习习1孙子剩余定理即孙子剩余定理即_，在近代数学和电子，在近代数学和电子计算机程序设计中有着广泛的应用计算机程序设计中有着广泛的应用2公元前公元前3世纪，欧几里得在世纪，欧几里得在原本原本中介绍的求两个正中介绍的求两个正整数的最大公约数的方法，称为整数的最大公约数的方法，称为_363与与231的最大公约数是的最大公约数是_中国剩余定理中国剩余定理欧几里得辗转相除法欧几里得辗转相除法21 栏目链接栏目链接 栏目链接栏目链接一、中国剩余定理要要 点点导导 航航 中国剩余定理，也称为孙子剩余定理该定中国剩余定理，也称为孙子剩余定理该定理在近代数学和电子计算机程序设计中有着广泛的理在近代

4、数学和电子计算机程序设计中有着广泛的应用应用 (1)剩余问题剩余问题 在整数除法里，一个数分别除以几个数，得到在整数除法里，一个数分别除以几个数，得到整数商后，均有剩余；已知各除数及其对应的余数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩从而要求出适合条件的这个被除数的问题，叫做剩余问题余问题 栏目链接栏目链接要要 点点导导 航航 (2)两个性质两个性质 性质性质1：几个数相加，如果只有一个加数不能被：几个数相加，如果只有一个加数不能被数数a整除，而其他加数均能被数整除，而其他加数均能被数a整除，那么它们的和整除，那么它们的和就不能被数就不能被数

5、a整除整除 如：如：10能被能被5整除，整除，15能被能被5整除，但整除，但7不能被不能被5整整除，所以除，所以(10157)不能被不能被5整除整除 性质性质2：二数不能整除，若被除数扩大：二数不能整除，若被除数扩大(或缩小或缩小)了了几倍，而除数不变，则其余数也同时扩大几倍，而除数不变，则其余数也同时扩大(或缩小或缩小)相相同的倍数同的倍数(余数必小于除数余数必小于除数) 栏目链接栏目链接要要 点点导导 航航 如：如：22731(224)71214(4)要余要余2，则，则222762；(229)728197(2)(要余要余5，则，则2257155) (3)中国剩余定理中国剩余定理 中国数学史

6、书上记载：在两千多年前的我国古代算书中国数学史书上记载：在两千多年前的我国古代算书孙子算经孙子算经中，有这样一个问题中，有这样一个问题(称为称为“物不知数物不知数”问问题题)及其解法及其解法： 栏目链接栏目链接要要 点点导导 航航 今有物不知其数，三三数之剩二；五五数之剩三；今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩七七数之剩二二问物几何？问物几何？ 答曰：二十三答曰：二十三 术曰：术曰：“三三数之剩二，置一百四十；五五数之剩三，三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十并之，得二百三十三，置六十三；七七数之剩二，置三十并之，得二百三十三，以二百一十减之

7、即得以二百一十减之即得” “ “术术”即解法书中还介绍了上述问题中余数为一的即解法书中还介绍了上述问题中余数为一的一般解法：凡三三数之剩一，则置七十；五五数之剩一，一般解法：凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上，以则置二十一；七七数之剩一，则置十五；一百六以上，以一百五减之即得一百五减之即得 栏目链接栏目链接要要 点点导导 航航 在明朝程大位著在明朝程大位著算术统宗算术统宗一书中，把上述一书中，把上述问题的基本解法，用诗句概括为问题的基本解法，用诗句概括为： 三人同行七十稀，五树梅花廿一枝，七子团圆正三人同行七十稀，五树梅花廿一枝，七子团圆正半

8、月，除百减五便得知半月，除百减五便得知 依定理译成算式为：依定理译成算式为： 702213152233，233105223. 这就是享誉中外的这就是享誉中外的“中国剩余定理中国剩余定理” (4)“物不知数物不知数”问题的算法分析与算法的流程问题的算法分析与算法的流程图与伪代码表示，请直接参见教材相关部分图与伪代码表示，请直接参见教材相关部分 栏目链接栏目链接要要 点点导导 航航 1辗转相除法辗转相除法 公元前公元前3世纪欧几里得在世纪欧几里得在原本原本中提出的：中提出的：“设设有不相等的二数，从大数中连续减去小数直到余数小于小有不相等的二数，从大数中连续减去小数直到余数小于小数，再从小数中连续

9、减去余数直到小于余数，这样一直下数，再从小数中连续减去余数直到小于余数，这样一直下去，若余数总是量不尽其前一个数，直到最后的余数为一去，若余数总是量不尽其前一个数，直到最后的余数为一个单位，则该二数互质个单位，则该二数互质”二、求两个正整数的最大公约数的算法二、求两个正整数的最大公约数的算法 栏目链接栏目链接要要 点点导导 航航 辗转相除法就是把给定的两个数，用较大的数除以辗转相除法就是把给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数，继续上较小的数，若余数不为零，则将余数和较小的数，继续上面的除法，直到余数为零，此时的除数就是所求的最大公面的除法，直到余数为零，此时的

10、除数就是所求的最大公约数约数 从算法思想我们可以看出，辗转相除法的基本步骤从算法思想我们可以看出，辗转相除法的基本步骤是用较大的数是用较大的数(用用a表示表示)除以较小的数除以较小的数(用用b表示表示)，得到：，得到：anbr(0rb) 由于这是一个反复执行的步骤，且执行的次数由余由于这是一个反复执行的步骤，且执行的次数由余数数r是否等于是否等于0决定，所以我们可以把它看作一个循环体，决定，所以我们可以把它看作一个循环体，用循环结构就可以实现其算法用循环结构就可以实现其算法 栏目链接栏目链接要要 点点导导 航航 2更相减损术更相减损术用更相减损术求两个正整数的最大公约数的过程与算法设用更相减损

11、术求两个正整数的最大公约数的过程与算法设计：对于给定的两个正整数，用较大的数减去较小的数，计：对于给定的两个正整数，用较大的数减去较小的数，接着将得到的差与较小的数比较，用这两个数中的较大的接着将得到的差与较小的数比较，用这两个数中的较大的数减去较小的数，继续上述的操作数减去较小的数，继续上述的操作(大数减小数大数减小数)，直到产，直到产生一对相等的数为止，那么这个数生一对相等的数为止，那么这个数(等数等数)就是所求的最大就是所求的最大公约数这是因为每次操作后所得的两数与前两数具有相公约数这是因为每次操作后所得的两数与前两数具有相同的最大公约数，而两数的值逐渐减小，经过有限步操作同的最大公约数

12、，而两数的值逐渐减小，经过有限步操作后一定可得相等的两数后一定可得相等的两数 栏目链接栏目链接要要 点点导导 航航 3“更相减损术更相减损术”与与“辗转相除法辗转相除法”的异同点的异同点 “ “更相减损术更相减损术”与与“辗转相除法辗转相除法”这两种算法分别这两种算法分别来源于东西方古代数学名著，但二者的算理确是相似的，来源于东西方古代数学名著，但二者的算理确是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但实质都是一个不断的递

13、归过程辗转相减，但实质都是一个不断的递归过程 辗转相除法的理论依据是：由辗转相除法的理论依据是：由anbr(ab)ranb得得a，b与与b，r有相同的公约数；更相减损术的理论有相同的公约数；更相减损术的理论依据是：由依据是：由abr(ab)abr得得a，b与与b，r 栏目链接栏目链接要要 点点导导 航航有相同的公约数所以，它们有相同的理论依据，有相同的公约数所以，它们有相同的理论依据，只不过一个用除法，另一个用减法罢了只不过一个用除法，另一个用减法罢了 栏目链接栏目链接要要 点点导导 航航三、二分法三、二分法 栏目链接栏目链接 栏目链接栏目链接典典 例例剖剖 析析分析：分析： 例例1我国我国算

14、经十书算经十书之一之一孙子算经孙子算经中有这中有这样一个问题：样一个问题：“今有物不知其数，三三数之剩二，五五今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二问物几何？数之剩三，七七数之剩二问物几何？”你能用程序解你能用程序解决这个问题吗？决这个问题吗？ 这个问题的通用解法称为这个问题的通用解法称为“孙子剩余定孙子剩余定理理”或或“中国剩余定理中国剩余定理”著名的著名的“韩信点兵问韩信点兵问题题”即为此例的应用即为此例的应用 栏目链接栏目链接 栏目链接栏目链接因此因此，可以让可以让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有一堆桃子不知数目，猴子第一天吃掉一半，有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一个，第二天照此办法，吃掉剩觉得不过瘾，又多吃了一个，第二天照此办法，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上剩下下桃子的一半另

16、加一个，天天如此，到第十天早上剩下一个桃子，问这堆桃子有多少个？一个桃子，问这堆桃子有多少个？ 栏目链接栏目链接典典 例例剖剖 析析 第十天桃子数：第十天桃子数：S101(个个)；第九天桃子数：第九天桃子数：S9(11)24(个个)；第八天桃子数：第八天桃子数：S8(14)210(个个)；第一天桃子数：第一天桃子数：S1(S21)2(个个)所以递推关系是所以递推关系是S101，Sn(Sn11)2，n1，2，9.故可用循环结构设计算法故可用循环结构设计算法解析：解析：流程图如右上图所示流程图如右上图所示答案：答案： 栏目链接栏目链接典典 例例剖剖 析析 例例2写出求两个正整数写出求两个正整数a，

17、b(ab)的最大公约数的的最大公约数的一个算法，并画出流程图，写出相应的伪代码一个算法，并画出流程图，写出相应的伪代码 利用辗转相除法利用辗转相除法，求出数列求出数列a a，b b，r r1 1，r r2 2，r rn n，0 0，这列数从第三项开始每项都是前两这列数从第三项开始每项都是前两项相除项相除( (小的除大的小的除大的) )所得的余数所得的余数，余数余数0 0的前一个的前一个r rn n即为即为a a和和b b的最大公约数的最大公约数分析：分析： 栏目链接栏目链接典典 例例剖剖 析析算法如下：算法如下：S1输入两个正整数输入两个正整数a，b(ab)；S2rab的余数；的余数；S3ab

18、，br；S4如果如果r0，转转S2；S5输出最大公约数输出最大公约数b.解析：解析： 栏目链接栏目链接典典 例例剖剖 析析伪代码如下：伪代码如下：Read a，bWhile mod(a，b)0rmod(a，b)abbrEnd WhilePrint b 栏目链接栏目链接流程图如下图所示：流程图如下图所示：典典 例例剖剖 析析规律总结：规律总结： 辗转相除法是解决求最大公约数的通法辗转相除法是解决求最大公约数的通法，也是解决求两个正整数最小公倍数的通法也是解决求两个正整数最小公倍数的通法，可以输入不，可以输入不同的同的a a、b b值值，先求两数的最大公约数先求两数的最大公约数典典 例例剖剖 析析

19、u变式训练变式训练 2下述伪代码输出的结果是下述伪代码输出的结果是_a375b85While Mod(a，b)0rMod(a，b)abbrEnd WhilePrint b 栏目链接栏目链接典典 例例剖剖 析析 伪代码是求伪代码是求375和和85的最大公约数的最大公约数37585435，8535215，351525，15530，375与与85的最大公约数是的最大公约数是5.解析：解析：5答案：答案： 栏目链接栏目链接典典 例例剖剖 析析 例例3 现有长度为现有长度为360 cm和和780 cm两种规格的钢筋两种规格的钢筋若干，要焊接一批正方体模型，问怎样才能保证正方若干，要焊接一批正方体模型，问

20、怎样才能保证正方体体积最大且不浪费？编写算法流程图，并写出相应体体积最大且不浪费？编写算法流程图，并写出相应的伪代码的伪代码 正方体的所有棱长都相等正方体的所有棱长都相等，故必须将钢筋剪故必须将钢筋剪裁成长度相等的钢筋条裁成长度相等的钢筋条，又必须不浪费又必须不浪费，这就说明必这就说明必须剪后无剩余须剪后无剩余，于是为了保证正方体的体积最大于是为了保证正方体的体积最大，剪剪的钢筋的最大长度为的钢筋的最大长度为360 cm360 cm和和780 cm780 cm的最大公约数的最大公约数，可用更相减损术求最大公约数可用更相减损术求最大公约数分析：分析： 栏目链接栏目链接典典 例例剖剖 析析 根据更

21、相减损术求根据更相减损术求780和和360的最大公约数的步的最大公约数的步骤如下：骤如下： 780360420， 42036060， 36060300， 30060240， 24060180， 18060120， 1206060， 60600.解析：解析： 栏目链接栏目链接典典 例例剖剖 析析则则60即为即为360和和780的最大公约数的最大公约数流程图如下图所示：流程图如下图所示： 栏目链接栏目链接典典 例例剖剖 析析伪代码如下：伪代码如下：Reada，bWhileabrabIfbrThen ab brElsearEnd IfEnd WhilePrintb 栏目链接栏目链接典典 例例剖剖 析

22、析 (1) (1)更相减损术的基本步骤是用较大的数更相减损术的基本步骤是用较大的数( (用用a a表示表示) )减去较小的数减去较小的数( (用用b b表示表示) )，每次操作后所得的两，每次操作后所得的两数与前两数具有相同的最大公约数，而两数的值逐渐减数与前两数具有相同的最大公约数，而两数的值逐渐减小，经过有限步操作后，总能得到相等的两个数，即求小，经过有限步操作后，总能得到相等的两个数，即求得两数的最大公约数得两数的最大公约数规律总结：规律总结： 栏目链接栏目链接典典 例例剖剖 析析 (2)辗转相除法进行的是除法运算辗转相除法进行的是除法运算，执行次数由执行次数由余数是否为余数是否为0决定

23、决定，更相减损术进行的是减法运算更相减损术进行的是减法运算，执执行次数由差数与较小的数是否相等决定行次数由差数与较小的数是否相等决定，二者实质都是二者实质都是一个不断递归的过程一个不断递归的过程，是一个反复执行的步骤是一个反复执行的步骤，因而用因而用循环结构就可实现其算法循环结构就可实现其算法 栏目链接栏目链接典典 例例剖剖 析析 3运行下面的伪代码，运行下面的伪代码，当输入当输入78和和36时，输出的结果是时，输出的结果是_u变式训练变式训练Reada，bWhileabIf ab ThenaabElsebbaEnd If End WhilePrint a 栏目链接栏目链接典典 例例剖剖 析析

24、 伪代码是求伪代码是求78与与36的最大公约数的最大公约数(78，36)(42，36)(6，36)(6，30)(6，24)(6，18)(6，12)(6，6)，所以所以78和和36的最的最大公约数为大公约数为6.解析：解析：6答案：答案： 栏目链接栏目链接典典 例例剖剖 析析 例例4 已知函数已知函数f(x)x25，写出求方程，写出求方程f(x)0在在2，3上的近似解上的近似解(精确到精确到0.001)的算法伪代码，并画的算法伪代码，并画出流程图出流程图 由题目可获取以下主要信息：由题目可获取以下主要信息：( (1)已知函数已知函数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