高中数学 114算法案例课件 湘教版必修5.ppt

课标要求 1 理解辗转相除法与二分法及中国剩余定理的含义 了解其执行过程 2 掌握秦九韶算法的计算过程 并了解它提高计算效率的实质 11 4算法案例 自学导引1 辗转相除法是用于求的一种方法 所谓辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数 则这时的小数就是原来两个数的最大公约数 两个数的最大公约数 不为零 除尽 x0 x0 a x0 4 秦九韶算法是我国南宋数学家在他的代表作中提出的一种用于计算的方法 对于任意一元n次多项式 秦九韶算法的步骤是 首先将多项式改写为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 秦九韶 数学九章 一元n次多项式的值 an vk 1x an k 说明 计算时 首先计算最内层的括号 然后由内向外逐层计算 直到最外层的一个括号 然后加上常数项 利用上面方法求一元n次多项式值的计算量仅需n次乘法和n次加法 自主探究1 任意给定两个正整数 用辗转相除法和更相减损术是否都可以求它们的最大公约数 答案是 更相减损术与辗转相除法都能在有限步内结束 故均可以用来求两个正整数的最大公约数 2 秦九韶算法与直接计算相比有什么优缺点 2 秦九韶算法 利用秦九韶算法求上述f 5 时只需要进行4次乘法运算和5次加减运算即可 与直接计算相比大大节省了乘法运算的次数 还避免了对自变量x单独做幂的计算 而与系数一起逐步增长幂次 从而提高计算的精度 又如利用秦九韶算法求多项式f x anxn an 1xn 1 a1x a0的值时 通过转化把乘法运算的次数减少到最多n次 加减运算最多n次 预习测评1 用辗转相除法求36与134的最大公约数 第一步是 a 134 36 98b 134 3 36 26c 先除以2 得到18与67d 134 36 3 余26 答案b2 求数320和2400的最大公约数为 答案160 答案an k循环 要点阐释1 辗转相除法 1 所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时的较小的数就是原来两个数的最大公约数 2 算法步骤 以求两正整数a b的最大公约数为例 s1 输入两个正整数a b a b s2 把a b的余数赋予r s3 如果r 0 那么把b赋予a 把r赋予b 转到第二步 否则转到第四步 s4 输出最大公约数b 3 程序框图如图所示 4 程序 程序框图如图伪代码 程序框图 如图伪代码 4 秦九韶算法 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 s1 计算最内层anx an 1的值 将anx an 1的值赋给一个变量v1 为方便将an赋予变量v0 s2 计算 anx an 1 x an 2的值 可以改写为v1x an 2 将v1x an 2的值赋给一个变量v2 依次类推 即每一步的计算之后都赋予一个新值vk 即从最内层的括号到最外层括号的值依次赋予变量v1 v2 vk vn 第n步所求值vn vn 1x a0即为所求多项式的值 典例剖析题型一最大公约数的求法 例1 用辗转相除法求下列两组数的最大公约数 并用更相减损术检验你的结果 1 80 36 2 294 84 解 1 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 294 84 3 42 84 42 2 即294与84的最大公约数是42 验证 因为294与84都是偶数 可同时除以2 即取147与42的最大公约数后再乘2 147 42 105105 42 6363 42 2142 21 21所以294与84的最大公约数为21 2 42 方法点评使用辗转相除法 我们可依据a nb r这个式子 反复执行 直到r 0为止 用更相减损术就是根据r a b这个式子 反复执行 直到r b为止 1 求261 319的最大公约数 解法一 辗转相除法 319 261 1 58 261 58 4 29 58 29 2 319与261的最大公约数是29 法二 更相减损术 319 261 58261 58 203203 58 145145 58 8787 58 2958 29 29 319与261的最大公约数是29 题型二中国剩余定理及二分法 例2 写出下列程序框图的用途 并将其伪代码写出 2 写出用二分法求方程x2 2 0的近似解的一个算法 并假设所求近似解与精确解的差的绝对值不超过0 005 题型三秦九韶算法的应用 例3 用秦九韶算法求多项式f x 1 x 0 5x2 0 16667x3 0 04167x4 0 00833x5 当x 0 2时的值 解根据秦九韶算法 把多项式改写成如下形式 f x 0 00833x 0 04167 x 0 16667 x 0 5 x 1 x 1 按照从内到外的顺序依次计算一次多项式当x 0 2时的值 v0 0 00833 v1 0 00833 0 2 0 04167 0 04 v2 0 04 0 2 0 16667 0 15867 v3 0 15867 0 2 0 5 0 46827 v4 0 46827 0 2 1 0 90635 v5 0 90635 0 2 1 0 81873 所以当x 0 2时 多项式的值为0 81873 方法点评秦九韶算法减少了运算的次数 因此它是多项式求值的简捷方法 此类题目的易错点有二 一是初始值的确定 即v0 an 易错写成v0 a0 二是vk的计算 即vk vk 1x an k k 1 2 n 易错写成vk vk 1x ak 3 用秦九韶算法求多项式f x 8x7 5x6 3x4 2x 1当x 2时的值 解根据秦九韶算法 把多项式改写成如下形式 f x 8x7 5x6 0 x5 3x4 0 x3 0 x2 2x 1 8x 5 x 0 x 3 x 0 x 0 x 2 x 1 按照从内到外的顺序 依次计算一次多项式当x 2时的值 v0 8 v1 8 2 5 21 v2 21 2 0 42 v3 42 2 3 87 v4 87 2 0 174 v5 174 2 0 348 v6 348 2 2 698 v7 698 2 1 1397 所以当x 2时 多项式的值为1397 误区警示由于对秦九韶算法的步骤使用不当而致误 例4 f x 3x4 2x2 4x 2 求f 2 的值 错解 f x 3x2 2 x 4 x 2 v1 3 2 2 2 14 v2 14 2 4 24 v3 24 2 2 50 f 2 50 错因分析错解中v1中含有x的二次式 不符合 秦九韶算法 正解 f x 3