《高中数学 第一章 算法初步 1.3 算法与案例 1.3.1 算法案例课件 新人教A版必修3》由会员分享，可在线阅读，更多相关《高中数学 第一章 算法初步 1.3 算法与案例 1.3.1 算法案例课件 新人教A版必修3（22页珍藏版）》请在金锄头文库上搜索。
1、第1 1课时辗转相除法与更相减损术、秦九韶算法1.理解辗转相除法与更相减损术的步骤,了解其执行过程,并会求最大公约数.2.掌握秦九韶算法,了解它提高计算效率的实质,并会求多项式的值.3.进一步体会算法的基本思想.1.辗转相除法与更相减损术(1)辗转相除法.算法步骤:第一步,给定两个正整数m,n.第二步,计算m除以n所得的余数r.第三步,m=n,n=r.第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.程序框图:程序: INPUTm,nDOr=m MOD nm=nn=rLOOP UNTILr=0PRINTmEND(2)更相减损术.算法分析:第一步,任意给定两个正整数,判断它们是否都
2、是偶数.若是,用2约简;若不是,执行第二步.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的差与减数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.【做一做1】用更相减损术求156和48的最大公约数时,第一步是.答案:用2约简2.秦九韶算法(1)概念:求多项式f(x)=anxn+an-1xn-1+a1x+a0的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求n个一次多项式的值,共进行n次乘法运算和n次加法运算.其过程是:改写多项式为:f(x)=anxn+an-1xn-1+a1
3、x+a0=(anxn-1+an-1xn-2+a1)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.设v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0.(2)算法步骤:第一步,输入多项式的次数n、最高次项的系数an和x的值.第二步,将v的值初始化为an,将i的值初始化为n-1.第三步,输入i次项的系数ai.第四步,v=vx+ai,i=i-1.第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v .(3)程序框图: (4)程序: INPUT“n=”;nIN
4、PUT“an=”;aINPUT“x=”;xv=ai=n-1WHILEi=0PRINT“i=”;iINPUT“ai=”;av=v x+ai=i-1WENDPRINTvEND【做一做2】用秦九韶算法求f(x)=2x3+x-3当x=3时的值的过程中,v2=.解析:f(x)=(2x+0)x+1)x-3,v0=2;v1=23+0=6;v2=63+1=19.答案:191.更相减损术与辗转相除法的区别与联系剖析:如表所示.2.秦九韶算法是比较先进的算法剖析:同一个问题有多种算法,如果某个算法比其他算法的步骤少,运算的次数少,那么这个算法就是比较先进的算法.判断算法是否先进的一个重要标志就是运算的次数越少越好
5、.求多项式f(x)=anxn+an-1xn-1+a1x+a0的值时,通常是先计算anxn,进行n次乘法运算;再计算an-1xn-1,进行n-1次乘法运算;这样继续下去但是用秦九韶算法时,改写多项式为f(x)=anxn+an-1xn-1+a1x+a0=(anxn-1+an-1xn-2+a1)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.先计算v1=anx+an-1,需1次乘法运算,1次加法运算;v2=v1x+an-2,需1次乘法运算,1次加法运算;vn=vn-1x+a0,需1次乘法运算,1次加法运算.所以需进行n次乘法
6、运算,n次加法运算,共进行2n次运算.因此说秦九韶算法与其他算法相比运算次数少,秦九韶算法是比较先进的算法.题型一题型二题型三【例1】(1)用辗转相除法求840与1 785的最大公约数;(2)用更相减损术求612与468的最大公约数.分析:本题是关于辗转相除法和更相减损术的直接应用.辗转相除法的操作是较大的数除以较小的数;更相减损术的操作是以大数减小数.解:(1)用辗转相除法求840和1 785的最大公约数.1 785=8402+105,840=1058.所以840和1 785的最大公约数是105.题型一题型二题型三(2)首先612和468都是偶数,所以用2约简,得到306和234,还是偶数,
7、需要再用2约简,得到153和117,最后用更相减损术计算得153-117=36, 117-36=81,81-36=45,45-36=9,36-9=27,27-9=18,18-9=9.所以612和468的最大公约数是922=36.反思求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相减损术.用辗转相除法,即根据a=nb+r这个式子,反复相除,直到r=0为止;用更相减损术,即根据r=|a-b|这个式子,反复相减,直到r=0为止.题型一题型二题型三【变式训练1】求228与1 995的最大公约数.解法一:(辗转相除法)1 995=8228+171,228=1171+57,171=357,所
8、以228与1 995的最大公约数为57.解法二:(更相减损术)1 995-228=1 767,1 767-228=1 539,1 539-228=1 311,1 311-228=1 083,1 083-228=855,855-228=627,627-228=399,399-228=171,228-171=57,171-57=114,114-57=57.所以228与1 995的最大公约数为57.题型一题型二题型三求多项式的值【例2】用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.分析:解决本题首先需要将原多项式化成f(x)=(7x+6)x+5)x+
9、4)x+3)x+2)x+1)x的形式,其次再弄清v0,v1,v2,v7分别是多少,再针对这些式子进行计算.题型一题型二题型三解:f(x)=(7x+6)x+5)x+4)x+3)x+2)x+1)x,所以有v0=7;v1=73+6=27;v2=273+5=86;v3=863+4=262;v4=2623+3=789;v5=7893+2=2 369;v6=2 3693+1=7 108;v7=7 1083=21 324.故当x=3时,多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x的值为21 324.反思秦九韶算法的关键在于把n次多项式转化为一次多项式,注意体会递推的实现过程,实施运算时
10、要由内向外,一步一步执行.题型一题型二题型三【变式训练2】用秦九韶算法求f(x)=3x5+8x4-3x3+5x2+12x-6当x=2时的值.解:根据秦九韶算法,把多项式改写成如下形式:f(x)=(3x+8)x-3)x+5)x+12)x-6,按照从内到外的顺序,依次计算一次多项式当x=2时的值.v0=3,v1=v02+8=32+8=14,v2=v12-3=142-3=25,v3=v22+5=252+5=55,v4=v32+12=552+12=122,v5=v42-6=1222-6=238,所以当x=2时,多项式的值为238.题型一题型二题型三易错辨析易错点:利用秦九韶算法求含空项的n次多项式的值
11、时易出现错误【例3】已知f(x)=3x4+2x2+4x+2,利用秦九韶算法求f(-2)的值.错解:f(x)=(3x2+2)x+4)x+2,v1=3(-2)2+2=14;v2=14(-2)+4=-24;v3=-24(-2)+2=50.故f(-2)=50.错因分析:所求f(-2)的值是正确的,但是错解中没有抓住秦九韶算法原理的关键,正确改写多项式,并使每一次计算只含有x的一次项.题型一题型二题型三正解:f(x)=3x4+0x3+2x2+4x+2=(3x+0)x+2)x+4)x+2,v1=3(-2)+0=-6;v2=-6(-2)+2=14;v3=14(-2)+4=-24;v4=-24(-2)+2=5
12、0.故f(-2)=50.反思利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写,依次计算一次多项式,由于后项计算用到前项的结果,故应认真、细心,确保中间结果的准确性.若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看成0xn.题型一题型二题型三【变式训练3】用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当x=2时的值.解:f(x)=8x7+5x6+0x5+3x4+0x3+0x2+2x+1=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.按照由内到外的顺序,依次计算一次多项式当x=2时的值.v0=8;v1=82+5=21;v2=212+0=42;v3=422+3=87;v4=872+0=174;v5=1742+0=348;v6=3482+2=698;v7=6982+1=1 397.故当x=2时,多项式的值为1 397.
