1、1.3 算法案例【知识提炼】1.辗转相除法与更相减损术(1)辗转相除法：辗转相除法：又叫_算法，是一种求两个正整数的 _的古老有效的算法.欧几里得最大公约数程序 INPUT m，n DO r=_ m=n n=r LOOP UNTIL r=0 PRINT m END m MOD n(2)更相减损术：我国古代数学专著九章算术中介绍的一种求两个正整数的 _的算法.运算过程 第一步，任意给定两个正整数，判断它们是否都是偶数，若是，_；若不是，执行第二步.最大公约数用2约简第二步，以较大的数减去较小的数，接着把所得的差与_比 较，并以大数减小数.继续这个操作，直到所得的数_为止，则 这个数(等数)或这个
2、数与约简的数的乘积就是所求的最大公约数.较小的数相等2.秦九韶算法 功能 计算n次多项式f(x)=anxn+an-1xn-1+a1x+a0的值 改写后 的形式 f(x)=anxn+an-1xn-1+a1x+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个一次多项式3.进位制及进位制之间的互化(1)进位制：概念：进位制是为了_而约定的记数系统，“满几进一”就是几进制.基数：几进制的基数就是_
3、.计数和运算方便几(2)不同进位制之间的互化：k进制化为十进制的方法：anan-1a1a0(k)=_(an，an-1，a1，a0N，0ank，0an-1，a1，a0n)，(1)用m除以n，若商为q1，余数为r1(0r1n)，则m=nq1+r1，显然若x是m和n的公约数，即x能整除m和n，则x也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数.(2)用n除以r1，得n=r1q2+r2(0r2nr1r2，所以到某一步必然有ri=ri+1qi+2，即ri恰能被ri+1整除，这时ri+1是ri和ri+1的公约数，它也必然是ri-1和ri，ri-2和ri-1，r1与r
4、2，n和r1，m和n的最大公约数.2.更相减损术求最大公约数的程序设计【知识拓展】更相减损术与辗转相除法的区别与联系 辗转相除法 更相减损术 区别 以除法为主 两个整数差值较大时运算次数较少 相除余数为零时得结果 以减法为主 两个整数的差值较大时，运算次数较多 相减，差与减数相等得结果 相减前要做是否都是偶数的判断 联系 都是求最大公约数的方法 二者的实质都是递归的过程 二者都要用循环结构来实现 知识点2 秦九韶算法 观察如图所示内容，回答下列问题：问题1：秦九韶算法的计数原理是怎样的?问题2：应按照怎样的步骤进行秦九韶算法?【总结提升】1.秦九韶算法的计数原理 秦九韶算法是按照从内到外的顺序
5、依次计算求值的.设f(x)=anxn+an-1xn-1+a1x+a0，则该算法先计算v1=anx+an-1，再计算v2=v1x+an-2，最后计算vn=vn-1x+a0.2.秦九韶算法的步骤 知识点3 进位制 观察如图所示内容，回答下列问题：问题1：进位制应如何表示?问题2：常见的进位制有哪些?【总结提升】1.进位制的表示 若一个数为十进制数，则其基数可以省略不写，若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数.2.常见的进位制(1)二进制：只使用0和1两个数字；满二进一，如1+1=10(2).(2)八进制：使用0，1，2，3，4，5，6，7八个不同的数字；
6、满八进一，如7+1=10(8).(3)十六进制：使用0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10，11，12，13，14，15；满十六进一，如F+1=2+E=10(16).【题型探究】类型一 求最大公约数【典例】1.(2015大同高一检测)用辗转相除法求378与90的最大公约数为 .2.(2015衡水高一检测)用更相减损术求294与84的最大公约数时，需做减法的次数是 .3.求104与65的最大公约数.【解题探究】1.典例1中应将两数怎样进行相除?提示：应将294除以84，用较大的数除以较小的数依次进行.2.
7、典例2中应用更相减损术时要做的第一步工作是什么?提示：由于294与84都是偶数，因此应先将两数都除以2再进行.3.典例3中如何探求两数的最大公约数?提示：可采用辗转相除法或更相减损术求两数的最大公约数.【解析】1.378=904+18，90=185+0，所以378与90的最大公约数是18.答案：18 2.因为294与84是偶数，首先除以2得到147，42，再求147与42的最大公约数147-42=105，105-42=63，63-42=21，42-21=21，共做了4次减法.答案：4 3.方法一(辗转相除法)第一步：10465=165+39 第二步：65=139+26 第三步：39=126+1
8、3 第四步：26=213+0 所以104和65的最大公约数为13.方法二(更相减损术)由于65不是偶数，把104和65以大数减小数，并辗转相减，即 104-65=39，65-39=26，39-26=13，26-13=13，所以104和65的最大公约数为13.【方法技巧】1.辗转相除法的算法步骤 第一步，输入两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.第五步，输出最大公约数m.2.更相减损术的求解步骤 第一步，给定两个正整数m，n(mn且m，n不全是偶数).第二步，计算m-n所得的差k.第三步
9、，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.【拓展延伸】三个数的最大公约数的求解方法(1)从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数.(2)根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数.(3)求得的最大公约数即为这三个数的最大公约数.【变式训练】1.用辗转相除法求225和135的最大公约数.2.用更相减损术求1734，816的最大公约数.【解析】1.225=1351+90，135=901+45，90=452，所以45是225和135的最大公约数.2.因为两数皆为偶数，首先除以2
10、得到867，408，再求867与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，所以1734与816的最大公约数是512=102.类型二 秦九韶算法的应用【典例】1.用秦九韶算法计算多项式f(x)=3x6+4x5-5x4+6x3-7x2+8x+1当x=2时的值时，需要做乘法和加法的次数分别是()A.6，6 B.5，6 C.5，5 D.6，5 2.用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1，当x=2时的值.【
11、解题探究】1.典例1中多项式的最高次数是几，多少项相加?2.典例2中不含x5，x3及x2项怎么办?【探究提示】1.典例1中多项式的最高次数是6，共7项相加.2.先把多项式f(x)=8x7+5x6+3x4+2x+1变形为f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+2x+1.【解析】1.选A.由秦九韶算法将多项式改成如下形式：f(x)=(3x+4)x-5)x+6)x-7)x+8)x+1，按由内到外的顺序，依次计算x=2时的值.v0=3，v1=32+4=10.v2=102-5=15，v3=152+6=36，v4=362-7=65，v5=652+8=138，v6=1382+1=27
12、7.这样求多项式的值时，是通过求6个一次多项式的值得到的，故进行了6次乘法和6次加法.2.根据秦九韶算法，把多项式改写成如下形式：f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+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=1397.所以当x=2时，多项式的值为1397.【延伸探究】典例2中需要做乘法和加法的次数是多少?【解析】根据秦九韶算法，把多项式改写成
13、如下形式：f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+2x+1=(8x+5)x+0)x+3)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=1397.所以当x=2时，多项式的值为1397.这样求多项式的值时，是通过求7个一次多项式的值得到的，故进行了7次乘法和7次加法.【方法技巧】应用秦九韶算法计算多项式的值应注意的问题(1)要正确将多项式的形式进行改写.(2)计算应由内向外依次计算.(3)当多项式函数
14、中间出现空项时，要以系数为零的齐次项补充.【变式训练】1.已知f(x)=x5+2x3+3x2+x+1，应用秦九韶算法计算当x=3时，v2的值为()A.27 B.11 C.109 D.36 2.(2015福州高一检测)用秦九韶算法写出当x=3时f(x)=2x5-4x3+3x2-5x+1的值.【解析】1.选B.将多项式改写成如下形式：f(x)=(x+0)x+2)x+3)x+1)x+1，由内向外依次计算：v0=1，v1=13+0=3，v2=33+2=11.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=4
15、53-5=130，v5=1303+1=391，所以f(3)=391.类型三 进位制及其转化【典例】1.(2015抚顺高一检测)把二进制数101101(2)化为十进制数为 .2.将十进制数458转化为四进制数为 .3.比较85(9)和210(6)的大小.【解题探究】1.典例1中二进制数右数第i位数字ai化为十进制数是什么数?提示：ai2i-1.2.典例2中应按照怎样的方法将458转化为四进制的数?提示：用4连续去除该十进制数得到商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的四进制数.3.典例3中比较85(9)和210(6)的大小的关键是什么?提示：比较这两个数的关键是统一进位
16、制，可将两个数转化为十进制数进行比较.【解析】1.101101(2)=125+024+123+122+021+120=32+8+4+1=45，所以二进制数101101(2)转化为十进制的数为45.答案：45 2.458=13022(4).答案：13022(4)3.因为85(9)=5+89=77，210(6)=0+16+262=78，而7877，所以210(6)85(9).【延伸探究】1.(改变问法)把典例2中的数转化成六进制的数，结果如何?【解析】458=2042(6).2.(改变问法)把典例2中的数转化成八进制的数，结果如何?【解析】所以458=712(8).【方法技巧】十进制数转化为其他进
17、制数的方法步骤【补偿训练】将235(7)转化为八进制数.【解题指南】先将非十进制数转化为十进制数，再向其他k进制数转化，注意十进制数的中间作用.【解析】235(7)=272+37+570=124(10)，所以124(10)=174(8)，即235(7)=174(8).【延伸探究】1.(变换条件)若将“235(7)”变为“235(6)”，如何转化为八进制数?【解析】因为235(6)=262+361+560=95(10)所以95(10)=137(8)故235(6)=137(8)2.(改变问法)如何将235(7)转变成四进制数?【解析】因为235(7)=272+37+570=124(10)所以237
18、(7)=1330(4).易错案例 利用秦九韶算法求多项式的值【典例】(2015哈尔滨高一检测)已知f(x)=x5+x3+x2+x+1，用秦九韶算法求f(3)的值.【失误案例】【错解分析】分析解题过程，你知道错在哪里吗?提示：错误的根本原因在于当多项式中间出现空项时，用秦九韶算法求函数值时没有补上系数为0的相应相项.【自我矫正】原多项式可化为：f(x)=(x+0)x+1)x+1)+1)x+1，当x=3时，v0=1，v1=13+0=3，v2=33+1=10，v3=103+1=31，v4=313+1=94，v5=943+1=283，所以，当x=3时，f(3)=283.【防范措施】1.多项式改写要恰当、正确 利用秦九韶算法计算多项式的值之前，必须先对多项式进行改写，多项式各项的次数按从高到低进行排列，如果有系数为0的项，要补全，然后再进行改写，否则容易出现如本题中f(x)=(x+1)x+1)x+1)x+1的错误.2.计算要准确 利用秦九韶算法计算多项式值的过程中，要进行多次计算，每一步中间结果要准确，如本题中v0，v1，v2，v3，v4，v5的计算都要准确无误，否则就可能导致错误出现.
