《四川开江县高中数学第一章算法初步1.3算法与案例新人教a必修3》由会员分享，可在线阅读，更多相关《四川开江县高中数学第一章算法初步1.3算法与案例新人教a必修3（33页珍藏版）》请在金锄头文库上搜索。
1、1.3算法案例35915问题1：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？18302318和30的最大公约数是23=6.先用两个数公有的质因数连续去除一直除到所得的商是互质数为止然后把所有的除数连乘起来.案例1辗转相除法与更相减损术问题2:我们都是利用找公约数的方法来求最大公约数，如果两个数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数研探新知1.辗转相除法:例1求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有
2、的知识即可求出最大公约数.解：8251610512146显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。1.辗转相除法:例1求两个正数8251和6105的最大公约数。解：82516105121466105214621813214618131333181333351483331482371483740.则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。第一步给定两个正数mn
3、第二步计算m除以n所得到余数r第三步m=nn=r第四步若r=0则mn的最大公约数等于m否则返回第二步辗转相除法求最大公约数算法：思考：需不需要比较m，n的大小不需要否开始输入两个正数mnr=mMODnr=0输出m结束m=nn=r是程序框图练习1：利用辗转相除法求两数4081与20723的最大公约数.(53)20723=40815+3184081=31812+265318=2651+53265=535+0.2.更相减损术:我国早期也有解决求最大公约数问题的算法，就是更相减损术.更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.翻译
4、出来为：第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（或这个数与约减数的乘积）就是所求的最大公约数.例2用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：9863356335283528728721217141477.所以，98与63的最大公约数是7。练习2：用更相减损术求两个正数84与72的最大公约数。(12)mnIFmnTHENm=dELSEm=nn=dENDIFd=m-nWEN
5、Dd=2kdPRINTdEND思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？辗转相除法与更相减损术的比较:（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.问题1设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法并写出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINTfEND程序点评:上述算法一共做了15次乘法运算
6、5次加法运算.优点是简单易懂缺点是不通用不能解决任意多项式求值问题而且计算效率不高.n次多项式至多n(n+1)2次乘法运算和n次加法运算案例2秦九韶算法这析计算上述多项式的值一共需要9次乘法运算5次加法运算.问题2有没有更高效的算法分析:计算x的幂时可以利用前面的计算结果以减少计算量即先计算x2然后依次计算的值.第二种做法与第一种做法相比乘法的运算次数减少了因而能提高运算效率.而且对于计算机来说做一次乘法所需的运算时间比做一次加法要长得多因此第二种做法能更快地得到结果.问题3能否探索更好的算法来解决任意多项式的求值问题f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2
7、+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以当x=5时多项式的值是2677.这种求多项式值的方法就叫秦九韶算法.变为求几个一次式的值几个乘法几个加法？秦九韶数书九章.2-50-43-60 x=5105252512512160560830403034所以当x=5时多项式的值是15170.练习:用秦九韶算法
8、求多项式f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.解:原多项式先化为:f(x)=2x6-5x5+0x4-4x3+3x2-6x+0列表21517015170注意:n次多项式有n+1项因此缺少哪一项应将其系数补0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我们可以改写成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多项式的值时首先计算最内层括号内一次多项式的值即v1=anx+an-1然后由内向外逐层计算一次多项式的值即一般地对于一个n次多项式v2=v1x+an-2v3=v2x+an-3vn=vn-1x+a0.这样求n次多
9、项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.点评:秦九韶算法是求一元多项式的值的一种方法.它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值通过这种转化把运算的次数由至多n(n+1)2次乘法运算和n次加法运算减少为n次乘法运算和n次加法运算大大提高了运算效率.v1=anx+an-1v2=v1x+an-2v3=v2x+an-3vn=vn-1x+a0.观察上述秦九韶算法中的n个一次式可见vk的计算要用到vk-1的值.若令v0=an得v0=anvK=vK-1x+an-k(k=12n）这是一个在秦九韶算法中反复执行的步骤因此可用循环结构来实现.第一步输入多项式次数n
10、、最高次项的系数an和x的值第二步将v的值初始化为an，将i的值初始化为n-1第三步输入i次项的系数ai第四步v=vx+aii=i-1第五步若i=0则返回第三步，否则输出v算法分析：否程序框图开始输入nanx的值输入aii=0i=n-1v=anv=vx+aii=i-1输出v结束是问题1我们常见的数字都是十进制的但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制电子计算机用的是二进制.那么什么是进位制不同的进位制之间又有什么联系呢进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一就是二进制满十进一就是十进制满十六进一就是十六进制等等.“满几进一”就是几进制
11、几进制的基数就是几.可使用数字符号的个数称为基数.基数都是大于1的整数.案例3进位制如二进制可使用的数字有0和1基数是2十进制可使用的数字有01289等十个数字基数是10十六进制可使用的数字或符号有09等10个数字以及AF等6个字母(规定字母AF对应1015)十六进制的基数是16.注意:为了区分不同的进位制常在数字的右下脚标明基数.如111001(2)表示二进制数34(5)表示5进制数.十进制数一般不标注基数.问题2十进制数3721中的3表示3个千7表示7个百2表示2个十1表示1个一从而它可以写成下面的形式:3721=3103+7102+2101+1100.想一想二进制数1011(2)可以类似
12、的写成什么形式1011(2)=123+022+121+120.同理:3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162+1161+6160.一般地若k是一个大于1的整数那么以k为基数的k进制数可以表示为一串数字连写在一起的形式anan-1a1a0(k)(0ank0an-1a1a0k)意思是:(1)第一个数字an不能等于0(2)每一个数字anan-1a1a0都须小于k.k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式即anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0.注意这是一个n+1位数.问题3二进制只用
13、0和1两个数字这正好与电路的通和断两种状态相对应因此计算机内部都使用二进制.计算机在进行数的运算时先把接受到的数转化成二进制数进行运算再把运算结果转化为十进制数输出.那么二进制数与十进制数之间是如何转化的呢例3:把二进制数110011(2)化为十进制数.分析:先把二进制数写成不同位上数字与2的幂的乘积之和的形式再按照十进制数的运算规则计算出结果.解:110011(2)=125+124+023+022+121+120=132+116+12+1=51.k进制数转化为十进制数的方法先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式即anan-1a1a0(k)=ankn+an-1kn-1+a
14、1k1+a0k0.再按照十进制数的运算规则计算出结果.例4:把89化为二进制的数.分析:把89化为二进制的数需想办法将89先写成如下形式89=an2n+an-12n-1+a121+a020.89=442+144=222+022=112+011=52+15=22+189=442+1=(222+0)2+1=(112+0)2+0)2+1=(52+1)2+0)2+0)2+1=(22+1)2+1)2+0)2+0)2+1=(12)+0)2+1)2+1)2+0)2+0)2+1=126+025+124+123+022+021+120=1011001(2).可以用2连续去除89或所得商(一直到商为0为止)然后取
15、余数-除2取余法.2=12+01=02+1441例4:把89化为二进制的数.我们可以用下面的除法算式表示除2取余法:289余数22202110251221210201把算式中各步所得的余数从下到上排列得到89=1011001(2).这种方法也可以推广为把十进制数化为k进制数的算法称为除k取余法.例5:把89化为五进制的数.解:以5作为除数相应的除法算式为:174589余数53250389=324(5).问题5你会把三进制数10221(3)化为二进制数吗解:第一步:先把三进制数化为十进制数:10221(3)=134+033+232+231+130=81+18+6+1=106.第二步:再把十进制数化为二进制数:106=1101010(2).10221(3)=106=1101010(2).
