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

1 3中国古代数学中的算法案例 第一章算法初步 学习目标1 理解辗转相除法与更相减损术中的数学原理 并能根据这些原理进行算法分析 2 理解割圆术中蕴含的数学原理 3 了解秦九韶算法及利用它提高计算效率的本质 4 对简单的案例能设计程序框图并写出算法程序 题型探究 问题导学 内容索引 当堂训练 问题导学 知识点一更相减损术 更相减损术的运算步骤第一步 任意给定两个正整数 判断它们是否都是 若是 用约简 若不是 执行 第二步 以的数减去的数 接着把所得的差与的数比较 并以大数减小数 继续这个操作 直到所得的数为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 偶数 2 第二步 较大 较小 较小 相等 知识点二割圆术 1 割圆术的算法s1假设圆的半径为1 面积为s 圆内接正n边形面积为sn 边长为xn 边心距为hn 先从圆内接正六边形的面积开始算起 即n 6 则正六边形的面积s6 6 s2利用公式s2n sn n xn 1 hn 重复计算 就可得到正十二边形 正二十四边形 的面积 因为圆的半径为1 所以随着n的增大 s2n的值不断趋近于圆周率 这样不断计算下去 就可以得到越来越精密的圆周率近似值 2 割圆术的算法思想刘徽从圆内接正六边形开始 让边数逐次加倍 逐个算出这些圆内接正多边形的面积 从而得到一系列逐渐递增的数值 来一步一步地逼近圆面积 最后求出圆周率的近似值 用刘徽自己的话概括就是 割之弥细 所失弥少 割之又割 以至于不可割 则与圆合体而无所失矣 思考 知识点三秦九韶算法 衡量一个算法是否优秀的重要参数是速度 把多项式f x x5 x4 x3 x2 x 1变形为f x x 1 x 1 x 1 x 1 x 1 然后求当x 5时的值 为什么比常规逐项计算省时 从里往外计算 充分利用已有成果 可减少重复计算 答案 秦九韶算法的一般步骤 把一个n次多项式f x anxn an 1xn 1 a1x a0改写成如下形式 anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算一次多项式的值 即v1 然后由内向外逐层计算一次多项式的值 即v2 v3 vn 这样 求n次多项式f x 的值就转化为求的值 最内层括号内 梳理 anx an 1 v1x an 2 v2x an 3 vn 1x a0 n个一次多项式 题型探究 例1试用更相减损术求612 396的最大公约数 解答 类型一更相减损术 方法一612 2 306 396 2 198 306 2 153 198 2 99 153 99 54 99 54 45 54 45 9 45 9 36 36 9 27 27 9 18 18 9 9 所以612 396的最大公约数为9 22 36 方法二612 396 216 396 216 180 216 180 36 180 36 144 144 36 108 108 36 72 72 36 36 故36为612 396的最大公约数 用更相减损术的算法步骤 第一步 给定两个正整数m n 不妨设m n 第二步 若m n都是偶数 则不断用2约简 使它们不同时是偶数 约简后的两个数仍记为m n 第三步 d m n 第四步 判断 d n 是否成立 若是 则将n d中的较大者记为m 较小者记为n 返回第三步 否则 2kd k是约简整数2的个数 为所求的最大公约数 反思与感悟 跟踪训练1用更相减损术求261和319的最大公约数 解答 319 261 58 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 319与261的最大公约数为29 例2已知一个5次多项式为f x 4x5 2x4 3 5x3 2 6x2 1 7x 0 8 用秦九韶算法求这个多项式当x 5时的值 类型二秦九韶算法的基本思想 解答 将f x 改写为f x 4x 2 x 3 5 x 2 6 x 1 7 x 0 8 由内向外依次计算一次多项式当x 5时的值 v0 4 v1 4 5 2 22 v2 22 5 3 5 113 5 v3 113 5 5 2 6 564 9 v4 564 9 5 1 7 2826 2 v5 2826 2 5 0 8 14130 2 当x 5时 多项式的值等于14130 2 秦九韶算法之所以优秀 一是其对所有多项式求值都适用 二是充分利用已有计算成果 效率更高 反思与感悟 跟踪训练2用秦九韶算法求多项式f x 7x7 6x6 5x5 4x4 3x3 2x2 x当x 3时的值 f x 7x 6 x 5 x 4 x 3 x 2 x 1 x 所以有v0 7 v1 7 3 6 27 v2 27 3 5 86 v3 86 3 4 262 v4 262 3 3 789 v5 789 3 2 2369 v6 2369 3 1 7108 v7 7108 3 21324 故当x 3时 多项式f x 7x7 6x6 5x5 4x4 3x3 2x2 x的值为21324 解答 当堂训练 1 用秦九韶算法计算多项式f x 6x6 5x5 4x4 3x3 2x2 x 7在x 0 4时的值时 需做加法和乘法的次数的和为a 10b 9c 12d 8 2 3 1 f x 6x 5 x 4 x 3 x 2 x 1 x 7 做加法6次 乘法6次 6 6 12 次 故选c 答案 解析 2 已知f x 2x3 x 3 用秦九韶算法求当x 3时v2的值 f x 2x3 x 3 2x3 0 x2 x 3 2x 0 x 1 x 3 v0 2 v1 2 3 0 6 v2 6 3 1 19 解答 2 3 1 3 用更相减损术求1734和816的最大公约数 因为1734和816都是偶数 所以分别除以2得867和408 867 408 459 459 408 51 408 51 357 357 51 306 306 51 255 255 51 204 204 51 153 153 51 102 102 51 51 所以867和408的最大公约数是51 故1734和816的最大公约数是51 2 102 解答 2 3 1 规律与方法 1 更相减损术 就是