高中数学 第一章 算法初步 1.3 算法与案例 1.3.1 算法案例课件 新人教A版必修3.ppt

第1课时辗转相除法与更相减损术 秦九韶算法 1 理解辗转相除法与更相减损术的步骤 了解其执行过程 并会求最大公约数 2 掌握秦九韶算法 了解它提高计算效率的实质 并会求多项式的值 3 进一步体会算法的基本思想 1 辗转相除法与更相减损术 1 辗转相除法 算法步骤 第一步 给定两个正整数m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 程序框图 程序 inputm ndor mmodnm nn rloopuntilr 0printmend 2 更相减损术 算法分析 第一步 任意给定两个正整数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的差与减数相等为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 做一做1 用更相减损术求156和48的最大公约数时 第一步是 答案 用2约简 2 秦九韶算法 1 概念 求多项式f x anxn an 1xn 1 a1x a0的值时 常用秦九韶算法 这种算法的运算次数较少 是多项式求值比较先进的算法 其实质是转化为求n个一次多项式的值 共进行n次乘法运算和n次加法运算 其过程是 改写多项式为 f 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 设v1 anx an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 2 算法步骤 第一步 输入多项式的次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 3 程序框图 4 程序 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 做一做2 用秦九韶算法求f x 2x3 x 3当x 3时的值的过程中 v2 解析 f x 2x 0 x 1 x 3 v0 2 v1 2 3 0 6 v2 6 3 1 19 答案 19 1 更相减损术与辗转相除法的区别与联系剖析 如表所示 2 秦九韶算法是比较先进的算法剖析 同一个问题有多种算法 如果某个算法比其他算法的步骤少 运算的次数少 那么这个算法就是比较先进的算法 判断算法是否先进的一个重要标志就是运算的次数越少越好 求多项式f x anxn an 1xn 1 a1x a0的值时 通常是先计算anxn 进行n次乘法运算 再计算an 1xn 1 进行n 1次乘法运算 这样继续下去 但是用秦九韶算法时 改写多项式为f 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 先计算v1 anx an 1 需1次乘法运算 1次加法运算 v2 v1x an 2 需1次乘法运算 1次加法运算 vn vn 1x a0 需1次乘法运算 1次加法运算 所以需进行n次乘法运算 n次加法运算 共进行2n次运算 因此说秦九韶算法与其他算法相比运算次数少 秦九韶算法是比较先进的算法 题型一 题型二 题型三 例1 1 用辗转相除法求840与1785的最大公约数 2 用更相减损术求612与468的最大公约数 分析 本题是关于辗转相除法和更相减损术的直接应用 辗转相除法的操作是较大的数除以较小的数 更相减损术的操作是以大数减小数 解 1 用辗转相除法求840和1785的最大公约数 1785 840 2 105 840 105 8 所以840和1785的最大公约数是105 题型一 题型二 题型三 2 首先612和468都是偶数 所以用2约简 得到306和234 还是偶数 需要再用2约简 得到153和117 最后用更相减损术计算得153 117 36 117 36 81 81 36 45 45 36 9 36 9 27 27 9 18 18 9 9 所以612和468的最大公约数是9 2 2 36 反思求两个正整数的最大公约数的问题 可以用辗转相除法 也可以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b 这个式子 反复相减 直到r 0为止 题型一 题型二 题型三 变式训练1 求228与1995的最大公约数 解法一 辗转相除法 1995 8 228 171 228 1 171 57 171 3 57 所以228与1995的最大公约数为57 解法二 更相减损术 1995 228 1767 1767 228 1539 1539 228 1311 1311 228 1083 1083 228 855 855 228 627 627 228 399 399 228 171 228 171 57 171 57 114 114 57 57 所以228与1995的最大公约数为57 题型一 题型二 题型三 求多项式的值 例2 用秦九韶算法求多项式f x 7x7 6x6 5x5 4x4 3x3 2x2 x当x 3时的值 分析 解决本题首先需要将原多项式化成f x 7x 6 x 5 x 4 x 3 x 2 x 1 x的形式 其次再弄清v0 v1 v2 v7分别是多少 再针对这些式子进行计算 题型一 题型二 题型三 解 f x 7x 6 x 5 x 4 x 3 x 2 x 1 x 所以有v0 7 v1 7 3 6 27 v2 27 3 5 86 v3 86 3 4 262 v4 262 3 3 789 v5 789 3 2 2369 v6 2369 3 1 7108 v7 7108 3 21324 故当x 3时 多项式f x 7x7 6x6 5x5 4x4 3x3 2x2 x的值为21324 反思秦九韶算法的关键在于把n次多项式转化为一次多项式 注意体会递推的实现过程 实施运算时要由内向外 一步一步执行 题型一 题型二 题型三 变式训练2 用秦九韶算法求f x 3x5 8x4 3x3 5x2 12x 6当x 2时的值 解 根据秦九韶算法 把多项式改写成如下形式 f x 3x 8 x 3 x 5 x 12 x 6 按照从内到外的顺序 依次计算一次多项式当x 2时的值 v0 3 v1 v0 2 8 3 2 8 14 v2 v1 2 3 14 2 3 25 v3 v2 2 5 25 2 5 55 v4 v3 2 12 55 2 12 122 v5 v4 2 6 122 2 6 238 所以当x 2时 多项式的值为238 题型一 题型二 题型三 易错辨析易错点 利用秦九韶算法求含空项的n次多项式的值时易出现错误 例3 已知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 错因分析 所求f 2 的值是正确的 但是错解中没有抓住秦九韶算法原理的关键 正确改写多项式 并使每一次计算只含有x的一次项 题型一 题型二 题型三 正解 f x 3x4 0 x3 2x2 4x 2 3x 0 x 2 x 4 x 2 v1 3 2 0 6 v2 6 2 2 14 v3 14 2 4 24 v4 24 2 2 50 故f 2 50 反思利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写 依次计算一次多项式 由于后项计算用到前项的结果 故应认真 细心 确保中间结果的准确性 若在多项式中有几项不存在 可将这些项的系数看成0 即把这些项看成0 xn 题型一 题型二 题型三 变式训练3 用秦九韶算法求多项式f x 8x7 5x6 3x4 2x 1当x 2时的值 解 f x 8x7 5x6 0 x5 3 x4 0 x3 0 x2