1.3中国古代数学中的算法案例.ppt

1、1.3算法案例,秦九韶算法,石家庄市第十九中学 岳儒芳,算法1：,问题1,4次乘法运算,5次加法运算.,问题2有没有更高效的算法?,计算x的幂时,可以利用前面的计算结果,以减少计算量,例1、已知多项式 , 求 的值,10次乘法运算，5次加法运算.,先计算x2，,然后依次计算,想法1：,想法2：,例2、已知 ，求,分析:,将 代入上式，从内往外依次计算,问题3,就是按照一定规则，解决某一类问题的明确的有限的步骤.,例1、已知 , 求 .,例2、已知 , 求 .,算法：,我们可以改写成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多项式的值时,首先计算最内层括号内

2、一次多项式的值,即,然后由内向外逐层计算一次多项式的值,即,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.,v0=an,v1=anx+an-1,秦九韶（1208年1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。主要成就:1247年完成了数学名著数学九章，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。秦九韶算法就是中国古代数学的一枝奇葩。直到今天，这种算法仍是多项式求值比较先进的算法 。 美国 著名科学史家萨顿说过，秦九韶是“他那个民族，他

3、那个时代，并且确实也是所有时代最伟大的数学家之一”。,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,这是一个在秦九韶算法中反复执行的步骤,因此可用 循环结构来实现.,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,v0=an,(k=1,2,n),根据 “初始化变量、设定循环控制条件、确定循环体”来构造循环结构,写算法步骤,画程序框图,编程,研究步骤：,知识探究(二):秦九韶算法的程序设计,思考:用秦九韶算法求多项式的值，可以用当型循环结构来构造算法.其算法步骤如何设计？,第一步，输入多项式的次数n， 最高次项的系数an和

4、x的值.,第二步，令v=an，i=n-1.,第三步，判断“i0”是否成立. 若是，执行第四步，否则，输出多项式的值v.,第四步，输入ai，v=vx+ai，i=i-1； 返回第三步.,根据 “初始化变量、设定循环控制条件、确定循环体”来构造循环结构,思考2:该算法的程序框图如何表示？,是,第一步，输入多项式的次数n， 最高次项的系数an和x的值.,第二步，令v=an，i=n-1.,第三步，判断“i0”是否成立. 若是，执行第四步， 否则，输出多项式的值v.,第四步，输入ai，v=vx+ai， i=i-1；返回第三步.,思考3:程序？,INPUT “n=”；n,INPUT “an=”；a,INPUT “x=”；x,v=a,i=n-1,WHILE i=0,INPUT “ai=”；a,v=v*x+a,i=i-1,WEND,PRINT v,END,是,PRINT “i=”；i,小结:,1、秦九韶算法；,2、转化思想和算法思想；,作业： 4、P45练习：2. 5、P48习题1.3A组：2.,3、用直到型循环结构写出秦九韶算法的算法步骤、画出其程序框图并编制程序