高中数学 1.3 算法案例课件 新人教A版必修3.ppt

高中数学 必修3 人教a版 1 3算法案例 学习目标 1 理解辗转相除法与更相减损术的含义 了解其执行过程 2 理解秦九韶算法的计算过程 并了解它提高计算效率的实质 3 理解进位制的概念 能进行不同进位制间的转化 4 了解进位制的程序框图和程序 知识链接 1 20和30的最大公约数为 2 在数学运算中 经常采用十进制 即 在生活中 也有其它进制 如每60分钟为1小时 即 3 已知函数f x x2 2x 1 计算f 1 的值时用了 次乘法和 次加法运算 当函数变为f x x 2 x 1 求f 1 时 用了1次乘法运算和 次加法运算 10 满十进一 60进制 2 2 2 预习导引 1 辗转相除法 1 辗转相除法 又叫欧几里得算法 是一种求两个正整数的 的古老而有效的算法 2 辗转相除法的算法步骤第一步 给定 第二步 计算 第三步 第四步 若r 0 则m n的最大公约数等于 否则 返回 最大公约数 两个正整数m n m除以n所得的余数r m n n r m 第二步 2 更相减损术第一步 任意给定两个正整数 判断它们是否都是 若是 用 若不是 执行 第二步 以 的数减去 的数 接着把所得的差与 的数比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 偶数 2约简 第二步 较大 较小 相等 较小 3 秦九韶算法把一个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 的值就转化为求 的值 n个一次多项式 最内层括号内 anx an 1 v1x an 2 v2x an 3 vn 1x a0 4 进位制进位制是人们为了 和 而约定的记数系统 满k进一 就是k进制 k进制的基数是k 把十进制转化为k进制数时 通常用除k取余法 计数 运算方便 要点一求两个正整数的最大公约数例1分别用辗转相除法和更相减损术求261和319的最大公约数 解法一 辗转相除法 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 29 29 0 所以319与261的最大公约数是29 规律方法1 利用辗转相除法求给定的两个数的最大公约数 即利用带余除法 用数对中较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的数对 再利用带余除法 直到大数被小数除尽 则这时的较小数就是原来两个数的最大公约数 2 利用更相减损术求两个正整数的最大公约数的一般步骤是 首先判断两个正整数是否都是偶数 若是 用2约简 也可以不除以2 直接求最大公约数 这样不影响最后结果 跟踪演练1用辗转相除法求80与36的最大公约数 并用更相减损术检验你的结果 解80 36 2 8 36 8 4 4 8 4 2 0 即80与36的最大公约数是4 验证 80 2 4036 2 1840 2 2018 2 920 9 1111 9 29 2 77 2 55 2 33 2 12 1 11 2 2 4所以80与36的最大公约数为4 要点二秦九韶算法例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 规律方法1 先将多项式写成一次多项式的形式 然后运算时从里到外 一步一步地做乘法和加法即可 这样比直接将x 2代入原式大大减少了计算量 若用计算机计算 则可提高运算效率 2 注意 当多项式中n次项不存在时 可将第n次项看作0 xn 跟踪演练2用秦九韶算法计算f x 6x5 4x4 x3 2x2 9x 需要加法 或减法 与乘法运算的次数分别为 a 5 4b 5 5c 4 4d 4 5答案d解析n次多项式需进行n次乘法 若各项均不为零 则需进行n次加法 缺一项就减少一次加法运算 f x 中无常数项 故加法次数要减少一次 为5 1 4 故选d 要点三进位制例3 1 把二进制数1110011 2 化为十进制数 2 将8进制数314706 8 化为十进制数 解 1 1110011 2 1 26 1 25 1 24 0 23 0 22 1 21 1 115 2 314706 8 3 85 1 84 4 83 7 82 0 81 6 80 104902 所以 化为十进制数是104902 规律方法1 将k进制转化为十进制的方法是 先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式 再按照十进制的运算规则计算出结果 2 十进制转化为k进制 采用除k取余法 也就是除基数 倒取余 跟踪演练3将八进制数74化成二进制数 解首先将八进制数74化成十进制数 74 8 7 81 4 80 60 10 然后再将十进制数60化成二进制数 所以60 10 111100 2 综上可得74 8 111100 2 1 两个整数490和910的最大公约数是 a 2b 10c 30d 70答案d解析 910 490 1 420 490 420 1 70 420 70 6 490与910的最大公约数是70 2 下列有可能是4进制数的是 a 5123b 6542c 3103d 4312答案c解析4进制数每位上的数字一定小于4 故选c 3 用秦九韶算法求多项式f x 7x6 6x5 3x2 2 当x 4时的值时 先算的是 a 4 4 16b 7 4 28c 4 4 4 64d 7 4 6 34答案d解析因为f x anxn an 1xn 1 a1x a0 anx an 1 x an 2 x a1 x a0 所以用秦九韶算法求多项式f x 7x6 6x5 3x2 2当x 4时的值时 先算的是7 4 6 34 4 2013 淮安高一检测 下列二进制数中最大的数是 a 111 2 b 1001 2 c 110 2 d 101 2 答案b解析据k进制数的位置原则知 四位数一定大于三位数 故选b 也可以先把它化为十进制数 再比较 5 用更相减损术求36与134的最大公约数 第一步应为 答案先除以2 得到18与67解析 36与134都是偶数 第一步应为 先除以2 得到18与67 1 求两个正整数的最大公约数的问题 可以用辗转相除法 也可以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b 这个式子 反复相减 直到r 0为止 2 秦九韶算法的关键在于把n次多项式转化为一次多项式 注