1.3.2算法案例：秦九邵算法.ppt

:,是求两个正整数的最大公约数的优秀算法,我们将算法转化为程序后,就可以由计算机来执行运算,,在我国古代数学中有一个优秀算法,即秦九韶算法,::秦九邵算法(一):秦九韶算法的基本思想思考1:对于多项式f(x)=x5+x4+x3+x2+x+1,求f(5),然后再相加,那么一共要做多少次乘法运算和多少次加法运算?4+3+2+1=10次乘法运算,:秦九邵算法:在上述问题中,先计算x2的值,然后依次计算x2·x,(x2·x)·x,((x2·x)·x)·x的值,这样每次都可以利用上一次计算的结果,再将这些数与x和1相加,那么一共做了多少次乘法运算和多少次加法运算?4次乘法运算,:秦九邵算法:利用后一种算法求多项式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+:秦九邵算法:对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0,由内向外逐层计算一次多项式的值,其算法步骤如何?第一步,计算v1=anx+an-,计算v2=v1x+an-,计算v3=v2x+an-3.…第n步,计算vn=vn-1x+:秦九邵算法:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法,利用该算法求f(x0)的值,一共需要多少次乘法运算,多少次加法运算?思考6:在秦九韶算法中,记v0=an,那么第k步的算式是什么?vk=vk-1x+an-k(k=1,2,…,n):秦九邵算法(二):秦九韶算法的程序设计思考1:用秦九韶算法求多项式的值,可以用什么逻辑结构来构造算法?其算法步骤如何设计?第一步,输入多项式的次数n,,令v=an,i=n-,,v=vx+ai,i=i-,判断i≥,则返回第二步;否则,:秦九邵算法:该算法的程序框图如何表示?开始输入n,an,x的值v=anv=vx+ai输入aii≥0?i=n-1i=i-:秦九邵算法