1.3中国古代数学中的算法案例.pptx

1.3算法案例,辗转相除法更相减损术秦九韶算法进位制,知识探究（一）:辗转相除法,18和30的最大公约数是6,21830391535,思考2:8251与6105的最大公约数是多少？可以用上述方法得到吗？,对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.,思考3:若用8251去除以6105，得到8251=61051+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,辗转相除法或欧几里得算法,求m1和m2的最大公约数m1=m2*a1+m3(m1和m2的最大公约数与m2和m3的最大公约数相等)m2=m3*a2+m4mn=mn+1*an(直到能够被整除为止，mn+1就是m1和m2的最大公约数),辗转相除法基本原理：,例1：用辗转相除法求378和90的最大公约数,例2：用辗转相除法求1734，816和1343的最大公约数,18,17,一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,P35,知识探究（二）:更相减损术,（1）九章算术中的更相减损术：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,（2）现代数学中的更相减损术：,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,P36,求m1和m2的最大公约数（1）若均为偶数，先约掉2的倍数a，直到不同为偶数；（2）m1-m2=m3(m1和m2的公约数与m2和m3的公约数相同)m2-m3=m4mn-mn+1=mn+2（直到mn+1=mn+2为止，那么mn+1或mn+1*a就是m1和m2的最大公约数）,更相减损术基本原理：,例3：用更相减损术求328和105的最大公约数,1,思考：辗转相除法和更相减损术的异同？,知识探究（三）:秦九韶算法,秦九韶（1208年1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道古，汉族，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）。精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著作数书九章，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。,求f(5).,思考一：若直接将x=5代入计算，会有多少次乘法，多少次加法？,秦九韶算法：,x5+x4+x3+x2+x+1,=x4(x+1)+x3+x2+x+1,=x3x(x+1)+1+x2+x+1,=x2xx(x+1)+1+1+x+1,=xxxx(x+1)+1+1+1+1,秦九韶算法：,x5+x4+x3+x2+x+1,=x4(x+1)+x3+x2+x+1,=x3x(x+1)+1+x2+x+1,=x2xx(x+1)+1+1+x+1,=xxxx(x+1)+1+1+1+1,V0=1,V1=V0*x+1,V2=V1*x+1,=x+1,=x(x+1)+1,V3=V2*x+1,=xx(x+1)+1+1,V4=V3*x+1,=xxx(x+1)+1+1+1,V5=V5*x+1,=xxxx(x+1)+1+1+1+1,几次乘法？几次加法？,V0=1,V1=V0*x+1,V2=V1*x+1,V3=V2*x+1,V4=V3*x+1,V5=V5*x+1,求f(5).,=6,=31,=156,=781,=3906,一般地：,V0=an,V1=V0*x+an-1,V2=V1*x+an-2,Vn=Vn-1*x+a0,P38,P48,知识探究（四）:进位制,思考1:进位制是为了计数和运算方便而约定的记数系统，如逢十进一，就是十进制；每七天为一周，就是七进制；每十二个月为一年，就是十二进制，每六十秒为一分钟，每六十分钟为一个小时，就是六十进制；一般地，“满k进一”就是k进制，其中k称为k进制的基数.,思考2:十进制使用09十个数字，那么二进制、五进制、七进制分别使用哪些数字？,思考3:十进制数4528表示的数可以写成4103+5102+2101+8100，依此类比，二进制数110011(2),八进制数7342(8)分别可以写成什么式子？,110011(2)=125+124+023+022+121+120,7342(8)=783+382+481+280.,例1将下列各进制数化为十进制数.(1)10303(4)；(2)1234(5).,10303(4)=144+342+340=307.,1234(5)=153+252+351+450=194.,方法：除2取余法，即用2连续去除89或所得的商，然后取余数。,例、把89化为二进制数,解：,根据“逢二进一”的原则，有,892441,2(2220)+1,2(2(2110)+0)+1,2(2(2(251)+0)+0)+1,5221,2（2（2（2（221）1）0）0）1,89126025124123022021120,所以：89=1011001（2）,2（2（2（2321）0）0）1,2（2（242220）0）1,2（2523+2200）1,2624+230020,892441,442220,222110,11251,2(2(2(2(221)+1)+0)+0)+1,所以892（2（2（2（221）1）0）0）1,2210,1201,2,1,2,2,2,5,0,2,11,2,22,2,44,2,89,1,0,0,1,1,0,1,余数,思考2:上述化十进制数为二进制数的算法叫做除2取余法，转化过程有些复杂，观察下面的算式你有什么发现吗？,思考3:上述方法也可以推广为把十进制数化为k进制数的算法，称为