人教A版必修3 1.3 算法案例 学案.doc

1.3算法案例学习目标1.理解辗转相除法与更相减损术的含义，了解其执行过程(重点).2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质(重点).3.理解进位制的概念，能进行不同进位制间的转化(重点).预习教材p3444，完成下面问题：知识点1辗转相除法与更相减损术1.辗转相除法(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法.(2)辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步.2.更相减损术(1)我国古代数学专著九章算术中介绍的一种求两个正整数的最大公约数的算法.(2)运算过程：第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.【预习评价】(1)用“辗转相除法”求得459和357的最大公约数是_.解析4593571102，357102351，102512，所以51是102和51的最大公约数，也就是459和357的最大公约数是51.答案51(2)用“更相减损术”求294和84的最大公约数时，需做减法的次数是_.解析先用2约简得147，42，然后辗转相减得：14742105，1054263，634221，422121，故需经过4次减法运算.答案4知识点2秦九韶算法功能计算n次多项式f(x)anxnan1xn1a1xa0的值改写后的形式f(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0计算方法从括号最内层开始，由内向外逐层计算v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值【预习评价】已知f(x)x52x33x2x1，应用秦九韶算法计算x3时的值时，v3的值为_.解析将函数式化成如下形式：f(x)(x0)x2)x3)x1)x1，由内向外依次计算：v01，v11303，v233211，v3113336.答案36知识点3进位制及进位制之间的转化1.概念：进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数(大于1的整数)就是几.2.不同进位制之间的转化：(1)k进制化为十进制的方法：anan1a1a0(k)anknan1kn1a1ka0(an，an1，a1，a0n，0ank，0an1，a1，a0k).(2)十进制化为k进制的方法除k取余法.【预习评价】把1010(4)化为十进制数为_.解析1010(4)14304214104068.答案68题型一求最大公约数【例1】(1)用辗转相除法计算60和48的最大公约数时，需要做的除法次数是()a.1 b.2c.3 d.4解析6048112，481240，所以需要做的除法次数为2，选b.答案b(2)求325，130，270三个数的最大公约数.解方法一(辗转相除法)：因为325130265，130652，所以325和130的最大公约数为65.因为27065410，651065，1052.所以65和270的最大公约数为5，故325，130，270三个数的最大公约数为5.方法二(更相减损术)：325130195，19513065，1306565.所以325和130的最大公约数是65.27065205，20565140，1406575，756510，651055，551045，451035，351025，251015，15105，1055.所以270与65的最大公约数为5.所以325，130，270的最大公约数为5.规律方法求两个正整数的最大公约数的方法(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数.若是，用2约简.也可以不除以2，直接求最大公约数，这样不影响最后结果.【训练1】用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果.解803628，36844，8420，即80与36的最大公约数是4.验证：80240，36218；40220，1829；20911，1192；927，725；523，321；211，1224；所以80与36的最大公约数为4.题型二秦九韶算法的应用【例2】用秦九韶算法求多项式f(x)x55x410x310x25x1当x2时的值.解f(x)x55x410x310x25x1(x5)x10)x10)x5)x1.当x2时，有v01；v1v0xa41(2)53；v2v1xa33(2)104；v3v2xa24(2)102；v4v3xa12(2)51；v5v4xa01(2)11.故f(2)1.规律方法1.秦九韶算法的步骤2.应用秦九韶算法计算多项式的值应注意的问题(1)要正确将多项式的形式进行改写.(2)计算应由内向外依次计算.(3)当多项式函数中间出现空项时，要以系数为零的齐次项补充.【训练2】已知函数g(x)x32x25x6，用秦九韶算法求f(10)的值.解由秦九韶算法，得f(x)x32x25x6(x22x5)x6(x2)x 5)x6.当x10时，f(10)(102)105)106(8105)10675106756.方向1k进制化为十进制【例3-1】八进制数342(8)化为十进制数为_.解析342(8)382481280226.答案226方向2十进制化为k进制【例3-2】将十进制数458分别转化为四进制数和六进制数.解算式如下图，故45813022(4)2042(6).方向3两种非十进制互化【例3-3】将八进制数127(8)化成二进制数.解先将八进制数127(8)化为十进制数.127(8)1822817806416787，再将十进制数87化成二进制数：所以871010111(2)，所以127(8)1010111(2).规律方法k进制数与十进制数互化的方法(1)k进制数转化为十进制数的方法先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出其结果.即anan1a2a1a0(k)anknan1kn1a2k2a1ka0，需要注意的是，k的幂的最高次数应是k进制数的位数减去1，然后逐个减小1，最后是0次幂.(2)十进制数转化为k进制数的方法除k取余法，即先把十进制数a除以k，商为q0，余数为r0，再把q0除以k，商为q1，余数为r1，反复进行这种除法，直到qn1除以k所得的商为0，余数是rn，即rnqn1为止，此时将所有余数按从右到左排列就得到所要求的k进制数rnrn1r0(k).除k取余法的注意事项：(1)要连续除：用k连续去除十进制数或所得的商，直到商为零为止；(2)倒着写：把各步得到的余数倒写(即从下到上排列)就是相应的k进制数.【训练3】若二进制数100y011和八进制数x03相等，求xy的值.解100y011(2)126y23121678y，x03(8)x82364x3，8y6764x3.y可取0，1，x可以取1，2，3，4，5，6，7，y0时，x1；y1时， 64x72无整数解；xy1.课堂达标1.更相减损术可解决下列问题中的()a.求两个正整数的最大公约数b.求多项式的值c.进位制的转化计算d.排序问题答案a2.把二进制数110(2)化成十进制数为()a.4 b.5c.6 d.7解析110(2)1221210206.答案c3.1 037和425的最大公约数是()a.51 b.17c.9 d.3解析1 0374252187，425187251，18751334，5134117，34172.即1 037和425的最大公约数是17.答案b4.16化为二进制数是_.解析所以1610 000(2).答案10 000(2)5.已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值.解将f(x)改写为f(x)(4x2)x3.5)x2.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.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术.用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止.2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行.3.把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数.而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数.基础过关1.下列说法中正确的个数为()辗转相除法也叫欧几里得算法；辗转相除法的基本步骤是用较大的数除以较小的数；求最大公约数的方法，除辗转相除法之外，没有其他方法；编写辗转相除法的程序时，要用到循环语句.a.1 b.2c.3 d.4解析、正确，错误.答案c2.把13化为六进制数为()a.6(6) b.12(6)c.13(6) d.21(6)解析所以1321(6).答案d3.用更相减损术求117和182的最大公约数时，需做减法的次数是()a.8 b.7c.6 d.5解析18211765，1176552，655213，521339，391326，261313，13是117和182的最大公约数，需做减法的次数是6.答案c4.用秦九韶算法求多项式f(x)1235x8x279x36x45x53x6当x4的值时，其中v1的值为_.解析f(x)1235x8x279x36x45x53x6，v0a63，v1v0xa53(4)57.答案75.378和90的最大公约数为_.解析辗转相除法：37890418，901850，378与90的最大公约数是18.答案186.已知k进制数132(k)与二进制数11110(2)相等，求k的值.解都转化为十进制求解.因为132(k)k23k2，11110(2)24232221684230，所以k23k230，即k23k280，解得k4或k7(舍去)，故k4.7.用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值.解f(x)(7x6)x5)x4)x3)x2)x1)x，所以v07，v173627，v2273586，v38634262，v426233789，v5789322 369，v62 369317 108，v77 108321 324.故x3时，多项式f(x)7x76x65x54x43x32x2x的值为21 324.能力提升8.下列哪组的最大公约数与1 855，1 120的最大公约数不同()a.1 120，735 b.385，350c.385，735 d.1 855，325解析(1 855，1 120)(735，1 120)(735，385)(350，385)(350，35)，1 855与1 120的最大公约数是35，由以上计算过程可知选d.答案d9.计算机中常用的十六进制是逢16进1的计数制，采用数字09和字母af共16个计数符号，这些符号与十进制的数的对应关系如下表：十六进制0123456789abcdef十进制0123456789101112131415例如，用十六进制表示：ed1b，则ab等于()a.6e b.72c.5f d.80解析ab用十进制可以表示为1011110，而11061614，所以用十六进制表示为6e.答案a10.612和396的最大公约数为_.解析先用2约简得306，198，再用2约简得153，99，1539954，995445，54459，45936，36927，27918，1899，9436，故36为612和396的最大公约数.答案3611.用秦九韶算法求多项式f(x)20.35x1.8x23x36x45x5x6当x1时的值时，令v0a6，v1v0xa5，v6v5xa0，则v3的值是_.解析f(x)x65x56x43x31.8x20.35x2(x5)x6)x3)x1.8)x0.35)x2，所以v01，v11(1)56，v2(6)(1)612，v312(1)315.答案1512.求1 356和2 400的最小公倍数.解2 4001 35611 044，1 3561 0441312，1 0443123108，312108296，10896112，96128.所以1 356与2 400的最大公约数为12.则1 3