高中数学 第一章 算法初步 1.3 中国古代数学中的算法案例课件 新人教B版必修3.ppt

1 3中国古代数学中的算法案例 1 理解中国古代三个问题 求两个正整数的最大公约数 割圆术 求多项式函数值 的算法 2 注意体会 更相减损之术 与 辗转相除法 的差异 以及秦九韶算法在求多项式函数值上的优越性 1 求两个正整数最大公约数的算法 1 等值算法 在我国古代也称为更相减损之术 它是用来求两个正整数的最大公约数的方法 其基本过程是 对于给定的两个数 用较大的数减去较小的数 接着把所得的差与较小的数比较 并以大数减去小数 继续这个操作 直到所得的两数相等为止 则所得数就是所求的最大公约数 2 辗转相除法 即欧几里得算法 是用较大的数除以较小的数所得的余数和较小的数构成新的一对数 继续做上面的除法 直到大数被小数除尽 这个较小的数就是所求的最大公约数 归纳总结1 用 等值算法 求两数的最大公约数时 是当大数减去小数的差恰好等于小数时停止减法 这时的小数就是要求的两数的最大公约数 2 求三个以上 含三个数 的数的最大公约数时 可依次通过求两个数的最大公约数与第三个数的最大公约数来求得 做一做1 用辗转相除法求168与72的最大公约数 要做n次除法运算 那么n为 a 2b 3c 4d 5答案 a 2 割圆术割圆术是我国魏晋时期的数学家刘徽在注 九章算术 中采用正多边形面积逐渐逼近圆面积的算法计算圆周率 的一种方法 他的思想后来又得到祖冲之的推进和发展 计算出的圆周率的近似值在世界上很长时间里处于领先地位 做一做2 用圆内接正多边形逼近圆 得到的圆周率的值总是 a 大于等于 的实际值b 大于 的实际值c 等于 的实际值d 小于 的实际值解析 用割圆术求出的是 的不足近似值 答案 d 知识拓展1 秦九韶算法很多文献称之为霍纳算法 2 用秦九韶算法计算多项式的值 关键是正确地将多项式改写 然后由内向外依次计算求得 1 辗转相除法与更相减损之术的异同剖析 相同点 都是求最大公约数的方法 更相减损之术的理论依据为 由m n r 得m n r 可以看出 m n与n r有相同的公约数 辗转相除法的理论依据是 由m nq r可以看出 m n和n r有相同的公约数 即二者的 算理 相似 不同点 更相减损之术进行的是减法运算 辗转相除法进行的是除法运算 计算次数上辗转相除法计算次数相对较少 结果上 辗转相除法体现结果是以相除余数为0得到 而更相减损之术则以减数与差相等而得到 3 教材中的 探索与研究 古希腊求两个正整数的最大公约数的方法是辗转相除法 即欧几里得算法 用较大的数除以较小的数所得的余数和较小的数构成新的一对数 继续做上面的除法 直到大数被小数除尽 这个较小的数就是最大公约数 以求288和123的最大公约数为例 操作如下 288 123 42 123 42 39 3 39 想一想这种算法的道理 试着编写程序在计算机上实现 剖析 辗转相除法求正整数a b a b 的最大公约数的步骤是 计算出a b的余数r 若r 0 则b为a b的最大公约数 若r 0 则把前面的除数b作为新的被除数 把余数r作为新的除数 继续运算 直到余数为零 此时的除数即为a b的最大公约数 从其算法思想我们可以看出 辗转相除法的基本步骤是用较大的数 用a表示 除以较小的数 用b表示 得到除式 a nb r 0 r b 由于这是一个反复执行的步骤 且执行的次数由余数r是否等于0决定 所以我们可以把它看做一个循环体 用循环结构就可以来实现其算法 程序略 题型一 题型二 题型三 题型一 题型二 题型三 反思用更相减损之术求解时 如果所给的两个正整数都是偶数时 那么一般先把这两个正整数除以2 最终把这两个正整数化成不都是偶数的情况 然后再用两数中较大的数减去较小的数 得到化简后两数的最大公约数 这时所求的最大公约数一定要注意 前面除了几个2 这时求出的最大公约数就要乘以几个2 题型一 题型二 题型三 题型一 题型二 题型三 题型一 题型二 题型三 反思先求最大公约数 因为两数的最小公倍数就是两数之积与两数最大公约数的商 所以这种方法也可以推广到n n 3 个数的情况 题型一 题型二 题型三 变式训练2 求396与270的最小公倍数 解 用辗转相除法求396与270的最大公约数 396 270 126 270 126 18 126 18 7 因此396与270的最大公约数为18 因此这两个数的最小公倍数为396 270 18 5940 题型一 题型二 题型三 题型一 题型二 题型三 反思有的同学习惯于常规解法 可能会直接代入求解 但这种算法计算机在执行时要进行21次乘法和6次加法运算 而利用秦九韶算法只需进行6次乘法 6次加法运算即可 要知道 让计算机进行一次乘法运算要比加法用的时间多很多 因此 要减少乘法运算的次数 这也就是秦九韶算法的优势所在了 题型一 题型二 题型三 变式训练3 求f x 5x5 2x4 3 5x3 2 6x2 1 7x 0 8当x 5时的函数值 解 由于f x 5x5 2x4 3 5x3 2 6x2 1 7x 0 8 5x 2 x 3 5 x 2 6 x 1 7 x 0 8 则v0 5 v1 5 5 2 27 v2 27 5 3 5 138 5 v3 138 5 5 2 6 689 9 v4 689 9 5 1 7 3451 2 v5 3451 2 5 0 8 17255 2 故当x 5时 多项式函数的值等于17255 2 随堂演练 即时巩固1我国数学家刘徽采用正多边形面积逐渐逼近圆面积的算法计算圆周率 这种算法称为 a 弧田法b 逼近法c 割圆术d 割图法解析 我国魏晋时期的数学家刘徽用割圆术的方法近似计算圆周率 答案 c 2840和1764的最大公约数是 a 84b 12c 168d 252解析 1764 840 924 840 84 840 84 756 84 672 84 588 84 504 84 420 84 336 84 252 84 168 84 84 故最大公约数是84 答案 a 3秦九韶算法能解决下列问题中的 a 求两个正整数的最大公约数b 多项式求值c 进位制的转化计算d 排序问题答案 b 4用辗转相除法求294和84的最大公约数时 需要做除法的次数是 a 1b 2c 3d 4解析 294 84 3 余42 84 42 2 余0 则最大公约数是42 故只做2次除法 答案 b 5利用秦九韶算法求当x 23时 多项式7x3 3x2 5x 11的值 s1x 23 s2y 7x3 3x2 5x 11 s3输出y s1x 23 s2y 7x 3 x 5 x 11 s3输出y 算6次乘法3次加法 算3次乘法3次加法 以上正确的描述为 填序号 答案 6用秦九韶算法求多项式f x x5 0 11x3 0 15x 0 04在x 0 3时的值 解 将f x 写为 f x x 0 x 0 11 x 0 x 0 15 x 0 0