《数学新设计同步人教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解析、正确,错