资源描述
湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校1.3 算法案例算法案例 第二课时第二课时 湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校问题提出问题提出湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校问题提出问题提出湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校问题提出问题提出湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考1).5(,12345)(2345fxxxxxxf求求已已知知 湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考121325).5(,12345)(2345fxxxxxxf求求已已知知 湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考121325算法算法1:需要需要(5+4+3+2+1)=15次乘法,次乘法,5次加法次加法).5(,12345)(2345fxxxxxxf求求已已知知 湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考121325算法算法1:需要需要(5+4+3+2+1)=15次乘法,次乘法,5次加法次加法).5(,12345)(2345fxxxxxxf求求已已知知 秦九韶算法秦九韶算法算法算法2:需要需要5次乘法,次乘法,5次加法次加法湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考121325算法算法1:需要需要(5+4+3+2+1)=15次乘法,次乘法,5次加法次加法).5(,12345)(2345fxxxxxxf求求已已知知 秦九韶算法秦九韶算法思考思考2).3(,1234567)(234567fxxxxxxxxf求求已已知知 算法算法2:需要需要5次乘法,次乘法,5次加法次加法湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(一一):秦九韶算法的基本思想秦九韶算法的基本思想 思考思考121325算法算法1:需要需要(5+4+3+2+1)=15次乘法,次乘法,5次加法次加法).5(,12345)(2345fxxxxxxf求求已已知知 秦九韶算法秦九韶算法思考思考218556).3(,1234567)(234567fxxxxxxxxf求求已已知知 算法算法2:需要需要5次乘法,次乘法,5次加法次加法湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校f(xf(x)=a)=an nx xn n+a+an n-1 1x xn n-1 1+a+a1 1x+ax+a0 0 =(a(an nx xn n-1 1+a+an n-1 1x xn n-2 2+a+a2 2x+ax+a1 1)x+ax+a0 0=(=(a(an nx xn n-2 2+a+an n-1 1x xn n-3 3+a+a2 2)x+ax+a1 1)x+a)x+a0 0=(=(a(an nx+ax+an n-1 1)x+ax+an n-2 2)x+)x+a+a1 1)x+a)x+a0 0.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考4:对于对于f(xf(x)=()=(a(an nx+ax+an n-1 1)x+)x+a an n-2 2)x+)x+a+a1 1)x+a)x+a0 0,由内向外逐层计算由内向外逐层计算一次多项式的值,其算法步骤如何?一次多项式的值,其算法步骤如何?湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考4:对于对于f(xf(x)=()=(a(an nx+ax+an n-1 1)x+)x+a an n-2 2)x+)x+a+a1 1)x+a)x+a0 0,由内向外逐层计算由内向外逐层计算一次多项式的值,其算法步骤如何?一次多项式的值,其算法步骤如何?第一步,计算第一步,计算v v1 1=a=an nx+ax+an n-1 1.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考4:对于对于f(xf(x)=()=(a(an nx+ax+an n-1 1)x+)x+a an n-2 2)x+)x+a+a1 1)x+a)x+a0 0,由内向外逐层计算由内向外逐层计算一次多项式的值,其算法步骤如何?一次多项式的值,其算法步骤如何?第一步,计算第一步,计算v v1 1=a=an nx+ax+an n-1 1.第二步,计算第二步,计算v v2 2=v=v1 1x+ax+an n-2 2.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考4:对于对于f(xf(x)=()=(a(an nx+ax+an n-1 1)x+)x+a an n-2 2)x+)x+a+a1 1)x+a)x+a0 0,由内向外逐层计算由内向外逐层计算一次多项式的值,其算法步骤如何?一次多项式的值,其算法步骤如何?第一步,计算第一步,计算v v1 1=a=an nx+ax+an n-1 1.第二步,计算第二步,计算v v2 2=v=v1 1x+ax+an n-2 2.第三步,计算第三步,计算v v3 3=v=v2 2x+ax+an n-3 3.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考4:对于对于f(xf(x)=()=(a(an nx+ax+an n-1 1)x+)x+a an n-2 2)x+)x+a+a1 1)x+a)x+a0 0,由内向外逐层计算由内向外逐层计算一次多项式的值,其算法步骤如何?一次多项式的值,其算法步骤如何?第一步,计算第一步,计算v v1 1=a=an nx+ax+an n-1 1.第二步,计算第二步,计算v v2 2=v=v1 1x+ax+an n-2 2.第三步,计算第三步,计算v v3 3=v=v2 2x+ax+an n-3 3.第第n n步,计算步,计算v vn n=v=vn n-1 1x+ax+a0 0.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考5:上述求多项式上述求多项式f(xf(x)=a)=an nx xn n+a+an n-1 1x xn n-1 1+a+a1 1x+ax+a0 0的值的方法的值的方法称为称为秦九韶算法秦九韶算法,利用该算法求,利用该算法求f(xf(x0 0)的的值,一共需要多少次乘法运算,多少次值,一共需要多少次乘法运算,多少次加法运算?加法运算?湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考5:上述求多项式上述求多项式f(xf(x)=a)=an nx xn n+a+an n-1 1x xn n-1 1+a+a1 1x+ax+a0 0的值的方法的值的方法称为称为秦九韶算法秦九韶算法,利用该算法求,利用该算法求f(xf(x0 0)的的值,一共需要多少次乘法运算,多少次值,一共需要多少次乘法运算,多少次加法运算?加法运算?思考思考6:在秦九韶算法中,记在秦九韶算法中,记v v0 0=a=an n,那么那么第第k步的算式是什么?步的算式是什么?湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考5:上述求多项式上述求多项式f(xf(x)=a)=an nx xn n+a+an n-1 1x xn n-1 1+a+a1 1x+ax+a0 0的值的方法的值的方法称为称为秦九韶算法秦九韶算法,利用该算法求,利用该算法求f(xf(x0 0)的的值,一共需要多少次乘法运算,多少次值,一共需要多少次乘法运算,多少次加法运算?加法运算?思考思考6:在秦九韶算法中,记在秦九韶算法中,记v v0 0=a=an n,那么那么第第k步的算式是什么?步的算式是什么?v vk k=v=vk k-1 1x+ax+an n-k k(k=1(k=1,2 2,n)n)湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校知识探究知识探究(二二):):秦九韶算法的程序设计秦九韶算法的程序设计 思考思考1:1:用秦九韶算法求多项式的值,可用秦九韶算法求多项式的值,可以用什么逻辑结构来构造算法?其算法以用什么逻辑结构来构造算法?其算法步骤如何设计?步骤如何设计?第一步,输入多项式的次数第一步,输入多项式的次数n n,最高次,最高次 项的系数项的系数a an n和和x x的值的值.第二步,令第二步,令v=av=an n,i=n-1.i=n-1.第三步,输入第三步,输入i i次项的系数次项的系数a ai i.第四步,第四步,v=vx+av=vx+ai i,i=i-1.i=i-1.第五步,判断第五步,判断i0i0是否成立是否成立.若是,则返回第若是,则返回第 二步;否则,输出多项式的值二步;否则,输出多项式的值v.v.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考2:2:该算法的程序框图如何表示?该算法的程序框图如何表示?开始开始输入输入n,an,x的值的值v=anv=vx+ai输入输入aii0?i=n-1i=i-1结束结束是是输出输出v否否湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校思考思考3:3:该程序框图对应的程序如何表述?该程序框图对应的程序如何表述?开始开始输入输入n,an,x的值的值v=anv=vx+ai输入输入aii0?i=n-1i=i-1结束结束是是输出输出v否否INPUT “n=”INPUT “n=”;n nINPUT “aINPUT “an n=”=”;a aINPUT “x=”INPUT “x=”;x x v=a v=ai=n-1i=n-1WHILE iWHILE i=0=0INPUT“ai=”INPUT“ai=”;b b v=v v=v*x+bx+bi=i-1i=i-1 WENDWENDPRINT yPRINT yENDEND湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校理论迁移理论迁移 例例1 1 已知一个已知一个5 5次多项式为次多项式为 用秦九韶算法求用秦九韶算法求f(5)f(5)的值的值.5432()523.52.61.70.8fxxxxxx=+-+-f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v v1 1=5=55+2=275+2=27;v v2 2=27=275+3.5=138.55+3.5=138.5;v v3 3=138.5=138.55-2.6=689.95-2.6=689.9;v v4 4=689.9=689.95+1.7=3451.25+1.7=3451.2;v v5 5=3451.2=3451.25-0.8=17255.2.5-0.8=17255.2.所以所以f(5)=17255.2.f(5)=17255.2.湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校例例2 阅读下列阅读下列程序,说明它程序,说明它解决的实际问解决的实际问题是什么?题是什么?理论迁移理论迁移湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校求多项式求多项式在在x=ax=a时的值时的值.234()12345f xxxxx求多项式求多项式在在x=ax=a时的值时的值.234()12345f xxxxx例例2 阅读下列阅读下列程序,说明它程序,说明它解决的实际问解决的实际问题是什么?题是什么?理论迁移理论迁移湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校小结作业小结作业湖南省长沙市一中卫星远程学校湖南省长沙市一中卫星远程学校作业:习案作业九作业:习案作业九个人观点供参考,欢迎讨论
展开阅读全文