高中数学必修三课件1.3算法案例

解：21824用公有质因数2除，3912用公有质因数3除，343和4互质不除了。得：18和24最大公约数是：2×3＝6想一想，如何求8251与6105的最大公约数？例、求18与24的最大公约数：短除法案例1、8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数显然45是90和45的最大公约数，也就是225和135的最大公约数思考1：从上面的两个例子可以看出计算的规律是什么？S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0解：辗转相除法（欧几里得算法）辗转相除除法的程序框图与程序开始输入m,nr=mMODnm=nn=rr=0？输出m结束否是INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND《九章算术》——更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。例、用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减。=7所以，98和63的最大公约数等于7。（98，63）=（63，35）98-63=3563-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）程序：INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFbaTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND开始输入：a,b输出：a×2i结束a=b?a=a/2,b=b/2是a=a-bt=a,a=b,b=tba?aMOD2=0且bMOD2=0?是否否否是i=0i=i+1秦九韶（约1202年－1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。主要成就:1247年完成了数学名著《数书九章》，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。秦九韶算法就是中国古代数学的一枝奇葩。直到今天，这种算法仍是多项式求值比较先进的算法。美国著名科学史家萨顿说过，秦九韶是“他那个民族，他那个时代，并且确实也是所有时代最伟大的数学家之一”。案例2、秦九韶算法知识探究(一):秦九韶算法的基本思想思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，怎么样求f(5)的值呢？思考2:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？f(x)=anxn+an-1xn-1+…+a1x+a0(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0==…=(…((anx+an-1)x+an-2)x+…+a1)x+a0次乘法运算，次加法运算.nn例1已知一个5次多项式为用秦九韶算法求f(5)的值.5432()423.52.61.70.8fxxxxxxf(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=v2=v3=v4=v5=所以f(5)=14130.2.解：根据秦九韶算法，把多项式改写成v0=4；4×5+2=22；22×5+3.5=113.5；113.5×5-2.6=564.9；2826.2；564.9×5+1.7=14130.2.2826.2×5-0.8=432()329111fxxxxx,求f(4)的值.f(x)=(((3x+2)x-9)x-11)x+1解：根据秦九韶算法，把多项式改写成v1=v2=v3=v4=∴f(4)=709.v0=3；3×4+2=14；14×4-9=47；47×4-11=177；709；177×4+1=程序？INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi=0INPUT“ai=”；av=v*x+ai=i-1WENDPRINTvEND输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1是输出v否结束开始PRINT“i=”；i[问题1]我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什么联系呢?进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六进一,就是十六进制;等等.“满几进一”,就是几进制,几进制的基数就是几.可使用数字符号的个数称为基数.基数都是大于1的整数.一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式anan-1…a1a0(k)k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.注意这是一个n+1位数.例1:把二进制数110011(2)化为十进制数.分析:先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再按照十进制数的运算规则计算出结果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.k进制数转化为十进制数的方法先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十进制数的运算规则计算出结果.例：10231（4）=________235（7）=________301124例2:把89化为二进制的数.十进制数转化为k进制数的方法441例2:把89化为二进制的数.我们可以用下面的除法算式表示除2取余法:289余数22202110251221210201把算式中各步所得的余数从下到上排列,得到89=1011001(2).这种方法也可以推广为把十进制数化为k进制数的算法,称为除k取余法.解：例3:把89化为五进制的数.解:以5作为除数,相应的除法算式为:174589余数532503∴89=324(5).[问题4]你会把三进制数10221(3)化为二进制数吗?解:第一步:先把三进制数化为十进制数:10221(3)=1×34+0×33+2×32+2×31+1×30=81+18+6+1=106.第二步:再把十进制数化为二进制数:106=1101010(2).∴10221(3)=106=1101010(2).知识回顾KnowledgeReview