算法案例辗转相除法与更相减损术秦九韶算法与进位制第一课时课件-数学高一必修3第一章算法初步1.3人教A版.ppt

目标导航 1 理解辗转相除法与更相减损术求最大公约数的方法 2 理解秦九韶算法中求多项式的值的步骤原理 3 能利用除k取余法把十进制数化为k进制数 1 辗转相除法的算法步骤第一步 给定两个正整数m n m n 第二步 计算 除以 所得的 数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于 否 则 返回第二步 m n 余 n 2 更相减损术的算法步骤第一步 任意给定两个正整数 判断它们是否都是偶数 若是用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把所得的差与 比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 较小的数 相等 3 秦九韶算法把一个n次多项式f x anxn an 1xn 1 a1x a0改写 成如下形式 anxn 1 an 1xn 2 a1 x a0 f x anxn an 1xn 1 a1x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算最内层括号内的一次多项式的值 即v1 anx an 1 然后由内向外逐层计算一次多项式的值 即 n 这样 求n次多项式f x 的值就转化为求 个一次多项式的值 v1 anx an 1 v2 v3 v2x an 3 vn v1x an 2 vn 1x a0 4 进位制 1 k进制数anan 1 a1a0 k 转化为十进制数为 2 把十进制数化为k进制数用 即把所给的十进制数除以 得到商数和余数 再用商数除以k 得到商数和余数 直到商数为 把上面各步所得的 从右到左排列 即得到k进制数 除k取余法 k 0 余数 ankn an 1kn 1 a1k a0 问题导思 1 如何求18与54的最大公约数 提示 短除法 2 要求6750与3492的最大公约数 上述法还好用吗 提示 数值太大 短除法不方便用 新课探究 知识1求两个正整数最大公约数的算法 1 更相减损之术 等值算法 用两个数中较大的数减去较小的数 再用和构成新的一对数 对这一对数再用减 以同样的操作一直做下去 直到产生 这个数就是最大公约数 2 辗转相除法 欧几里得算法 用较大的数除以较小的数所得的和 构成新的一对数 继续做上面的除法 直到 这个较小的数就是最大公约数 差数 较小的数 大数 小数 一对相等的数 余数 较小的数 大数被小数除尽 问题导思 1 怎样计算多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 统计所做的计算的种类及计算次数分别是什么 提示 f 5 55 54 53 52 5 1 3906 根据我们的计算统计可以得出我们共需要10次乘法运算 5次加法运算 知识2秦九韶算法 2 我们把多项式变形为f x x2 1 x 1 x 1 x x 1 再统计一下计算当x 5时的计算的种类及计算次数分别是什么 提示 从里往外计算仅需4次乘法和5次加法运算即可得出结果 1 把一元n次多项式P x anxn an 1xn 1 a1x a0改写为P x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 令vk anx an 1 x an k 1 x an k 2 计算P x0 的方法先计算 然后逐层计算 直到 然后加上 最内层括号 由内向外 最外层括号 常数项 知识3进位制 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 使用数字符号的个数称为基数 基数为n 即称为n进位制 简称n进制 现在最常用的是十进制 通常使用10个阿拉伯数字0 9进行记数 例1 分别用辗转相除法和等值算法求319和261的最大公约数 分析 使用辗转相除法可依据m nq r 反复执行 直到r 0为止 用等值算法是根据m n r 直到n 1为止 典例精讲 解析 辗转相除法 319 261 1 余58 261 58 4 余29 58 29 2 余0 所以319与261的最大公约数是29 等值算法 319 261 58 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 即 319 261 261 58 203 58 145 58 87 58 58 29 29 29 所以319与261的最大公约数是29 1 利用 等值算法 求给定的两个数的最大公约数 即多次利用减法 用数对中较大的数减去较小的数 直到相减的差与数对中较小的数相等为止 2 更相减损之术的步骤 1 判断两数是否都为偶数 若是 则都除以2直到所得两数不全为偶数 2 用较大的数减去较小的数 将差和较小的数构成一对新数 继续用较大数减去较小数 重复执行 3 当差和较小数相等时 结束执行 此时差 或较小数 为不全为偶数的两数的最大公约数 用 等值算法 更相减损之术 求下列两数的最大公约数 1 98 280 2 72 168 解 1 98 280 98 182 98 84 14 84 14 70 14 56 14 42 14 28 14 14 最大公约数为14 2 72 168 72 96 72 24 48 24 24 24 最大公约数为24 例2 用秦九韶算法计算多项式f x x6 12x5 60 x4 160 x3 240 x2 192x 64当x 2时的值 分析 解析 将f x 改写为f x x 12 x 60 x 160 x 240 x 192 x 64 由内向外依次计算一次多项式当x 2时的值 v0 1 v1 1 2 12 10 v2 10 2 60 40 v3 40 2 160 80 v4 80 2 240 80 v5 80 2 192 32 v6 32 2 64 0 f 2 0 即x 2时 原多项式的值为0 1 用秦九韶算法计算多项式的值时 要正确将多项式的形式进行改写 然后由内向外依次计算 当多项式函数中间出现空项式 要以系数为零的齐次项补充 2 秦九韶算法的步骤 变式训练 利用秦九韶算法计算多项式f x 11 5x 3x2 7x3在 x 23的值时 不会用到下列哪个值 D A 161 B 3772 C 86641 D 85169 解析 f x 11 5x 3x2 7x3 7x 3 x 5 x 11 所以当x 23时 v0 7 v1 7 23 3 161 3 164 v2 164 23 5 3772 5 3767 v3 3767 23 11 86641 11 86652 例3 求324 243 270三数的最大公约数 分析 先求324和243的最大公约数 再求这个数与270的最大公约数 解析 324 243 243 81 162 81 81 81 则324与243的最大公约数为81 又 270 81 189 81 108 81 81 27 54 27 27 27 则270与81的最大公约数为27 故324 243 270三数的最大公约数为27 求三个数的最大公约数 可先求两个数的最大公约数a 再求a与第三个数的最大公约数b 则b为所求的三个数的最大公约数 该题的解法可推广到求n个数的最大公约数 用更相减损之术求27090 21672 8127的最大公约数 解 先求27090与21672的最大公约数 27090 21672 21672 5418 16254 5418 10836 5418 5418 5418 27090与21672的最大公约数是5418 再求5418与8127的最大公约数 8127 5418 2709 5418 2709 2709 5418与8127的最大公约数为2709 27090 21672 8172的最大公约数为2709 类型4进制数之间的转化 例4 1 将101111011 2 转化为十进制数 2 将1231 5 转化为七进制数 分析 k进制数anan 1 a2a1a0 k 0 ai k 转化为十进制数 anan 1 a2a1a0 k an kn an 1 kn 1 a2 k2 a1 k a0 1 要将k进制数转化为n进制数 n k 10 可先将k进制数转化为十进制数 然后再转化为所求的n进制数 解析 1 101111011 2 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379 10 2 1231 5 1 53 2 52 3 5 1 191 10 1231 5 362 7 变式训练 3 填空 248 130 1 11111000 2 10 2 154 6 7 1 辗转相除法与更相减损术求最大公约数的区别与联系 课堂总结 2 秦九韶算法的优点 1 减少乘法运算的次数 2 规律性强 便于利用循环语句实现 3 不用对x做幂的运算 每次都是计算一个一次多项式的 值 提高了计算精度 3 进位制对于任何一个数 我们可以用不同的进位制来表示 比如 十进数57 可以用二进制表示为111001 也可以用八进制表示为71 用十六进制表示为39 它们所代表的数值都是一样的 表示各种进制数时 一般要在数字右下角加注来表示 如111001 2 表示二进制数 34 5 表示五进制数 电子计算机一般都使用二进制 1 用更相减损之术可求得78与36的最大公约数是 A 24B 18C 12D 6 解析 78 36 42 42 36 6 36 6 30 30 6 24 24 6 18 18 6 12 12 6 6 6为78与36的最大公约数 答案 D 当堂检测 2 用秦九韶算法计算f x 6x5 4x4 x3 2x2 x3 2x2 9x 需要加法 或减法 与乘法运算的次数分别为 A 5 4B 5 5C 4 4D 4 5 解析 n次多项式当最高次项的系数不为1时 需进行n次乘法 若各项均不为零 则需进行n次加法 缺一项就减少一次加法运算 f x 中无常数项 故加法次数要减少一次 为5 1 4 答案 D 3 用更相减损之术求81与135的最大公约数时 要进行 次减法运算 解析 135 81 54 81 54 27 54 27 27 共进行了3次减法运算 答案 3 4 将二进制数101101 2 化为