资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3 算法案例,1/34,3 5,9 15,问题1：在小学，我们已经学过求最大条约数知识，你能求出18与30最大条约数吗？,18 30,2,3,18和30最大条约数是23=6.,先用两个数公有,质因数,连续去除,一直除到所得商是互质数为止,然后把全部除数连乘起来.,案例1 辗转相除法与更相减损术,2/34,问题2:我们都是利用找条约数方法来求,最大条约数，假如两个数比较大而且依据我,们观察又不能得到一些条约数，我们又应,该怎样求它们最大条约数？比如求8251与,6105最大条约数?,3/34,研探新知,1.辗转相除法:,例1 求两个正数8251和6105最大条约数。,分析：8251与6105两数都比较大，而且没有显著条约数，如能把它们都变小一点，依据已经有知识即可求出最大条约数.,解：8251610512146,显然8251与6105最大条约数也必是2146约数，一样6105与2146条约数也必是8251约数，所以8251与6105最大条约数也是6105与2146最大条约数。,4/34,1.辗转相除法:,例1 求两个正数8251和6105最大条约数。,解：8251610512146;,6105214621813;,214618131333;,18133335148;,333148237;,1483740.,则37为8251与6105最大条约数。,以上我们求最大条约数方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前3左右首先提出。,5/34,第一步,给定两个正数,m,n,第二步,计算,m,除以,n,所得到余数,r,第三步,m=n,n=r,第四步,若,r=0,则,m,n,最大条约数等于,m;,不然返回第二步,辗转相除法求最大条约数算法：,思索：需不需要比较m，n大小,不需要,6/34,否,开始,输入两个正数m,n,r=m MOD n,r=0?,输出m,结束,m=n,n=r,是,程序框图,7/34,练习1：利用辗转相除法求两数4081与20723最大条约数.,(53),20723=40815+318;,4081=31812+265;,318=2651+53;,265=535+0.,8/34,2.更相减损术:,我国早期也有处理求最大条约数问题算法，就是更相减损术.,更相减损术求最大条约数步骤以下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.,翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.,第二步：以较大数减去较小数，接着把较小数与所得差比较，并以大数减小数。继续这个操作，直到所得数相等为止，则这个数（或这个数与约减数乘积）就是所求最大条约数.,9/34,例2 用更相减损术求98与63最大条约数.,解：因为63不是偶数，把98和63以大数减小数，并辗转相减，,即：986335;,633528;,35287;,28721;,21714;,1477.,所以，98与63最大条约数是7。,练习2：用更相减损术求两个正数84与72最大条约数。,(12),10/34,INPUT,m,n,IF,mn,THEN,m=d,ELSE,m=n,n=d,END IF,d=m-n,WEND,d=2 k*d,PRINT,d,END,思索：你能依据更相减损术设计程序，求两个正整数最大条约数吗？,11/34,辗转相除法与更相减损术比较:,（1）都是求最大条约数方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，尤其当两个数字大小区分较大时计算次数区分较显著。,（2）从结果表达形式来看，辗转相除法表达结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.,12/34,问题1设计求多项式f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7当x=5时值算法,并写出程序.,x=5,f=2x5-5x4-4x3+3x2-6x+7,PRINT f,END,程序,点评:上述算法一共做了15次乘法运算,5次加法运算.优点是简单,易懂;缺点是不通用,不能处理任意多项式求值问题,而且计算效率不高.,n次多项式至多n(n+1)/2次乘法运算和n次加法运算,案例2 秦九韶算法,13/34,这析计算上述多项式值,一共需要9次乘法运算,5次加法运算.,问题2有没有更高效算法?,分析:计算x幂时,能够利用前面计算结果,以降低计算量,即先计算x,2,然后依次计算,值.,第二种做法与第一个做法相比,乘法运算次数降低了,因而能提升运算效率.而且对于计算机来说,做一次乘法所需运算时间比做一次加法要长得多,所以第二种做法能更加快地得到结果.,14/34,问题3能否探索更加好算法,来处理任意多项式求值问题?,f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,=(,2x,4,-5x,3,-4x,2,+3x-6)x+7,=(2x,3,-5x,2,-4x+3)x-6)x+7,=(2x,2,-5x-4)x+3)x-6)x+7,=(2x-5)x-4)x+3)x-6)x+7,v,0,=2,v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3,=215+3=108,v,4,=v,3,x-6,=1085-6=534,v,5,=v,4,x+7=5345+7=2677,所以,当x=5时,多项式值是2677.,这种求多项式值方法就叫,秦九韶算法.,变为求几个一次式值,几个乘法,几个加法？,秦九韶数书九章.,15/34,2 -5 0 -4 3 -6 0,x=5,10,5,25,25,125,121,605,608,3040,3034,所以,当x=5时,多项式值是15170.,练习:用秦九韶算法求多项式 f(x)=2x,6,-5x,5,-4x,3,+3x,2,-6x当x=5时值.,解:原多项式先化为:,f(x)=2x,6,-5x,5,+,0,x,4,-4x,3,+3x,2,-6x+,0,列表,2,15170,15170,注意:n次多项式有n+1项,所以缺乏哪一项应将其系数补0.,16/34,f(x)=a,n,x,n,+a,n-1,x,n-1,+a,n-2,x,n-2,+a,1,x+a,0,.,我们能够改写成以下形式:,f(x)=(a,n,x+a,n-1,)x+a,n-2,)x+a,1,)x+a,0,.,求多项式值时,首先计算最内层括号内一次多项式值,即,v,1,=a,n,x+a,n-1,然后由内向外逐层计算一次多项式值,即,普通地,对于一个n次多项式,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3,v,n,=v,n-1,x+a,0,.,这么,求n次多项式f(x)值就转化为求n个一次多项式值.这种算法称为,秦九韶算法.,17/34,点评:秦九韶算法是求一元多项式值一个方法.,它特点是:把求一个n次多项式值转化为求n个一次多项式值,经过这种转化,把运算次数由至多n(n+1)/2次乘法运算和n次加法运算,降低为n次乘法运算和n次加法运算,大大提升了运算效率.,18/34,v,1,=a,n,x+a,n-1,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3,v,n,=v,n-1,x+a,0,.,观察上述秦九韶算法中n个一次式,可见v,k,计算要用到v,k-1,值.,若令v,0,=a,n,得,v,0,=a,n,v,K,=v,K-1,x+a,n-k,(k=1,2,n）,这是一个在秦九韶算法中重复执行步骤,所以可用循环结构来实现.,19/34,第一步,输入多项式次数,n,、最高次项系数,an,和,x,值,第二步,将,v,值初始化为,an,，将,i,值初始化为,n-1,第三步,输入,i,次项系数,ai,第四步,v=vx+ai,i=i-1,第五步,若,i=0,则返回第三步，不然输出,v,算法分析：,20/34,否,程序框图,开始,输入n,a,n,x值,输入,a,i,i=0?,i=n-1,v=a,n,v=vx+a,i,i=i-1,输出v,结束,是,21/34,问题1我们常见数字都是十进制,不过并不是生活中每一个数字都是十进制.比如时间和角度单位用六十进位制,电子计算机用是二进制.那么什么是进位制?不一样进位制之间又有什么联络呢?,进位制是人们为了计数和运算方便而约定一个记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六进一,就是十六进制;等等.,“,满几进一,”,就是几进制,几进制,基数,就是几.,可使用数字符号个数称为基数.基数都是大于1整数.,案例3 进位制,22/34,如二进制可使用数字有0和1,基数是2;,十进制可使用数字有0,1,2,8,9等十个数字,基数是10;,十六进制可使用数字或符号有09等10个数字以及AF等6个字母(要求字母AF对应1015),十六进制基数是16.,注意:为了区分不一样进位制,常在数字右下脚标明基数,.,如111001,(2),表示二进制数,34,(5),表示5进制数.,十进制数普通不标注基数.,23/34,问题2十进制数3721中3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它能够写成下面形式:,3721=310,3,+710,2,+210,1,+110,0,.,想一想二进制数1011,(2),能够类似写成什么形式?,1011,(2),=12,3,+02,2,+12,1,+12,0,.,同理:,3421,(5),=35,3,+45,2,+25,1,+15,0,.,C7A16,(16),=1216,4,+716,3,+1016,2,+116,1,+616,0,.,24/34,普通地,若k是一个大于1整数,那么以k为基数k进制数能够表示为一串数字连写在一起形式,a,n,a,n-1,a,1,a,0(k),(0a,n,k,0a,n-1,a,1,a,0,k),意思是:(1)第一个数字a,n,不能等于0;,(2)每一个数字a,n,a,n-1,a,1,a,0,都须小于k.,k进制数也能够表示成不一样位上数字与基数k幂乘积之和形式,即,a,n,a,n-1,a,1,a,0(k),=a,n,k,n,+a,n-1,k,n-1,+a,1,k,1,+a,0,k,0,.,注意这是一个n+1位数.,25/34,问题3二进制只用0和1两个数字,这恰好与电路通和断两种状态相对应,所以,计算机内部都使用二进制.,计算机在进行数运算时,先把接收到数转化成二进制数进行运算,再把运算结果转化为十进制数输出.,那么二进制数与十进制数之间是怎样转化呢?,26/34,例3:把二进制数110011,(2),化为十进制数.,分析:先把二进制数写成不一样位上数字与2幂乘积之和形式,再按照十进制数运算规则计算出结果.,解:110011,(2),=12,5,+12,4,+02,3,+02,2,+12,1,+12,0,=132+116+12+1=51.,27/34,k进制数转化为十进制数方法,先把k进制数表示成不一样位上数字与基数k幂乘积之和形式,即,a,n,a,n-1,a,1,a,0(k),=a,n,k,n,+a,n-1,k,n-1,+,+a,1,k,1,+a,0,k,0,.,再按照十进制数运算规则计算出结果.,28/34,例4:把89化为二进制数.,分析:把89化为二进制数,需想方法将89先写成以下形式,89=a,n,2,n,+a,n-1,2,n-1,+a,1,2,1,+a,0,2,0,.,29/34,89=442+,1,44=222+,0,22=112+,0,11=52+,1,5=22+,1,89=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,=12,6,+02,5,+12,4,+12,3,+02,2,+02,1,+12,0,=1011001,(2),.,能够用2连续去除89或所得商(,一直到商为0为止,),然后取余数,-除2取余法.,2=12+,0,1=02+,1,30/34,44 1,例4:把89化为二进制数.,我们能够用下面除法算式表示除2取余法:,2,89,余数,2,22 0,2,11 0,2,5 1,2,2 1,2,1 0,2,0 1,把算式中各步所得余数,从下到上排列,得到,89=1011001,(2),.,这种方法也能够推广为把十进制数化为k进制数算法,称为,除k取余法,.,31/34,例5:把89化为五进制数.,解:以5作为除数,对应除法算式为:,17 4,5,89,余数,5,3 2,5,0 3,89=324,(5),.,32/34,问题5你会把三进制数10221,(3),化为二进制数吗?,解:第一步:先把三进制数化为十进制数:,10221,(3),=13,4,+03,3,+23,2,+23,1,+13,0,=81+18+6+1=106.,第二步:再把十进制数化为二进制数:,106=1101010,(2),.,10221,(3),=106=,1101010,(2),.,33/34,小结,进位制概念及表示方法,;,各种进位制之间相互转化,.,a,n,a,n-1,a,1,a,0(k),=a,n,k,n,+a,n-1,k,n-1,+a,1,k,1,+a,0,k,0,.,34/34,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
