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

1 3中国古代数学中的算法案例 一 求两个正整数的最大公约数的算法 问题思考 1 试计算4与12 8与72 6与96的最大公约数 再计算一下4与12 4 8与72 8 6与96 6的最大公约数 通过比较 你能发现什么规律 提示 这两组的最大公约数均分别是4 8 6 由此可归纳出对于两个正整数a b a b a与b的最大公约数和b与a b的最大公约数相同 2 填空 1 等值算法 在我国古代也称为更相减损之术 它是用来求两个正整数的最大公约数的方法 其基本过程是 对于给定的两个数 用较大的数减去较小的数 接着把所得的差与较小的数比较 并以大数减去小数 继续这个操作 直到所得的两数相等为止 则所得数就是所求的最大公约数 2 辗转相除法 即欧几里得算法 是用较大的数除以较小的数所得的余数和较小的数构成新的一对数 继续做上面的除法 直到大数被小数除尽 这个较小的数就是最大公约数 3 辗转相除法与更相减损之术有何异同 提示 相同点 都是求最大公约数的方法 更相减损之术的理论依据为 由m n r 得m n r 可以看出 m n与n r有相同的公约数 辗转相除法的理论依据是 由m nq r可以看出 m n和n r有相同的公约数 即二者的 算理 相似 不同点 更相减损之术进行的是减法运算 辗转相除法进行的是除法运算 计算次数上辗转相除法计算次数相对较少 结果上 辗转相除法体现结果是以相除余数为0得到 而更相减损之术则以减数与差相等而得到 4 做一做 840和1764的最大公约数是 a 84b 12c 168d 252答案 a 二 割圆术 问题思考 1 填空 割圆术是我国魏晋时期的数学家刘徽在注 九章算术 中采用正多边形面积逐渐逼近圆面积的算法计算圆周率 的一种方法 他的思想后来又得到祖冲之的推进和发展 计算出的圆周率的近似值在世界上很长时间里处于领先地位 2 做一做 用圆内接正多边形逼近圆 因而得到的圆周率总是 的实际值 答案 小于 三 秦九韶算法 问题思考 1 填空 1 秦九韶算法是我国宋代数学家秦九韶在他的代表作 数学九章 中提出的一种用于计算多项式的值的方法 直到今天 这种算法仍是世界上多项式求值的最先进的算法 2 秦九韶算法适用于一般的多项式f x anxn an 1xn 1 a1x a0的求值问题 用秦九韶算法可把n次多项式的求值问题转化成求n个一次多项式的值的问题 即求v0 an v1 v0 x an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 提示 根据秦九韶算法知 v2 v1x an 2 v1 anx an 1 故v2 anx an 1 x an 2 3 为什么说秦九韶算法是多项式求值最先进的算法 4 做一做 已知f x x5 2x3 3x2 x 1 应用秦九韶算法计算x 3时的值时 v3的值为 答案 36 思考辨析判断下列说法是否正确 正确的在后面的括号内画 错误的画 1 用更相减损之术求294与84的最大公约数时 需要做5次减法 2 秦九韶算法是按照从内到外的顺序依次计算求值的 3 秦九韶算法适用所有函数的求函数值运算 答案 1 2 3 探究一 探究二 探究三 易错辨析 例1 分别用辗转相除法和更相减损之术求下列两数的最大公约数 1 261 319 2 1734 816 解 1 辗转相除法 319 261 1 余58 261 58 4 余29 58 29 2 余0 319与261的最大公约数是29 更相减损之术 261 319 261 58 203 58 145 58 87 58 29 58 29 29 319与261的最大公约数是29 探究一 探究二 探究三 易错辨析 2 辗转相除法 1734 816 2 余102 816 102 8 余0 1734与816的最大公约数是102 更相减损之术 因为两数皆为偶数 首先除以2得到867 408 再求867与408的最大公约数 867 408 459 408 51 408 51 357 51 306 51 255 51 204 51 153 51 102 51 51 1734与816的最大公约数是51 2 102 反思感悟用等值算法 更相减损之术 求两个数的最大公约数时 当大数减小数的差恰好等于小数时停止算法 这时的小数或差即所求最大公约数 用辗转相除法求两个数的最大公约数时 当大数除以小数的余数能整除这个小数时停止算法 这个余数即所求两数的最大公约数 探究一 探究二 探究三 易错辨析 变式训练1 1 用更相减损之术求36与135的最大公约数 需做减法的次数是 解析 135 36 99 36 63 36 27 36 27 9 18 9 9 9 故共进行了6次减法运算 答案 6 2 求140与76的最大公约数 解 方法一 利用更相减损之术 140 76 64 76 64 12 52 12 40 12 28 12 16 12 4 12 4 8 4 4 140与76的最大公约数为4 方法二 利用辗转相除法 140 76 64 76 64 12 4 12 140与76的最大公约数为4 探究一 探究二 探究三 易错辨析 例2 求1356和2400的最小公倍数 思路分析 两数的最小公倍数就是两数之积与此两数最大公约数的商 即解 2400 1356 1 1044 1356 1044 1 312 1044 312 3 108 312 108 2 96 108 96 1 12 96 12 8 1356与2400的最大公约数为12 探究一 探究二 探究三 易错辨析 反思感悟求两个正整数的最小公倍数要先求其最大公约数 两数的最小公倍数就是两数之积与两数最大公约数的商 并且这种方法也可以推广到n n 3 且n n 个数的情况 探究一 探究二 探究三 易错辨析 变式训练2求375与85的最小公倍数 解 375 85 4 35 85 35 2 15 35 15 2 5 15 5 3 0 375与85的最大公约数是5 375与85的最小公倍数是375 85 5 6375 探究一 探究二 探究三 易错辨析 例3 用秦九韶算法求多项式f x x5 0 11x3 0 15x 0 04当x 0 3时的值 思路分析 本题中有些项不存在 如x4 x2 要补上 写为0 x4 0 x2 将f x 写为f x x 0 x 0 11 x 0 x 0 15 x 0 04 按从内到外的顺序依次计算多项式的值 解 v0 1 v1 v0 0 3 0 0 3 v2 v1 0 3 0 11 0 2 v3 v2 0 3 0 0 06 v4 v3 0 3 0 15 0 132 v5 v4 0 3 0 04 0 0796 所以当x 0 3时 多项式的值为 0 0796 探究一 探究二 探究三 易错辨析 反思感悟1 应用秦九韶算法的关键是将一个n次多项式转化为n个一次多项式 转化要正确 2 计算时要由内向外逐次计算 由于下一次计算需要用到上一次的计算结果 故应认真 细心 确保中间结果的准确性 3 多项式中当有几项不存在 这些项的系数为0 时 应将这些项的系数看作0进行转化和计算 探究一 探究二 探究三 易错辨析 1 若本例中条件不变 求当x 2时 多项式的值 解 f x x 0 x 0 11 x 0 x 0 15 x 0 04 按从内到外的顺序 依次计算多项式的值 v0 1 v1 v0 2 0 2 v2 v1 2 0 11 4 11 v3 v2 2 0 8 22 v4 v3 2 0 15 16 29 v5 v4 2 0 04 32 54 所以当x 2时多项式的值为32 54 探究一 探究二 探究三 易错辨析 2 若本例中条件不变 改为求所用乘法和加法的次数是多少 解 根据秦九韶算法 把多项式写成如下形式 f x x 0 x 0 11 x 0 x 0 15 x 0 04 按从内到外的顺序 若x 0 3 则有v0 1 v1 v0 0 3 0 0 3 v2 v1 0 3 0 11 0 2 v3 v2 0 3 0 0 06 v4 v3 0 3 0 15 0 132 v5 v4 0 3 0 04 0 0796 故f 0 3 是通过5个一次多项式的值得到的 所以进行了5次乘法和5次加法 探究一 探究二 探究三 易错辨析 因对多项式改写不正确而致误 典例 已知多项式f x 3x5 2x2 5x4 3x3 x 则f 2 错解原式改写为f x 3x 2 x 5 x 3 x 1 x 于是v0 3 v1 3 2 2 4 v2 4 2 5 3 v3 3 2 3 9 v4 9 2 1 19 v5 19 2 38 故填38 探究一 探究二 探究三 易错辨析 正解f x 3x5 2x2 5x4 3x3 x 3x5 5x4 3x3 2x2 x 3x 5 x 3 x 2 x 1 x 于是v0 3 v1 3 2 5 1 v2 1 2 3 5 v3 5 2 2 8 v4 8 2 1 17 v5 17 2 34 所以当x 2时 多项式的值为34 答案34 探究一 探究二 探究三 易错辨析 防范措施解决此类问题的关键是要严格按照秦九韶算法的递推公式结构 并且事先将多项式f x 改写成所要求的形式 这样才能避免求值出错 对于本典例就是由于没有将f x 按x的降幂排列而导致计算出错 探究一 探究二 探究三 易错辨析 变式训练已知多项式f x 3x5 2x2 5x4 x 则f 2 等于 解析 f x 3x5 5x4 0 x3 2x2 x 3x 5 x 0 x 2 x 1 x 于是v0 3 v1 3 2 5 11 v2 11 2 0 22 v3 22 2 2 46 v4 46 2 1 93 v5 93 2 186 所以当x 2时 多项式的值为 186 答案 186 1 2 3 4 5 1 用 等值算法 可求得204与85的最大公约数是 a 15b 17c 51d 85解析 204 85 119 119 85 34 85 34 51 51 34 17 34 17 17 204和85的最大公约数是17 故选b 答案 b 1 2 3 4 5 2 我国数学家刘徽采用正多边形面积逐渐逼近圆面积的计算方法来求圆周率 其算法的特点为 a 运算速度快b 能计算出 的精确值c 内外夹逼 d 无限次地分割答案 c 1 2 3 4 5 3 用秦九韶算法求多项式f x x5 2x4 3x3 4x2 5x 6当x 7时的值时 需要做加法 乘法的次数分别是 a 6 6b 5 5c 5 4d 4 5答案 b 1 2 3 4 5 4 用秦九韶算法求多项式f x 0 5x5 4x4 3x2 x 1当x 3时的值 先算的是 a 3 3 9b 0 5 35 121 5c 0 5 3 4 5 5d 0 5 3 4 3 16 5解析 把多项式表示成如下形式 f x 0 5x 4 x 0 x 3 x 1 x 1 按递推方法 由内往外 先算0 5x 4的值 故选c 答案 c 1 2 3 4 5 5 用秦九韶算法计算多项式f x x6 12x