必修三算法案例课件.ppt

思考:你能用当型循环结构构造算法，求两个正整数的最大公约数吗？写出算法步骤、程序框图和程序。 小结 进位制的概念及表示方法; 各种进位制之间的相互转化. 要求多项式的值，应该先算最内层的一次多项式的值，即 然后，由内到外逐层计算一次多项式的值，即 最后的一项是什么？ 这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。 算法步骤： 第一步：输入多项式次数n、最高次项的系数an和x的值. 第二步：将v的值初始化为an，将i的值初始化为n-1. 第三步：输入i次项的系数ai 第四步：v=vx+ai,i=i-1. 第五步：判断i是否小于或等于0，若是，则返回第三步；否则，输出多项式的值v。 程序框图： 这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。 输入ai 开始 输入n,an,x i 0? 输出v 结束 v=vx+ai i=i-1 Y N i=n-1 V=an 输入ai 开始 输入n,an,x i 0? 输出v 结束 v=vx+ai i=i-1 Y N i=n-1 V=an INPUT n=;n INPUT an=;a INPUT x=;x v=a i=n-1 WHILE i=0 PRINT i=;i INPUT ai=;a v=v*x+a i=i-1 WEND PRINT v END 程序 特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。 例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0x-5=2×5-5=5 v2=v1x-4=5×5-4=21 v3=v2x+3=21×5+3=108 v4=v3x-6=108×5-6=534 v5=v4x+7=534×5+7=2677 所以,当x=5时,多项式的值是2677. 然后由内向外逐层计算一次多项式的值,即 2 -5 -4 3 -6 7 x=5 10 5 25 21 105 108 540 534 2670 2677 所以,当x=5时,多项式的值是2677. 原多项式的系数 多项式的值. 例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法二:列表 2 2 -5 0 -4 3 -6 0 x=5 10 5 25 25 125 121 605 608 3040 3034 所以,当x=5时,多项式的值是15170. 练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值. 解:原多项式先化为: f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0 列表 2 15170 15170 注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0. 例2 已知一个五次多项式为 用秦九韶算法求这个多项式当x = 5的值。 解： 将多项式变形： 按由里到外的顺序，依此计算一次多项式当x = 5时的值： 所以，当x = 5时，多项式的值等于14130.2 你从中看到了怎样的规律？怎么用程序框图来描述呢？ 程序框图： 开始 输入f(x)的系数：a0,a1,a2,a3,a4a5 输入x0 n≤5? 输出v 结束 v=vx0+a5-n n=n+1 Y N n=1 v=a5 这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。 练习、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1 用秦九韶算法求这个多项式当x=-2时的值。 课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的程序框图 [问题1]我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什么联系呢? 进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六