《数学新设计同步人教A版必修三讲义：第一章 算法初步 1.3 Word版含答案.doc》由会员分享，可在线阅读，更多相关《数学新设计同步人教A版必修三讲义：第一章 算法初步 1.3 Word版含答案.doc（12页珍藏版）》请在金锄头文库上搜索。
1、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)运算过程：第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.【预习评价】(1)用“辗转相除法”求得459和357的最大公约数是_.解析4593571102，357102351，102512，所以51是102和51的最大公约数，也就是459和357的最大公约数是51.答案51(2)用“更相减损术”求294和84的最大公约数时，需做减法的次数是_.解析先
3、用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)(x
4、0)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题型一求最大公约数【例
5、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
6、，1406575，756510，651055，551045，451035，351025，251015，15105，1055.所以270与65的最大公约数为5.所以325，130，270的最大公约数为5.规律方法求两个正整数的最大公约数的方法(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数.若是，用2约简.也可以不除以2，直接求最大公约数，这
7、样不影响最后结果.【训练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)
8、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
9、)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的幂的乘积之和的形式，再按照十进制的运算规则计算出其结果.即ana
10、n1a2a1a0(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】若二
11、进制数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，4
12、25187251，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时
13、，多项式的值等于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解析、正确，错
