资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 算法初步,1.3,算法案例,例:求下面两个正整数的最大公约数:,(,1,)求,25,和,35,的最大公约数,(,2,)求,49,和,63,的最大公约数,25,(,1,),5,5,35,7,49,(,2,),7,7,63,9,所以,,25,和,35,的最大公约数为,5,所以,,49,和,63,的最大公约数为,7,思考:除了用这种方法外还有没有其它方法?,例:如何算出,8251,和,6105,的最大公约数?,辗转相除法与更相减损术,一、辗转相除法(欧几里得算法),1,、定义:,所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数。,2,、步骤,(以求,8251,和,6105,的最大公约数的过程为例),第一步,用两数中较大的数除以较小的数,求得商和余数,8251=61051+2146,结论:,8251,和,6105,的公约数就是,6105,和,2146,的公约数,求,8251,和,6105,的最大公约数,,只要求出,6105,和,2146,的公约数就可以了。,为什么呢?,第二步,对,6105,和,2146,重复第一步的做法,6105=21462+1813,同理,6105,和,2146,的最大公约数也是,2146,和,1813,的最大公约数。,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例:用辗转相除法求,225,和,135,的最大公约数,225=1351+90,135=901+45,90=452,显然,37,是,148,和,37,的最大公约数,也就是,8251,和,6105,的最大公约数,显然,45,是,90,和,45,的最大公约数,也就是,225,和,135,的最大公约数,思考:从上面的两个例子中可以看出计算的规律是什么?,S1,:用大数除以小数,S2,:除数变成被除数,余数变成除数,S3,:重复,S1,,直到余数为,0,辗转相除法是一个反复执行直到余数等于,0,才停止的步骤,这实际上是一个循环结构。,m=n q,r,用程序框图表示出右边的过程,r=m MOD n,m=n,n=r,r=0?,是,否,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,思考:辗转相除法中的关键步骤是哪种逻辑结构?,程序框图:,开始,输入,m,n,r=m MOD n,m=n,r=0?,是,否,n=r,输出,m,结束,思考:你能把辗转相除法编成一个计算机程序吗?,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,思考:你能根据更相减损术设计程序,求两个正整数的最大公约数吗?,(,1,)设计求多项式,当,x=5,时的值的算法,并写出程序。,(,2,)有没有更高效的算法?能否探求更好的算法,来解决任意多项式的求解问题?,三、秦九韶算法,引导学生把多项式变形为:,思考:从内到外,如果把每一个括号都看成一个常数,那么变形后的式子中有哪些“一次式”?,x,的系数依次是什么?,(,3,)若将,x,的值代入变形后的式子中,那么求值的计算过程是怎样的?,将变形前,x,的系数乘以,x,的值,加上变形前的第,2,个系数,得到一个新的系数;将此系数继续乘以,x,的值,再加上变形前的第,3,个系数,又得到一个新的系数;继续对新系数做上面的变换,直到与变形前的最后一个系数相加,得到一个新的系数为止。这个系数即为所求多项式的值。这种算法即是“秦九韶算法”,(,4,)用秦九韶算法求多项式的值,与多项式组成有直接关系吗?用秦九韶算法计算上述多项式的值,需要多少次乘法运算和多少次加法运算?,计算只与多项式的系数有关,,数书九章,秦九韶算法,设,是一个,n,次的多项式,对该多项式按下面的方式进行改写:,思考:当知道了x的值后该如何求多项式的值?,这是怎样的一种改写方式?最后的结果是什么?,要求多项式的值,应该先算最内层的一次多项式的值,即,然后,由内到外逐层计算一次多项式的值,即,最后的一项是什么?,这种将求一个,n,次多项式,f,(x),的值转化成求,n,个一次多项式的值的方法,称为,秦九韶算法,。,思考:在求多项式的值上,这是怎样的一个转化?,程序框图:,这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。,输入,a,i,开始,输入,n,a,n,x,i=0?,输出,v,结束,v=vx+a,i,i=i-1,Y,N,i=n-1,V=a,n,秦九韶算法的特点:,通过一次式的反复计算,逐步得出高次多项式的值,对于一个,n,次多项式,只需做,n,次乘法和,n,次加法即可。,程序:,INPUT “n=”,;,n,INPUT“an=“;a,INPUT“x=“;x,v=a,i=n-1,WHILE i=0,PRINT“i=“;i,INPUT“ai=“;a,v=v*x+a,i=i-1,WEND,PRINT v,END,四、进位制,1,、什么是进位制?,进位制是人们为了计数和运算方便而约定的记数系统。,进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数,基数为,n,,即可称,n,进位制,简称,n,进制。,比如:,满二进一,就是二进制;,满十进一,就是十进制;,满十二进一,就是十二进制;,满六十进一,就是六十进制,基数:,“满几进一”就是几进制,几进制的基数就是几,.,2,、最常见的进位制是什么?除此之外还有哪些常见的进位制?请举例说明,最常见的进位制应该是我们数学中的十进制,比如一般的数值计算,但是并不是生活中的每一种数字都是十进制的,.,古人有,半斤八两,之说,就是十六进制与十进制的转换,.,比如时间和角度的单位用六十进位制,计算“一打”数值时是,12,进制的。,电子计算机用的是二进制。,式中,1,处在百位,第一个,3,所在十位,第二个,3,所在个位,,5,和,9,分别处在十分位和百分位。十进制数是逢十进一的。,我们最常用最熟悉的就是十进制数,它的数值部分是十个不同的数字符号,0,,,1,,,2,,,3,,,4,,,5,,,6,,,7,,,8,,,9,来表示的。,十进制:,例如,133.59,,它可用一个多项式来表示:,133.59=1*10,2,+3*10,1,+3*10,0,+5*10,-1,+9*10,-2,实际上,十进制数只是计数法中的一种,但它不是,唯一记数法。除了十进制数,生产生活中还会遇到非十,进制的记数制。如时间:,60,秒为,1,分,,60,分为,1,小时,它,是六十进制的。两根筷子一双,两只手套为一副,它们,是二进制的。,其它进制:,二进制、七进制、八进制、十二进制、六十进制,二进制只有,0,和,1,两个数字,七进制用,06,七个数字,十六进制有,09,十个数字及,ABCDEF,六个字母,.,为了区分不同的进位制,常在数的右下角标明基数,十进制一般不标注基数,.,例如十进制的,133.59,,写成,133.59,(10),七进制的,13,,写成,13,(7),;二进制的,10,,写成,10,(2),一般地,若,k,是一个大于,1,的整数,那么以,k,为基数的,k,进制可以表示为一串数字连写在一起,的形式:,十进制的构成,十进制由两个部分构成,例如:,3721,其它进位制的数又是如何的呢?,第一、它有,0,9,十个数字;,第二、它有,“,数位,”,,即,从右往左,为个位、十位、百位、千位等等。,(,用,10,个数字来记数,称基数为,10),表示有:,1,个,1,,,2,个十,,7,个百即,7,个,10,的平方,,3,个千即,3,个,10,的立方,十进制:“满十进一”,其它进制数化成十进制数公式,二进制,二进制是用,0,、,1,两个数字来描述的如,11001,二进制的表示方法,区分的写法:,11001,(,2,),或者,(11001),2,八进制呢?,如,7342,(8),k,进制呢?,a,n,a,n-1,a,n-2,a,1(k),?,二进制与十进制的转换,1,、二进制数转化为十进制数,例,1,:将二进制数,110011,(2),化成十进制数。,解:,根据进位制的定义可知,所以,,110011,(,2,),=51,例,2,、设计一个算法,将,k,进制数,a(,共有,n,位,),转换为十进制数,b,。,(1),算法步骤,:,第一步,输入,a,k,和,n,的值;,第二步,将,b,的值初始化为,0,i,的值初始化为,1,;,第三步,,b=b+a,i,*k,i-1,i=i+1,第四步,判断,in,是否成立,.,若是,则执行第五步,否则,返回第三步;,第五步,输出,b,的值,.,(2),程序框图,:,开始,输入,a,k,n,b=0,i=1,把,a,的右数第,i,位数字赋给,t,b=b+t*k,i-1,i=i+1,in?,否,是,输出,b,结束,(3),程序:,INPUT“a,k,n=”;a,k,n,b=0,i=1,t=a MOD 10,DO,b=b+t*k(i-1),a=a10,t=a MOD 10,i=i+1,LOOP UNTIL in,PRINT b,END,*上面的程序如采用,get,函数,可简化为:,INPUT a,k,n,i=1,b=0,WHILE i=n,t=GET ai,b=t*k(i-1)+b,i=i+1,WEND,PRINT b,END,备注,:,GET,函数用于取出,a,的右数第,i,位数,方法:除,2,取余法,即用,2,连续去除,89,或所得的商,然后取余数。,例、把,89,化为二进制数,解:,根据“逢二进一”的原则,有,89,2,44,1,2,(2,22,0),+1,2(2,(2,11,0),+0)+1,2(2(2,(2,5,1),+0)+0)+1,5,2,2,1,2,(,2,(,2,(,2,(,2,2,1,),1,),0,),0,),1,89,12,6,02,5,12,4,12,3,02,2,02,1,12,0,所以:,89=1011001,(,2,),2,(,2,(,2,(,2,3,2,1,),0,),0,),1,2,(,2,(,2,4,2,2,2,0,),0,),1,2,(,2,5,2,3,+2,2,0,0,),1,2,6,2,4,+2,3,0,0,2,0,89,2,44,1,44,2,22,0,22,2,11,0,11,2,5,1,2(2(2,(,2,(2,2,1),+1),+0)+0)+1,所以,89,2,(,2,(,2,(,2,(,2 2,1,),1,),0,),0,),1,2,、十进制转换为二进制,注意:,1.,最后一步商为,0,,,2.,将上式各步所得的余数,从下到上排列,,得到:,89=1011001,(,2,),另解(,除,2,取余法的另一直观写法,):,5,2,2,2,1,2,0,1,0,余数,11,22,44,89,2,2,2,2,0,1,1,0,1,练习,将下面的十进制数化为二进制数?,(,1,),10,(,2,),20,把,89,化为五进制数。,3,、十进制转换为其它进制,解:,根据,除,k,取余法,以,5,作为除数,相应的除法算式为:,所以,,89=324,(,5,),89,5,17,5,3,5,0,4,2,3,余数,
展开阅读全文