1.3算法案例(二).ppt

1.3 算法案例(二) 必修③ 第一章 算法初步 知识回顾: 上节课我们学了哪两种求最大公约数的方法? 辗转相除法和更相减损术 怎样求多项式 , 当 时的值? 作法1：把x=5代入f（x），计算各项的值，然后把它们加起来. 一共作了1+2+3+4=10次乘法运算,5次加法运算. 作法2：先计算 ,然后依次计算的 ,值,这样每次都可以利用上一次的计算结果. 一共作了4次乘法运算,5次加法运算. 秦九韶算法 秦九韶算法 求多项式在x= 时的值时，按照从内到外的顺序，依次计算一次多项式当x= 的值. 这样，求n次多项式f（x）的值就转化为求n个一次多项式的值。上述方法就是秦九韶算法. 例题1、已知一个5次多项式为 f(x)= 用秦九韶算法求这个多项式当x=5时的值. 解：f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8 按照从内到外的顺序，依次计算一次多项式当x=5的值. 所以, 当 时,多项式的值是17255.2. 练习:用秦九韶算法求多项式:f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x.当x=3时的值. 其算法步骤是: 第一步：输入多项式最高次数n，最高次数的系数 和x的值. 第二步：将v的值初始化为 ,将i的值初始化为n-1. 第三步：输入i次项的系数 第四步：,i=i-1,v=vx+ 第五步：判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v. 思考:设计一个算法,利用秦九韶算法求 其中给定x的值. 输出v 开始 输入 n,an,,x的值 i=0? v=vx+ai i=i-1 输入ai 结束 v=an 否 是 i=n-1 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 秦九韶 ：（公元1202-1261年）南宋，数学家。他在1247年（淳佑七年）著成『数书九章』十八卷．全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。这是一部划时代的巨著，它总结了前人在开方中所使用的列筹方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去，其中对「大衍求一术」﹝一次同余组解法）和「正负开方术」﹝高次方程的数值解法）等有十分深入的研究. 作 业 （1）P48习题1.3A组2 （2）补充：用更相减损术设计程序,求两个正整数m，n的最大公约数.