高中数学 第一章 算法初步 1.3 算法案例学案（含解析）新人教A版必修3

1、1.3 算法案例辗转相除法与更相减损术提出问题问题1：如何求18与54的最大公约数？提示：短除法问题2：要求6 750与3 492的最大公约数，上述法还好用吗？提示：数值太大，短除法不方便用问题3：还有没有其他方法，可用来解决“问题2”中的问题？提示：有导入新知1辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法(2)辗转相除法的算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则返回第二步2更相减损术(1)更相减损术是我国古代数学专著九章算术中介绍的一种求两个

2、正整数的最大公约数的算法(2)其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数化解疑难辗转相除法与更相减损术的比较两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为0减数与差相等最大公约数的选取最后一步中的除数最后一步中的减数计算次数步骤较少，运算复杂步骤较多，运算简单相同点同为求两个正整数最大公约数的方法，都是递归过程秦九韶算法提出问题已知多项式f(x)x53x43

3、x34x2x1.问题1：求f(1)提示：f(1)1334113.问题2：若求f(39)，再代入运算出现什么情况？提示：运算量太大，不易运算问题3：当x的值较大时，有没有更好的方法求函数值呢？提示：有可将f(x)转化为求一次多项式的值导入新知秦九韶算法的算法原理把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即

4、v2v1xan2，v3v2xan3，vnvn1xa0.这样，求n次多项式f(x)的值就转化为求n个一次多项式的值化解疑难秦九韶算法的步骤进位制提出问题问题1：今天是星期二，那么20天后是星期几？提示：20天后是星期一问题2：每周七天，逢七便又是一循环，这与我们所学过的十进制，逢十进一是否有相似之处？提示：其实一周七天，与十进制一样，相当于逢七进一，是七进制论法导入新知1进位制(1)概念：进位制是为了计数和运算方便而约定的记数系统，“满几进一”就是几进制(2)基数：几进制的基数就是几2不同进位制之间的互化(1)k进制化为十进制的方法：anan1a1a0(k)anknan1kn1a1ka0(an，

5、an1，a1，a0N，0ank,0an1，a1，a0k)(2)十进制化为k进制的方法除k取余数化解疑难常见的进位制(1)二进制：只使用0和1两个数字；满二进一，如1110.(2)八进制：使用0,1,2,3,4,5,6,7八个不同的数字；满八进一，如7110.(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；满十六进一，如F12E10.求最大公约数例1分别用辗转相除法和更相减损术求779与209的最大公约数解(1)辗转相除法：7792093152，209152157

6、，15257238，5738119，38192.所以，779与209的最大公约数为19.(2)更相减损术：779209570，1525795，570209361, 955738，361209152, 573819，20915257, 381919.所以779和209的最大公约数为19.类题通法1用辗转相除法求最大公约数的步骤2用更相减损术求最大公约数的步骤第一步，给定两个正整数m，n(mn且m，n不全是偶数)第二步，计算mn所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示第四步，若mn，则m，n的最大公约数等于m；否则，返回第二步活学活用用辗转相除法和更相减损术求1 515

7、与600的最大公约数，需要运算的次数分别为()A4,15B5,14C5,13 D4,12解析：选B辗转相除法6003151285,315285130,28530915,30152，故最大公约数为15，且需计算5次用更相减损术法：1515600915，915600315,600315285，31528530,28530255,25530225,22530195,19530165,16530135,13530105,1053075,753045,453015,301515，故最大公约数为15，且需计算14次.秦九韶算法及其应用例2用秦九韶算法求多项式f(x)6x65x54

8、x43x32x2x当x2时的值解f(x)(6x5)x4)x3)x2)x1)x，当x2时，有v06，v162517，v2172438，v3382379，v47922160，v516021321，v63212642，故当x2时，多项式f(x)6x65x54x43x32x2x的值为642.类题通法秦九韶算法原理及注意事项(1)秦九韶算法的原理是(k1,2，n)(2)在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，那么下一步，一直到最后一步就会全部算错，同学们在计算这种题时应格外小心活学活用用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1.当x

9、0.4时的值时，需要做乘法和加法的次数分别是()A6,6 B5,6C5,5 D6,5解析：选Af(x)(3x4)x5)x6)x7)x8)x1，所以需要进行6次乘法和6次加法进位制例3(1)将101 111 011(2)转化为十进制数；(2)将235(7)转化为十进制数；(3)将137(10)转化为六进制数；(4)将53(8)转化为二进制数解(1)101 111 011(2)128027126125124123022121120379(10)(2)235(7)272371570124(10)(3)137362465，137(10)345(6)(4)53(8)58138043(10)53(8)10

10、1 011(2)类题通法1k进制数化为十进制数的步骤(1)把k进制数写成不同数位上的数字与k的幂的乘积之和的形式(2)按十进制数的运算规则运算出结果2十进制数化为k进制数(除k取余法)的步骤活学活用若六进制数13m502(6)化为十进制数等于12 710，求数字m的值解：因为13m502(6)165364m63562061260216m11 846，令216m11 84612 710，所以m4.典例利用秦九韶算法求f(x)x5x3x2x1当x3时的值()A121B283C321 D239解析原多项式可化为：f(x)(x0)x1)x1)x1)x1.当x3时，v01，v11303，v233110，

11、v3103131，v4313194，v59431283.所以，当x3时f(3)283.答案B易错防范当多项式中间出现空项时，用秦九韶算法求函数值要补上系数为0的相应项，否则，本题极易出现如下所示的错误算法，从而误选A.f(x)(x1)x1)x1)x1，当x3时，v01，v1314，v243113，v3133140，v440311201121，所以当x3时，f(3)121.成功破障用秦九韶算法求多项式f(x)x50.11x30.15x0.04当x0.3时的值解：根据秦九韶算法，将f(x)写为：f(x)(x0)x0.11)x0)x0.15)x0.04.按照从内到外的顺序，依次计算一次多项式当x0.

12、3时的值：v01；v1v00.300.3；v2v10.30.110.2；v3v20.300.06；v4v30.30.150.132；v5v40.30.040.079 6.所以，当x0.3时，多项式的值为0.079 6.随堂即时演练1在对16和12求最大公约数时，整个操作如下：16124,1248,844.由此可以看出12和16的最大公约数是()A4B12C16 D8解析：选A根据更相减损术的方法判断2用秦九韶算法求多项式f(x)12xx23x32x4在x1时的值，v2的结果是()A4 B1C5 D6解析：选Dn4，a42，a33，a21，a12，a01，由秦九韶算法的递推关系式得v02，v1v

13、0xa35，v2v1xa26.3将51化为二进制数得_解析：答案：110 011(2)4用辗转相除法求294和84的最大公约数时，需要做除法的次数是_解析：29484342，84422.答案：25将1 234(5)转化为八进制数解：将1 234(5)转化为十进制数：1 234(5)153252351450194.再将十进制数194转化为八进制数：所以1 234(5)302(8)课时达标检测一、选择题14 830与3 289的最大公约数为()A23B35C11 D13答案：A2用秦九韶算法求多项式f(x)4x5x22当x3的值时，需要进行乘法运算和加减运算的次数分别为()A4,2 B5,3C5,

14、2 D6,2答案：C3用辗转相除法求72与120的最大公约数时，需要做除法的次数为()A4 B3C5 D6答案：B4用更相减损术求459与357的最大公约数，需要做减法的次数为()A4 B5C6 D7答案：B5下列各数，化为十进制后，最大的为()A101 010(2) B111(5)C32(8) D54(6)答案：A二、填空题6用更相减损术求三个数168,54,264的最大公约数为_解析：为简化运算，先将3个数用2约简为84,27,132.由更相减损术，先求84与27的最大公约数.842757，572730,30273,27324,24321,21318，18315,15312,1239,93

15、6,633.故84与27的最大公约数为3.再求3与132的最大公约数，易知132344，所以3与132的最大公约数就是3.故84,27,132的最大公约数为3；168,54,264的最大公约数为6.答案：67三位七进制数表示的最大的十进制数是_解析：最大的三位七进制数表示的十进制数最大，最大的三位七进制数为666(7)，则666(7)672671670342.答案：3428按照秦九韶算法求多项式f(x)1.5x53.5x44.1x33.6x6当x0.5时的值的过程中，令v0a5，v1v0xa4，v5v4xa0，则v4_.解析：由题意，有v01.5，v11.50.53.54.25，v24.250.54.11.975，v31.9750.500.987 5，v40.987 50.53.64.093 75.答案：4.093 75三、解答题910x1(2)y02(3)，求x、y的值解：因为10x1(2)120x2102212392x，y02(3)230y329y2，所以92x9y2且x，y，所以x1，y1. 10用秦九韶算法计算当x2时，多项式f(x)x612x560x4160x3240x2192x64的值解：将f(x)改写为f(x)(x12)x60)x160