高考数学一轮复习 1.3.2《算法案例——秦九邵算法》课件 新人教A版必修3.ppt

1 3算法案例 第二课时 例2求325 130 270三个数的最大公约数 因为325 130 2 65 130 65 2 所以325与130的最大公约数是65 因为270 65 4 10 65 10 6 5 10 5 2 所以65与270最大公约数是5 故325 130 270三个数的最大公约数是5 问题提出 1 辗转相除法和更相减损术 是求两个正整数的最大公约数的优秀算法 我们将算法转化为程序后 就可以由计算机来执行运算 实现了古代数学与现代信息技术的完美结合 2 对于求n次多项式的值 在我国古代数学中有一个优秀算法 即秦九韶算法 我们将对这个算法作些了解和探究 秦九韶算法 问题1 设计求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值的算法 并写出程序 x 5f 2 x 5 5 x 4 4 x 3 3 x 2 6 x 7printfend 程序 点评 上述算法一共做了15次乘法运算 5次加法运算 优点是简单 易懂 缺点是不通用 不能解决任意多项多求值问题 而且计算效率不高 知识探究 一 秦九韶算法的基本思想 思考2 在上述问题中 若先计算x2的值 然后依次计算x2 x x2 x x x2 x x x的值 这样每次都可以利用上一次计算的结果 那么一共做了多少次乘法运算和多少次加法运算 9次乘法运算 5次加法运算 第二种做法与第一种做法相比 乘法的运算次数减少了 因而能提高运算效率 而且对于计算机来说 做一次乘法所需的运算时间比做一次加法要长得多 因此第二种做法能更快地得到结果 思考3 能否探索更好的算法 来解决任意多项式的求值问题 f x 2x5 5x4 4x3 3x2 6x 7 2x4 5x3 4x2 3x 6 x 7 2x3 5x2 4x 3 x 6 x 7 2x2 5x 4 x 3 x 6 x 7 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 所以 当x 5时 多项式的值是2677 这种求多项式值的方法就叫秦九韶算法 5次乘法运算 5次加法运算 思考4 利用最后一种算法求多项式f x anxn an 1xn 1 a1x a0的值 这个多项式应写成哪种形式 f x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a2x a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 思考4 对于f x anx an 1 x an 2 x a1 x a0 由内向外逐层计算一次多项式的值 其算法步骤如何 第一步 计算v1 anx an 1 第二步 计算v2 v1x an 2 第三步 计算v3 v2x an 3 第n步 计算vn vn 1x a0 思考5 上述求多项式f x anxn an 1xn 1 a1x a0的值的方法称为秦九韶算法 利用该算法求f x0 的值 一共需要多少次乘法运算 多少次加法运算 思考6 在秦九韶算法中 记v0 an 那么第k步的算式是什么 vk vk 1x an k k 1 2 n n次乘法运算 n次加法运算 知识探究 二 秦九韶算法的程序设计 思考1 用秦九韶算法求多项式的值 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 输入多项式的次数n 最高次项的系数an和x的值 第二步 令v an i n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i 0是否成立 若是 则返回第二步 否则 输出多项式的值v 思考2 该算法的程序框图如何表示 思考3 该程序框图对应的程序如何表述 input n n input an a input x x v an i n 1 whilei 0 input ai b v v x b i i 1 wend printy end 理论迁移 例1已知一个5次多项式为用秦九韶算法求f 5 的值 f x 5x 2 x 3 5 x 2 6 x 1 7 x 0 8 v1 5 5 2 27 v2 27 5 3 5 138 5 v3 138 5 5 2 6 689 9 v4 689 9 5 1 7 3451 2 v5 3451 2 5 0 8 17255 2 所以f 5 17255 2 变式 例2已知一个5次多项式为用秦九韶算法求当x 5时 v1 v3的值及求f 5 的值做多少次乘法运算 解 f x 5x 0 x 3 5 x 0 x 1 7 x 0 8 v1 5 5 0 25 v2 25 5 3 5 128 5 v3 128 5 5 0 642 5 v4 642 5 5 1 7 3214 2 v5 3214 2 5 0 8 16070 8 所以v1 25 v3 642 5 f 5 16070 8 例3阅读下列程序 说明它解决的实际问题是什么 input x an 0y 0whlen 5y y n 1 a nn n 1wendprintyend 求多项式在x a时的值 小结作业 评价一