1、1.3算法案例1会用辗转相除法与更相减损术求两个数的最大公约数(易错易混点)2会用秦九韶算法求多项式的值(难点)3会在不同进位制间进行相互转化(重点)基础初探教材整理1辗转相除法与更相减损术阅读教材P34P36例1前的内容，完成下列问题1辗转相除法(1)辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法(2)所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数2更相减损术更相减损术是我国古代
2、数学专著九章算术中介绍的一种求两数最大公约数的方法其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数(1)228与1 995的最大公约数是_(2)18与30的最大公约数是_【解析】(1)1 9952288171，228171157，171573，57是228与1 995的最大公约数(2)301812，18126，1266，18与30的最大公约数是6.【答案】(1)57(2)6教材整理2秦
3、九韶算法阅读教材P37P38例2前的内容，完成下列问题求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算其过程是：改写多项式为：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.设v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0.设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A顺序结构B条件结构C循环结构 D以上都
4、有【解析】根据秦九韶算法的含义知选D.【答案】D教材整理3进位制阅读教材P40的内容，完成下列问题1进位制是人们为了计数和运算方便而约定的记数系统“满k进一”就是k进制，k进制的基数是k.2将k进制数化为十进制数的方法是：先把k进制数写成各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果3将十进制数化为k进制数方法是：除k取余法即用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出就是相应的k进制数判断(正确的打“”，错误的打“”)(1)五进制的基数是5，用0,1,2,3,4,5六个数字表示()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算
5、效率()(3)用秦九韶算法可以求两个正整数的最大公约数()(4)不同进位制中，十进制的数比二进制的数大()【答案】 (1)(2)(3) (4) 小组合作型求最大公约数(1)98,280的最大公约数为()A7B14C16D8(2)用更相减损术求得78与36的最大公约数为_【精彩点拨】求两个数的最大公约数可用辗转相除法，也可用更相减损术【尝试解答】(1)由辗转相除法可得：28098284,9884114,84146.故最大公约数为14.也可以使用更相减损术或短除法(2)783642,42366,36630，30624,24618,18612，1266.【答案】(1)B(2)61求两个正整数的最大公
6、约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止2当两个整数的差较大时，用辗转相除法计算的次数较少再练一题1用辗转相除法求78与36的最大公约数【解】由辗转相除法得，783626，3666，故78与36的最大公约数是6.秦九韶算法已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值【精彩点拨】可根据秦九韶算法原理，将所给的多项式改写，然后由内到外逐次计算【尝试解答】将f(x)改写为f(x)(4x2)x3.5)x2
7、.6)x1.7)x0.8，由内向外依次计算一次多项式，当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72 826.2；v52 826.250.814 130.2.所以当x5时，多项式的值等于14 130.2.1先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可这样比直接将x2代入原式大大减少了计算量若用计算机计算，则可提高运算效率2注意：当多项式中n次项不存在时，可将第n项看作0xn.再练一题2用秦九韶算法计算f(x)6x54x4x32x29x，需要加法(或减法)与乘法运算的次数分别为()A5
8、,4B5,5C4,4D4,5【解析】n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算f(x)中无常数项，故加法次数要减少一次，为514.故选D.【答案】D探究共研型进位制及其转化探究1常见进位制有哪些？【提示】(1)十进制使用0,1,2,3,4,5,6,7,8,9这十个数字，基数为10.(2)二进制使用0和1这两个数字，基数为2.(3)八进制使用0,1,2,3,4,5,6,7这八个数字，基数为8.(4)十六进制使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个符号，基数为16.其中A，B，C，D，E，F分别相当于十进制中的10,11,
9、12,13,14,15.探究2两个非十进制的数之间怎样转化？【提示】两个非十进制的数之间的转化，可以先化成十进制数，再化成另一进制的数，即将十进制作为“桥梁”探究3不同进位制的数能比较大小吗？【提示】进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数可以比较大小，一般转化成十进制数比较大小更方便探究4进位制的原理是什么？不同的进位制如何区分？【提示】(1)十进制的原理是满十进一一个十进制正整数N可以写成an10nan110n1a1101a0100的形式，其中an，an1，a1，a0都是0至9中的数字，且an0.例如36531026105.(2)一般地，k进制数的原理是满k进一，k进
10、制数一般在右下角处标注(k)，以示区别例如270(8)表示270是一个8进制数但十进制一般省略不写把“五进制”数1234(5)转化为“十进制”数，再把它转化为“八进制”数. 【精彩点拨】k进制化十进制时，利用求各位上的数与k的幂的乘积后再相加的方法，十进制化其他进制可采用除k取余法【尝试解答】1 234(5)153252351450194，而1 234(5)194(10)302(8)把一个非十进制转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数.而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下
11、到上排列；(3)切记在所求数的右下角标明基数.再练一题3210(6)化成十进制数为_，85化成七进制数为_. 【解析】210(6)2621678，所以85151(7)【答案】78151(7)秦九韶算法中的运算次数直接法乘法运算的次数最多可达，加法最多n次，秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次已知f(x)x52x43x34x25x6，用秦九韶算法求这个多项式当x2时的值时，做了几次乘法？几次加法？【尝试解答】在v1中虽然“v1224”，而计算机还是做了1次乘法“v12124”因为用秦九韶算法计算多项式f(x)anxnan1xn1a1xa0当xx0时的值时，首先将多项式改
12、写成f(x)(anxan1)xa1)xa0，然后再计算v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0.无论an是不是1，这次的乘法都是要进行的由以上分析，共做了5次乘法，5次加法再练一题4用秦九韶算法求多项式f(x)4x5x22当x3时的值时，需要进行的乘法运算和加法运算的次数分别为()A4,2B5,3C5,2D6,2【解析】f(x)4x5x22(4x)x)x1)x)x2，需5次乘法运算和2次加法运算【答案】C1490和910的最大公约数为()A2B10C30D70【解析】9104901420,490420170,420706，故最大公约数为70.【答案】D2用更相减损
13、术求294和84的最大公约数时，需做减法的次数是() A2B3 C4D5【解析】29484210,21084126,1268442,844242.【答案】C3下列有可能是4进制数的是()A5123B6542 C3103D4312【解析】4进制数每位上的数字一定小于4，故选C.【答案】C4将51化为二进制数得_【解析】【答案】110 011(2)5利用秦九韶算法求f(x)x5x3x2x1当x3时的值【解】原多项式可化为：f(x)(x0)x1)x1)x1)x1当x3时v01，v11303，v233110，v3103131，v4313194，v59431283.所以，当x3时f(3)283.学业分层
14、测评(八)算法案例(建议用时：45分钟)学业达标一、选择题1关于进位制说法错误的是()A进位制是人们为了计数和运算方便而约定的记数系统B二进制就是满二进一，十进制就是满十进一C满几进一，就是几进制，几进制的基数就是几D为了区分不同的进位制，必须在数的右下角标注基数【解析】一般情况下，不同的进位制须在数的右下角标注基数，但十进制可以不用标注，所以不是必须在数的右下角标注基数，所以D错误【答案】D2下列四个数中，数值最小的是()A25(10)B54(4)C10 110(2)D10 111(2)【解析】统一成十进制，B中，54(4)541424.C中，10 110(2)124122222.D中，10
15、 111(2)23.【答案】C3用更相减损术求1 515和600的最大公约数时，需要做减法次数是() A15B14C13D12【解析】1 515600915,915600315,600315285,31528530,28530255,25530225,22530195,19530165,16530135,13530105,1053075,753045,453015,301515.1 515与600的最大公约数是15，则共做14次减法【答案】B4计算机中常用的十六进制是逢16进1的计数制，采用数字09和字母AF共16个计数符号，这些符号与十进制数的对应关系如下表：十六进制0123456789AB
16、CDEF十进制0123456789101112131415例如，用十六进制表示：ED1B，则AB等于()A6EB72C5FDB0【解析】AB用十进制表示1011110，而11061614，所以用16进制表示6E.【答案】A5以下各数有可能是五进制数的是()A15B106C731D21 340【解析】五进制数中各个数字均是小于5的自然数，故选D.【答案】D二、填空题6用更相减损术求36与134的最大公约数，第一步应为_【解析】36与134都是偶数，第一步应为：先除以2，得到18与67.【答案】先除以2，得到18与677用秦九韶算法求f(x)2x3x3当x3时的值v2_.【解析】f(x)(2x0)
17、x1)x3，v02；v12306；v263119.【答案】198将八进制数127(8)化成二进制数为_【解析】先将八进制数127(8)化为十进制数：127(8)1822817806416787，再将十进制数87化成二进制数：871010111(2)，127(8)1010111(2)【答案】1010111(2)三、解答题9用更相减损术求288与153的最大公约数【解】288153135,15313518,13518117,1171899,991881,811863,631845,451827,27189,1899.因此288与153的最大公约数为9.10用秦九韶算法计算多项式f(x)x612x5
18、60x4160x3240x2192x64，当x2时的值【解】将f(x)改写为f(x)(x12)x60)x160)x240)x192)x64，由内向外依次计算一次多项式当x2时的值，v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640.所以f(2)0，即x2时，原多项式的值为0.能力提升1下面一段程序的目的是()A求m，n的最小公倍数B求m，n的最大公约数C求m被n除的商D求n除以m的余数【解析】本程序当m，n不相等时，总是用较大的数减去较小的数，直到相等时跳出循环，显然是“更相减损术”故选B.【答案】B2若k进制数12
19、3(k)与十进制数38相等，则k_.【解析】由k进制数123可知k4.下面可用验证法：若k4，则38(10)212(4)，不合题意；若k5，则38(10)123(5)成立，所以k5.或者123(k)1k22k3k22k3，k22k338，k22k350，k5(k70舍去)【答案】53若二进制数10b1(2)和三进制数a02(3)相等，求正整数a，b. 【解】10b1(2)123b212b9，a02(3)a3229a2，2b99a2，即9a2b7.a1,2，b0,1，当a1时，b1，符合题意；当a2时，b，不符合题意a1，b1.4用秦九韶算法求多项式f(x)8x75x63x42x1，当x2时的值【解】根据秦九韶算法，把多项式改写成如下形式：f(x)8x75x60x53x40x30x22x1(8x5)x0)x3)x0)x0)x2)x1.而x2，所以有v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211 397.所以当x2时，多项式的值为1 397.版权所有：高考资源网()
