人教版高中数学【必修三】[知识点整理及重点题型梳理]_算法案例_提高

1、精品文档用心整理人教版高中数学必修三知识点梳理重点题型（常考知识点）巩固练习算法案例【学习目标】1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.【要点梳理】要点一：辗转相除法也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n

2、得到一个商q0和一个余数r0；第二步：若r0=0，则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1=0，则r0为m，n的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；依次计算直至rn=0，此时所得到的rn1即为所求的最大公约数.用辗转相除法求最大公约数的程序框图为：资料来源于网络仅供免费交流使用精品文档用心整理程序：input“m=”;minput“n=”;nifmnthenx=mm=nn=xendifr=mmodnwhiler0r=mmodnm=nn=rwendprintnend要点诠释：辗转相除法的基本步骤

3、是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子m=nq+r(0rb)；第二步，如果ab，则执行s3，否则转到s5；第三步，将a-b的值赋予r；第四步，若br，则把b赋予a，把r赋予b，否则把r赋予a，重新执行s2；第五步，输出最大公约数b.程序:input“a=”，ainput“b=”，bwhileabifa=ba=a-b;elseb=b-awendendprintb或者input“请输入两个不相等的正整数”；a，bi=0whileamod2=0andbmod2=0a=a/2b=b/2i=i+1wendd

4、oifbathent=aa=bb=tendif资料来源于网络仅供免费交流使用精品文档用心整理c=aba=bb=cloopuntila=bprintaiend要点诠释：用辗转相除法步骤较少，而更相减损术虽然有些步骤较长，但运算简单.要点三：秦九韶计算多项式的方法f(x)=axn+axn-1+ann-1n-2xn-2+ax+a10=(axn-1+axn-2+ann-1n-2xn-3+a)x+a10=(axn-2+axn-3+nn-1=+a)x+a)x+a210=(ax+a)x+ann-1n-2)x+a)x+a10，则有0令v=(k(ax+ann-1)x+an-2)x+an-(k-1)x+an-kv

5、=ankvk=v-1x+a，其中-nkk=1,2,ln.这样，我们便可由v依次求出v,v,lv；012nv=vx+a,10n-1v=vx+a,21n-2v=vx+a,32n-3lv=vnn-1x+a0要点诠释：显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算要点四：进位制进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为7

6、1、用十六进制表示为39，它们所代表的数值都是一样的.表示各种进位制数一般在数字右下角加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.1.k进制转换为十进制的方法：aaalaaann-1210(k)=akn+ann-1kn-1+l+ak2+ak+a，把k进制数a转化为十进制210数b的算法程序为：input“a,k,n=”;a,k,ni=1b=0whilei=n资料来源于网络仅供免费交流使用精品文档用心整理t=getaib=b+t*k(i-1)i=i+1wendprintbend2.十进制转化为k进制数b的步骤为：第一步，将给定的十进制整数除以基数k，余数便是等值的k进制

7、的最低位；第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.要点诠释：1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.【典型例题】类型一：辗转相除法与更相减损术例1分别用辗转相除法和更相减损术求378与90的最大公约数【答案】18【解析】用辗转相除法：378=904+18，90=1853

8、78与90的最大公约数是18用更相减损术：378与90都是偶数，用2约分后得189和4518945=144，14445=99，9945=54，5445=9，459=36，369=27，279=18，189=9378与90的最大公约数为29=18【总结升华】比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.由该题可以看出，辗转相除法得最大公约数的

9、步骤较少.对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.举一反三：【变式1】（1）用更相减损术求两个正数84与72的最大公约数（2）利用辗转相除法求3869与6497的最大公约数与最小公倍数【解析】（1）因为84=214，72=184，所以2118=3，183=15，153=12，123=9，93=6，资料来源于网络仅供免费交流使用精品文档用心整理63=3所以21和18的最大公约数等于3所以84和72的最大公约数等于12【总结升华】先约简，再求21与18的最大公约数，然后乘以约简的4得84与72的最大公约数（2）6497=38691+2628，3869=

10、26281+1241，2628=12412+146，1241=1468+73，146=732+0所以3869与6497的最大公约数为73，最小公倍数为3869649773=344341例2求三个数：168，54，264的最大公约数【思路点拨】运用更相减损术或辗转相除法，先求168和54的最大公约数a，再求a与264的最大公约数【答案】6【解析】采用更相减损术先求168和54的最大公约数（168，54）（114，54）（60，54）（6，54）（6，48）（6，42）（6，36）（6，30）（6，24）（6，18）（6，12）（6，6）故168和54的最大公约数为6采用辗转相除法求6和264的最

11、大公约数264=446+0，6为264与6的最大公约数，也是这三个数的最大公约数【总结升华】求最大公约数通常有两种方法：一是辗转相除法；二是更相减损术，对于3个数的最大公约数的求法，则是先求其中两个数的最大公约数m，再求m与第三个数的最大公约数同样可推广到求3个以上数的最大公约数举一反三：【变式1】求三个数324，243，135的最大公约数【答案】27【解析】324=2431+81，243=813+0，324与243的最大公约数为81又135=811+54，81=541+27，54=272+0，81与135的最大公约数为27三个数324，243，135的最大公约数为27更相减损术：324243

12、=81，24381=162，16281=81，81是324和243的最大公约数又13581=54，8154=27，资料来源于网络仅供免费交流使用精品文档用心整理5427=27，27是81与135的最大公约数三个数324，243，135的最大公约数为27例3.甲、乙、丙三种溶液分别重147g、343g、133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？【思路点拨】由题意，每个小瓶最多能装的溶液的质量应是三种溶液质量的最大公约数.【答案】7g【解析】先求147与343的最大公约数.343-147=196，196-147=49，147-49=98，98-49=49

13、，147与343的最大公约数是49.再求49与133的最大公约数.133-49=84，84-49=35，49-35=14，35-14=21，21-14=7，14-7=7.147，343，133的最大公约数是7.故每瓶最多装7g.【总结升华】本题关键是分析清楚题意，找出三个数的最大公约数.求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.类型二：秦九韶算法（例42015春河北邯郸月考）用秦九韶算法求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值【思路点拨】利用秦九韶算法计算多项式的值，先将多项式转化为(2x-5)x-4)

14、x+3)x-6)x+7的形式，然后逐步计算v到v的值，即可得到答案05【答案】2677【解析】f(x)=2x5-5x4-4x3+3x2-6x+7=(2x-5)x-4)x+3)x-6)x+7v=25-5=5，1v=55-4=21，2v=215+3=108，3资料来源于网络仅供免费交流使用精品文档用心整理v=1085-6=534，4v=5345+7=26775所以f（5）=2677【总结升华】秦九韶算法的原理是0v=ankvk=v-1x+an-,(k=1,2,3,n)k在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，则下一步，一直到最后一步就会全部算错同学们

15、在计算这种题时应格外小心举一反三：【变式1】用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当x=2时的值【答案】1397【解析】f(x)=8x7+5x6+0x5+3x4+0x3+0x2+2x+1=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1v0=8，v1=82+5=21，v2=212-0=42，v3=422-3=87，v4=872+0=174，v5=1742+0=348，v6=3482+2=698，v7=6982+1=1397，所以，当x=2时，多项式的值为1397【变式2】用秦九韶算法计算多项式f(x)=6x6+5x5+4x4+3x3+2x2+x+7在x=0.4

16、时的值时，需做加法和乘法的次数和是（）a10b9c12d8【答案】c(6【解析】f(x)=(x+x45+)x+)3+1x+)x+2)x加法6次，乘法6次，6+6=12（次），故选c类型三：进位制例5（1）试把十进制数136转化为二进制数；（2）试把十进制数1234转化为七进制数）【答案】（1）10001000（2（2）3412（7）【解析】（1）由于136=268+0，68=234+034=217+017=28+1资料来源于网络仅供免费交流使用精品文档用心整理8=24+04=22+02=21+01=20+1）所以136=10001000（2（2）1234=7176+2，176=725+125=

17、73+43=70+3所以1234=3412（7）【总结升华】（1）应注意搞清每一次除法中的被除数、除数，当商为零时停止除法，把每步所得的余数倒着排成一个数，就是相应的二进制数（2）十进制数转化为七进制数与转化为二进制数的方法类似，要认真体会其原理举一反三：【变式1】（1）把十进制数89转化为二进制数；（2）将十进制数2l转化为五进制数【解析】（1）用除2取余法：89=2(2(2(2(2(2(20+1)+0)+1)+1)+0)+0)+1=2(2(2(22(220+2+0)+1)+1)+0)+0)+1=126+025+124+123+022021+120=1011001(2)（2）用除5取余法，可得）21=41（5例6（2016春湖南娄底月考）若二进制数100y011和八进制数x03相等，求x+y的值【思路点拨】直接利用进位制运算法则化简求解即可【答案】1【解析】100y011=126+y23+12+1=67+8y，x03=x82+3=64x+3，67+8y=64x+3，y=0或1，x可以取1、2、3、4、5、6、7，y=0时，x=1；y=1时，64x=72，无解；x+y=1举一反三：【变式1】在十进制中，2