高一数学(1.3-2秦九邵算法).ppt

1.3 算法案例 第二课时 设计求多项式f(x)=2x55x44x3+3x2 6x+7当x=5时的值的算法，并写出程序 。 一般的解决方案 INPUT “x=”;x x=5; f=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7; PRINT f 上述算法一共做了解15次乘法运算，5 次加法运算. 优点是简单，易懂; 缺点是不通用，不能解决任意多项式 的求值问题，而且计算效率不高。 有没有更高效的算法？ 用提取公因式的方法多项式变形为 f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x+7 =(2x5)x4)x+3)x6)x+7 这样共作了5次加法，5次乘法. 从内到外，如果把每一个括号都看成一个 常数，那么变形后的式子中有哪些“一次 式”？x的系数依次是什么？ 问题提出 1.辗转相除法和更相减损术，是求 两个正整数的最大公约数的优秀算法， 我们将算法转化为程序后，就可以由计 算机来执行运算，实现了古代数学与现 代信息技术的完美结合. 2.对于求n次多项式的值，在我国古 代数学中有一个优秀算法，即秦九韶算 法，我们将对这个算法作些了解和探究. 思考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. 数书九章秦九韶算法 设是一个n次的多项式 对该多项式按下面的方式进行改写： 这是怎样的一 种改写方式？ 最后的结果是 什么？ 要求多项式的值，应该先算最内层的一次多项式的值，即 然后，由内到外逐层计算一次多项式的值，即 最后的一项 是什么？ 这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的 方法，称为秦九韶算法。 这种计算方法，称之为秦九韶方法。 直到今天，这种算法仍是世界上多项式 求值的最先进的算法。 这种方法的计算量仅为：乘法n次，加法n次. 直接求和法：直接计算P(x)=anxn+an1xn1 +a1x+a0 的值需要进行n次加法，而乘 法需要1+2+3+n=n(n+1)/2次。 理论迁移 例1 已知一个5次多项式为 用秦九韶算法求f(5)的值. f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8. v1=55+2=27； v2=275+3.5=138.5； v3=138.55-2.6=689.9； v4=689.95+1.7=3451.2； v5=3451.25-0.8=17255.2. 所以f(5)= =17255.2. 你从中看到了怎 样的规律？怎么 用程序框图来描 述呢？ 开始 输入f (x)的系数： a5 、 a4、 a3、 a2、a1、 a0 输入x n=0 v=a5 v= vx+a5-n n=n+1 n =0 INPUT “ai=”；b v=v*x+b i=i-1 WEND PRINT v END 例2 阅读 下列程序，说 明它解决的实 际问题是什么 ？ INPUT “x=”；a n=0 y=0 WHLE n5 y=y+(n+1)*an n=n+1 WEND PRINT y END 求多项式 在x=a时的值. 小结作业 评价一个算法好坏的一个重要标志 是运算的次数，如果一个算法从理论上 需要超出计算机允许范围内的