高中数学 1.32《算法案例》秦九邵算法课件 新人教A版必修3.pptVIP

1 3算法案例 第二课时 问题提出 1 辗转相除法和更相减损术 是求两个正整数的最大公约数的优秀算法 我们将算法转化为程序后 就可以由计算机来执行运算 实现了古代数学与现代信息技术的完美结合 2 对于求n次多项式的值 在我国古代数学中有一个优秀算法 即秦九韶算法 我们将对这个算法作些了解和探究 秦九韶算法 知识探究 一 秦九韶算法的基本思想 思考1 对于多项式f x x5 x4 x3 x2 x 1 求f 5 的值 若先计算各项的值 然后再相加 那么一共要做多少次乘法运算和多少次加法运算 4 3 2 1 10次乘法运算 5次加法运算 思考2 在上述问题中 若先计算x2的值 然后依次计算x2 x x2 x x x2 x x x的值 这样每次都可以利用上一次计算的结果 再将这些数与x和1相加 那么一共做了多少次乘法运算和多少次加法运算 4次乘法运算 5次加法运算 思考3 利用后一种算法求多项式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 知识探究 二 秦九韶算法的程序设计 思考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 a 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阅读下列程序 说明它解决的实际问题是什么 input x an 0y 0whlen 5y y n 1 a nn n 1wendprintyend 求多项式在x a时的值 小结作业 评价一个算法好坏的一个重要标志是运算的次数 如果一个算法从理论上需要超出计算机允许范围