2016-2017年最新审定苏教版高中数学必修三:1.4《算法案例》ppt(精品课件)_图文


最新审定苏教版高中数学必修三精品课件 1. 4 算法案例 情景切入 韩信是秦末汉初的著名军事家.据说有一次 汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩 信有什么方法,不要逐个报数,就能知道场上的士 兵的人数. 韩信先令士兵排成 3 列纵队,结果有 2 人多余; 接着立即下令将队形成为 5 列纵队,这一改,又多 出 3 人;随后他又下令改为 7 列纵队,这次又剩下 2 人无法成整行. 在场的人都哈哈大笑,以为韩信不能清点出 准确的人数,不料笑声刚落,韩信高声报告共有士 兵2 333人.众人听了一愣,不知道韩信用什么方法 这么快就能得出正确的结果的.同学们,你知道吗? 1.理解辗转相除法与更相减损术求最大公约数的方 法. 2.理解中国剩余定理在数学中的应用. 3.理解二分法求方程的近似解的算法. 栏 目 链 接 自 主 学 习 1.孙子剩余定理即中国剩余定理 ______________,在近代数学和 电子计算机程序设计中有着广泛的应用. 2.公元前3世纪,欧几里得在《原本》中介绍的求 两个正整数的最大公约数的方法,称为 欧几里得辗转相除法 __________________. 21 3.63与231的最大公约数是__________. 栏 目 链 接 栏 目 链 接 要 点 导 航 一、中国剩余定理 中国剩余定理,也称为孙子剩余定 理.该定理在近代数学和电子计算机程序设计 中有着广泛的应用. 栏 目 链 接 (1)剩余问题. 在整数除法里,一个数分别除以几个数, 得到整数商后,均有剩余;已知各除数及其对 应的余数,从而要求出适合条件的这个被除数 的问题,叫做剩余问题. 要 点 导 航 (2)两个性质. 性质 1 :几个数相加,如果只有一个加数不 能被数a整除,而其他加数均能被数a整除,那么 它们的和就不能被数a整除. 如:10能被 5整除,15能被 5整除,但 7不能 被5整除,所以(10+15+7)不能被5整除. 性质2:二数不能整除,若被除数扩大(或缩 栏 目 链 接 小 ) 了几倍,而除数不变,则其余数也同时扩大 (或缩小)相同的倍数(余数必小于除数). 要 点 导 航 如:22÷7=3……1 (22×4)÷7=12……1×4(=4) [要余2,则22×2÷7=6……2;(22×9)÷7= 28……1×9-7(=2)] (要余5,则22×5÷7=15……5) (3)中国剩余定理. 栏 目 链 接 中国数学史书上记载:在两千多年前的我国古 代算书《孙子算经》中,有这样一个问题(称为“物 不知数”问题)及其解法: 要 点 导 航 今有物不知其数,三三数之剩二;五五数之剩 三;七七数之剩二问物几何? 答曰:二十三. 术曰:“三三数之剩二,置一百四十;五五数 之剩三,置六十三;七七数之剩二,置三十.并之, 得二百三十三,以二百一十减之即得.” 栏 目 链 接 “术”即解法.书中还介绍了上述问题中余数为 一的一般解法:凡三三数之剩一,则置七十;五五数 之剩一,则置二十一;七七数之剩一,则置十五;一 百六以上,以一百五减之即得. 要 点 导 航 在明朝程大位著《算术统宗》一书中,把 上述问题的基本解法,用诗句概括为: 三人同行七十稀,五树梅花廿一枝,七子 团圆正半月,除百减五便得知. 依定理译成算式为: 70×2+21×3+15×2=233,233-105×2 =23. 栏 目 链 接 这就是享誉中外的“中国剩余定理”. (4) “物不知数”问题的算法分析与算法的 流程图与伪代码表示,请直接参见教材相关部 分. 要 点 导 航 二、求两个正整数的最大公约数的算法 1.辗转相除法. 公元前3世纪欧几里得在《原本》中提出的: 栏 目 链 接 “设有不相等的二数,从大数中连续减去小数直到 余数小于小数,再从小数中连续减去余数直到小于 余数,这样一直下去,若余数总是量不尽其前一个 数,直到最后的余数为一个单位,则该二数互质.” 要 点 导 航 辗转相除法就是把给定的两个数,用较大的 数除以较小的数,若余数不为零,则将余数和较小 的数,继续上面的除法,直到余数为零,此时的除 数就是所求的最大公约数. 从算法思想我们可以看出,辗转相除法的基 本步骤是用较大的数 ( 用 a 表示 ) 除以较小的数 ( 用 b 表 栏 目 链 接 示),得到:a=nb+r(0≤r<b). 由于这是一个反复执行的步骤,且执行的次数 由余数 r 是否等于 0 决定,所以我们可以把它看作一 个循环体,用循环结构就可以实现其算法. 要 点 导 航 2.更相减损术. 用更相减损术求两个正整数的最大公约数的过程与 算法设计:对于给定的两个正整数,用较大的数减 去较小的数,接着将得到的差与较小的数比较,用 栏 目 链 接 这两个数中的较大的数减去较小的数,继续上述的 操作(大数减小数),直到产生一对相等的数为止,那 么这个数(等数)就是所求的最大公约数.这是因为每 次操作后所得的两数与前两数具有相同的最大公约 数,而两数的值逐渐减小,经过有限步操作后一定 可得相等的两数. 要 点 导 航 点. 3.“更相减损术”与“辗转相除法”的异同 “更相减损术”与“辗转相除法”这两种算 法分别来源于东西方古代数学名著,但二者的算理 确是相似的,有异曲同工之妙.主要区别在于辗转 相除法进行的是除法运算,即辗转相除;而更相减 损术进行的是减法运算,即辗转相减,但实质都是 栏 目 链 接 一个不断的递归过程. 辗转相除法的理论依据是:由 a=nb+r(a>b) ? r = a- nb得 a, b与 b, r 有相同的公约数;更相减 损术的理论依据是:由 a-b= r(a>b)? a= b+ r得 a, 要 点 导 航 有相同的公约数.所以,它们有相同的理论依 据,只不过一个用除法,另一个用减法罢了. 栏 目 链 接 要 点 导 航 三、二分法 用

相关文档

2015-2016年最新审定苏教版高中数学必修三:1.4《算法案例》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三:1.3.3《循环语句》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三:3.3《几何概型》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三:2.1.3《分层抽样》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三:3.4《互斥事件》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三:1.3.2《条件语句》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三-章末归纳提升【3】ppt(精品课件)
2015-2016年最新审定苏教版高中数学必修三:3.1.1《随机现象》ppt(精品课件)
2016-2017年最新审定苏教版高中数学必修三-章末归纳提升【2】ppt(精品课件)
2015-2016年最新审定苏教版高中数学必修三:2.1.2《系统抽样》ppt(精品课件)
电脑版
?/a>