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

课标要求 1 理解辗转相除法与更相减损术的含义 了解其执行过程 2 理解秦九韶算法的计算过程 并了解它提高计算效率的实质 3 理解进位制的概念 能进行不同进位制间的转化 4 了解进位制的程序框图和程序 核心扫描 1 三种算法的原理及应用 重难点 2 三种算法的框图表示及程序 难点 3 不同进位制之间的相互转化 重点 4 秦九韶算法中多项式的改写 易错点 1 3算法案例 辗转相除法 1 辗转相除法 又叫欧几里得算法 是一种求两个正整数的 的古老而有效的算法 2 辗转相除法的算法步骤第一步 给定 第二步 计算 第三步 第四步 若r 0 则m n的最大公约数等于 否则 返回 自学导引 1 最大公约数 两个正整数m n m除以n所得的余数r m n n r m 第二步 更相减损术第一步 任意给定两个正整数 判断它们是否都是 若是 用 若不是 执行 第二步 以 的数减去 的数 接着把所得的差与 的数比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 任意给定两个正整数 用辗转相除法和更相减损术是否都可以求它们的最大公约数 提示是 更相减损术与辗转相除法都能在有限步内结束 故均可以用来求两个正整数的最大公约数 2 偶数 2约简 第二步 较小 较小 相等 较大 秦九韶算法把一个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 的值就转化为求 的值 3 最内层括号内 anx an 1 v1x an 2 v2x an 3 vn 1x a0 n个一次多项式 进位制进位制是人们为了 和 而约定的记数系统 满k进一 就是k进制 k进制的基数是k 把十进制转化为k进制数时 通常用除k取余法 不同进制间的数不能比较大小 对吗 提示不对 不同的进位制是人们为了计数和运算方便而约定的记数系统 不同进位制的数照样可比较大小 不过一般要转化到十进制下比较大小更方便一些 4 计数 运算方便 1 辗转相除法与更相减损术的区别和联系 名师点睛 秦九韶算法 1 特点 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做n次乘法和n次加法即可 2 算法步骤 设pn x anxn an 1xn 1 a1x a0 将其改写为pn x 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 第一步 计算最内层anx an 1的值 将anx an 1的值赋给一个变量v1 为方便将an赋予变量v0 第二步 计算 anx an 1 x an 2的值 可以改写为v1x an 2 将v1x an 2的值赋给一个变量v2 2 依次类推 即每一步的计算之后都赋予一个新值vk 即从最内层的括号到最外层 括号的值依次赋予变量v1 v2 vk vn 第n步所求值vn vn 1x a0即为所求多项式的值 3 秦九韶算法有以下几个优点 大大减少了乘法的次数 使计算量减小 在计算机上做一次乘法所需要的时间是做加法 减法的几倍到十几倍 减少做乘法的次数也就加快了计算的速度 规律性强 便于利用循环语句来实现算法 避免了对自变量x单独做幂的计算 每次都是计算一个一次多项式的值 从而可以提高计算的精度 关于进位制应注意的问题 1 十进制的原理是满十进一 一个十进制正整数n可以写成an 10n an 1 10n 1 a1 101 a0 100的形式 其中an an 1 a1 a0都是0至9中的数字 且an 0 例如365 3 102 6 10 5 2 一般地 k进制数的原理是满k进一 k进制数一般在右下角处标注 k 以示区别 例如270 8 表示270是一个8进制数 但十进制一般省略不写 3 在k进制中 有 有k个不同的数字符号 即0 1 2 3 k 1 逢k进一 即每位数计满k后向高位进一 一个k进位制的正整数就是各位数码与k的方幂的乘积的和 其中幂指数等于相应数码所在位数 从右往左数 减1 例如230451 k 2 k5 3 k4 0 k3 4 k2 5 k 1 3 题型一求两个正整数的最大公约数 分别用辗转相除法和更相减损术求261和319的最大公约数 思路探索 使用辗转相除法可依据m nq r 反复执行直到余数为0 更相减损术则是根据m n r 反复执行 直到n r为止 解法一 辗转相除法 319 261 1 余58 261 58 4 余29 58 29 2 余0 所以319与261的最大公约数为29 例1 法二 更相减损术 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 直接求最大公约数 这样不影响最后结果 用辗转相除法求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 变式1 将七进制数235 7 转化为八进制 解235 7 2 72 3 71 5 124 利用除8取余法 如图所示 所以124 174 8 所以235 7 转化为八进制数为174 8 题型二进位制之间的转化 例2 规律方法对于非十进制数之间的互化 通常是把这个数先转化为十进制数 然后再利用除k取余法 把十进制数转化为k进制数 而在使用除k取余法时要注意以下几点 1 必须除到所得的商是0为止 2 各步所得的余数必须从下到上排列 3 切记在所求数的右下角标明基数 把下列各数转换成十进制数 1 101101 2 2 2102 3 3 4301 6 解 1 101101 2 1 25 0 24 1 23 1 22 0 2 1 45 2 2102 3 2 33 1 32 2 65 3 4301 6 4 63 3 62 1 973 变式2 用秦九韶算法求f x 3x5 8x4 3x3 5x2 12x 6 当x 2的值 题型三秦九韶算法在多项式中的应用 例3 规范解答 根据秦九韶算法 把多项式改写成如下形式 f x 3x 8 x 3 x 5 x 12 x 6 按照从内到外的顺序 依次计算一次多项式当x 2时的值 2分 v0 3 v1 v0 2 8 3 2 8 14 4分 v2 v1 2 3 14 2 3 25 6分 v3 v2 2 5 25 2 5 55 8分 v4 v3 2 12 55 2 12 122 v5 v4 2 6 122 2 6 238 10分 所以当x 2时 多项式的值为238 12分 题后反思 1 先将多项式写成一次多项式的形式 然后运算时从里到外 一步一步地做乘法和加法即可 这样比直接将x 2代入原式大大减少了计算量 若用计算机计算 则可提高运算效率 2 注意 当多项式中n次项不存在时 可将第n次项看作0 xn 用秦九韶算法计算f x 6x5 4x4 x3 2x2 9x 需要加法 或减法 与乘法运算的次数分别为 a 5 4b 5 5c 4 4d 4 5解析n次多项式需进行n次乘法 若各项均不为零 则需进行n次加法 缺一项就减少一次加法运算 f x 中无常数项 故加法次数要减少一次 为5 1 4 故选d 答案d 变式3 已知f x x5 2x4 3x3 4x2 5x 6 用秦九韶算法求这个多项式当x 2时的值时 做了几次乘法 几次加法 错解 根据秦九韶算法 把多项式改写成如下形式f x x 2 x 3 x 4 x 5 x 6 按照从内到外的顺序 依次计算一次多项式当x 2时的值 v1 2 2 4 v2 2v1 3 11 v3 2v2 4 26 v4 2v3 5 57 v5 2v4 6 120 显然 在v1中未做乘法 只做了1次加法 在v2 v3 v4 v5中各做了1次加法 1次乘法 因此 共做了4次乘法 5次加法 误区警示对秦九韶算法中的运算次数理解错误 示例 在v1中虽然 v1 2 2 4 而计算机还是