《高中数学全程复习方略配套课件辗转相除法与更相减损术秦九韶算法》由会员分享，可在线阅读，更多相关《高中数学全程复习方略配套课件辗转相除法与更相减损术秦九韶算法（53页珍藏版）》请在金锄头文库上搜索。
1、第1课时 辗转相除法与更相减损术、 秦九韶算法,1.理解三种算法的原理及应用. 2.了解三种算法的框图的表示及程序. 3.会用秦九韶算法求多项式的值.,1.本节重点是三种算法的原理及应用和用秦九韶算法求多项式的值. 2.本节难点是三种算法的应用和三种算法的框图的表示及程序.,1.辗转相除法 （1）概念：辗转相除法是用于求两个正整数_的一 种算法，这种算法是由欧几里得在公元前300年左右首先提出 的，因而又叫_,最大公约数,欧几里得算法,（2）程序,m MOD n,2.更相减损术 （1）相应概念及基本过程 更相减损术是我国古代数学专著_中介绍的一种 求两个正整数最大公约数的方法 （2）运算过程
2、第一步，任意给定两个正整数，判断它们是否都是偶数，若 是，_；若不是，执行第二步,九章算术,用2约简,第二步，以较大的数减去较小的数，接着把所得的差与_ _比较，并以大数减小数继续这个操作，直到所得的数_ 为止，则这个数（等数）或这个数与约简的数的乘积就是所求 的最大公约数,较小的,数,相等,（3）程序,r,r,a-b,3.秦九韶算法 （1）算法原理：把一个n次多项式f（x）=anxn+an-1xn-1+ +a1x+a0改写成如下形式： 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
3、+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， 这样，求n次多项式f（x）的值就转化为求n个一次多项式的值.,（2）程序如下：,v*x0+a（n-i）,1.实际应用更相减损术时要做的第一步工作是什么？ 提示：先判断a,b是否为偶数，若是都除以2再进行. 2.当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？ 提示：所缺的项写成系数为零的形式，即写成0
4、xn的形式.,3.25与35的最大公约数为_. 【解析】35=125+10， 25=210+5， 10=25， 所以25与35的最大公约数为5. 答案：5,4.用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+ 8x+1，当x=0.4时,需要做乘法的次数是_. 【解析】多项式变形为 f（x）=3x6+4x5+5x4+6x3+7x2+8x+1 =（3x+4）x+5）x+6）x+7）x+8）x+1， 其中乘法的次数为6. 答案：6,1.比较辗转相除法与更相减损术的区别 （1）都是求两个正整数最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除
5、法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显. （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到.,2.用秦九韶算法的注意点 在计算vk（k=0,1,2,n）时，逐级迭代提高了计算的速度，计算要准确，任何一步的失误，都会导致结果的错误.,辗转相除法及其应用 【技法点拨】 辗转相除法（欧几里得算法） （1）算理：所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数.,（2）算法步骤
6、第一步：输入两个正整数m,n（mn）. 第二步：计算m除以n所得的余数r. 第三步：m=n,n=r. 第四步：若r0,则m,n的最大公约数等于m； 否则，返回第二步. 第五步：输出最大公约数m.,【典例训练】 1.378与90的最大公约数为_ 2.用辗转相除法求225和135的最大公约数. 【解析】1.辗转相除法： 37890418， 901850， 所以378与90的最大公约数是18. 答案：18,2.225=1351+90， 135=901+45， 90=452， 所以45是225和135的最大公约数.,【想一想】 为何辗转相除法总能求出最大公约数？ 提示：由除法的性质可以知道，对于任意两
7、个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数.,【变式训练】用辗转相除法求123和48的最大公约数. 【解析】辗转相除法求最大公约数的过程如下： 12324827， 4812721， 271216， 21363， 623+0， 所以123和48的最大公约数为3.,更相减损术及其应用 【技法点拨】 更相减损术的求解步骤 第一步，给定两个正整数m，n（mn且m，n不全是偶数）. 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.,【典例训练】
8、1.用更相减损术求294与84的最大公约数时，需做减法的次数是_. 2.用更相减损术求104与65的最大公约数. 【解析】1.294与84是偶数,首先除以2得到147，42，再求147与42的最大公约数147-42=105,105-42=63,63-42=21,42-21=21,共做了4次减法. 答案：4,2.由于65不是偶数，把104和65以大数减小数，并辗转相减，即 104-65=39， 65-39=26， 39-26=13， 26-13=13， 所以104和65的最大公约数为13.,【互动探究】本题2条件不变，如何用辗转相除法求解？ 【解析】第一步：10465=165+39 第二步：65
9、=139+26 第三步：39=126+13 第四步：26=213+0 所以104和65的最大公约数为13.,【思考】 更相减损术与辗转相除法比较有何运算特点？应用更相减损术的易错点是什么？ 提示：（1）尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程（2）应用更相减损术要注意的是差和 较小的数比较，然后再相减.,【变式训练】用更相减损术求1 734，816的最大公约数. 【解析】因为两数皆为偶数，首先除以2得到867，408，再求867
10、与408的最大公约数 867-408=459， 459-408=51， 408-51=357， 357-51=306， 306-51=255，,255-51=204， 204-51=153， 153-51=102， 102-51=51， 所以1 734与816的最大公约数是512=102,秦九韶算法及其应用 【技法点拨】 算法步骤 第一步，输入多项式次数n、最高次项的系数an和x的值. 第二步，将v的值初始化为an，将i的值初始化为n-1. 第三步，输入i次项的系数ai. 第四步，v=vx+ai,i=i-1. 第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.,【典例
11、训练】 1.已知f（x）x52x33x2x1，应用秦九韶算法计算当x=3时，v3的值为（ ） （A）27 （B）11 （C）109 （D）36 2.（2012福州高一检测）用秦九韶算法写出当x=3时f（x）=2x5-4x3+3x2-5x+1的值.,【解析】1.选B.将多项式改写成如下形式： f（x）（x0）x2）x3）x1）x1， 由内向外依次计算： v01， v11303， v233211. 2.f（x）=（2x-0）x-4）x+3）x-5）x+1， v0=2，,v1=23+0=6， v2=63-4=14， v3=143+3=45， v4=453-5=130， v5=1303+1=391，
12、所以f（3）=391.,【思考】怎样用程序框图表示秦九韶算法？用秦九韶算法解题的关键是什么？ 提示：（1）程序框图:,（2）应用秦九韶算法解题的关键是把多项式转化成n个一次多项式.,三个数的最大公约数 【技法点拨】 三个数的最大公约数的求解方法 先从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数，然后再根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数，最后求得的最大公约数即为这三个数的最大公约数,【典例训练】 1.168,56,224的最大公约数是_. 2.用辗转相除法或者更相减损术求三个数324,243,135的最大公约数. 【解析】1.168=563,1
13、68,56的最大公约数是56, 224=564,故56,224的最大公约数为56, 三个数168,56,224的最大公约数是56. 答案：56,2.辗转相除法： 324=243181，243=8130， 则324与243的最大公约数为81. 又135=81154，81=54127，54=2720， 则81与135的最大公约数为27. 所以三个数324,243,135的最大公约数为27.,更相减损术： 324243=81,24381=162,16281=81，则324与243的最大公约数为81. 13581=54,8154=27,5427=27，则81与135的最大公约数为27. 所以三个数32
14、4,243,135的最大公约数为27.,【易错误区】利用秦九韶算法求值的易错点 【典例】利用秦九韶算法求多项式f（x）=x6-5x5+6x4+x2+3x+2当x=-2时的值（ ） （A）320 （B）-160 （C）-320 （D）300 【解题指导】,【解析】选A.将多项式变形为 f（x）=（x-5）x+6）x+0）x+1）x+3）x+2， v0=1, v1=-2+（-5）=-7, v2=-7（-2）+6=20， v3=20（-2）+0=-40， v4=-40（-2）+1=81，,v5=81（-2）+3=-159， v6=-159（-2）+2=320， 所以多项式当x=-2时的值是320.,
15、【阅卷人点拨】通过阅卷后分析，对解答本题的常见错误及解题启示总结如下：,【即时训练】已知多项式f（x）=3x5+8x4-3x3+5x2+12x-6,则 f（2）=_. 【解析】根据秦九韶算法，把多项式改写成如下形式： f（x）=（3x+8）x-3）x+5）x+12）x-6. 按照从内到外的顺序，依次计算一次多项式当x=2时的值. v0=3， v1=32+8=14， v2=142-3=25，,v3=252+5=55， v4=552+12=122， v5=1222-6=238， 所以当x=2时，多项式的值为238. 答案：238,1.更相减损术可解决下列问题中的（ ） （A）求两个正整数的最大公约数 （B）求多项式的值 （C）进位制的转化计算 （D）排序问题 【解析】选A.更相减损术是解决求两个或两个以上的正整数的最大公约数的.,2.用秦九韶算法求多项式f（x）=4x53x4+6x9，当x=3时的值时，需要乘法运算和加法运算的次数为（ ） （A）4,2 （B）5,3 （C）5,5 （D）5,4 【解析】选B. f（x）=4x53x4+6x9= （4x3）x）x）x+6）x9.,3.求两个正整数840与1 785的最大公约数_. 【解析】1 785=8402+105, 840=1058, 所以105为840与1 785的最大公约数. 答案：105,
