高中数学 13-2秦九邵算法课件 新人教A版必修3 课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3,算法案例,第二课时,问题提出,1.,辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合,.,2.,对于求,n,次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究,.,秦九韶算法,知识探究,(,一,):,秦九韶算法的基本思想,思考,1:,对于多项式,f(x,)=x,5,+x,4,+x,3,+x,2,+x+1,，求,f(5),的值,.,若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？,4+3+2+1=10,次乘法运算，,5,次加法运算,.,思考,2:,在上述问题中，若先计算,x,2,的值，然后依次计算,x,2,x,，,(x,2,x),x,，,(x,2,x),x),x,的值，这样每次都可以利用上一次计算的结果，再将这些数与,x,和,1,相加，那么一共做了多少次乘法运算和多少次加法运算？,4,次乘法运算，,5,次加法运算,.,思考,3:,利用后一种算法求多项式,f(x,)=a,n,x,n,+a,n-1,x,n-1,+,+a,1,x+a,0,的值，这个多项式应写成哪种形式？,f(x,)=a,n,x,n,+a,n-1,x,n-1,+,+a,1,x+a,0,=,(a,n,x,n-1,+a,n-1,x,n-2,+,+a,2,x+a,1,),x+a,0,=(,(a,n,x,n-2,+a,n-1,x,n-3,+,+a,2,),x+a,1,)x+a,0,=,=(,(,(a,n,x+a,n-1,),x+a,n-2,)x+,+a,1,)x+a,0,.,思考,4:,对于,f(x,)=(,(a,n,x+a,n-1,)x+a,n-2,)x+,+a,1,)x+a,0,，由内向外逐层计算一次多项式的值，其算法步骤如何？,第一步，计算,v,1,=a,n,x+a,n-1,.,第二步，计算,v,2,=v,1,x+a,n-2,.,第三步，计算,v,3,=v,2,x+a,n-3,.,第,n,步，计算,v,n,=v,n-1,x+a,0,.,思考,5:,上述求多项式,f(x,)=a,n,x,n,+a,n-1,x,n-1,+,+a,1,x+a,0,的值的方法称为,秦九韶算法,，利用该算法求,f(x,0,),的值，一共需要多少次乘法运算，多少次加法运算？,思考,6:,在秦九韶算法中，记,v,0,=a,n,，那么第,k,步的算式是什么？,v,k,=v,k-1,x+a,n-k,(k=1,，,2,，,，,n),知识探究,(,二,):,秦九韶算法的程序设计,思考,1:,用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，输入多项式的次数,n,，最高次 项的系数,a,n,和,x,的值,.,第二步，令,v=a,n,，,i=n-1.,第三步，输入,i,次项的系数,a,i,.,第四步，,v=,vx+a,i,，,i=i-1.,第五步，判断,i0,是否成立,.,若是，则返回第 二步；否则，输出多项式的值,v.,思考,2:,该算法的程序框图如何表示？,开始,输入,n,，,a,n,，,x,的值,v=a,n,v=,vx+a,i,输入,a,i,i0,？,i=n,-,1,i=i,-,1,结束,是,输出,v,否,思考,3:,该程序框图对应的程序如何表述？,开始,输入,n,，,a,n,，,x,的值,v=a,n,v=,vx+a,i,输入,a,i,i0,？,i=n,-,1,i=i,-,1,结束,是,输出,v,否,INPUT,“,n=,”,；,n,INPUT,“,a,n,=,”,；,a,INPUT,“,x=,”,；,x,v=a,i=n-1,WHILE i,=0,INPUT,“,ai,=,”,；,b,v=v*,x+b,i=i-1,WEND,PRINT y,END,理论迁移,例,1,已知一个,5,次多项式为 用秦九韶算法求,f(5),的值,.,f(x,)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.,v,1,=5,5+2=27,；,v,2,=27,5+3.5=138.5,；,v,3,=138.5,5-2.6=689.9,；,v,4,=689.9,5+1.7=3451.2,；,v,5,=3451.2,5-0.8=17255.2.,所以,f(5)=17255.2.,例,2,阅读下列程序，说明它解决的实际问题是什么？,INPUT,“,x=,”,；,a,n=0,y=0,WHLE n,5,y=y+(n+1)*,an,n=n+1,WEND,PRINT y,END,求多项式 在,x=a,时的值,.,小结作业,评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法,.,在多项式求值的各种算法中，秦九韶算法是一个优秀算法,.,作业：,P45,练习：,2.,P48,习题,1.3A,组：,2.,