1.3算法案例

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1.3算法案例,1.,回顾算法的三种表示方法：,（,1,）、自然语言,（,2,）、程序框图,（,3,）、程序语言,（三种逻辑结构）,（五种基本语句）,复习引入,一、输入语句,1,、一般格式：,INPUT,“,提示内容”；变量,INPUT “x=”,；,x,二、输出语句,1,、一般格式：,PRINT,“,提示内容”；表达式,三、赋值语句,1,、一般格式,：,变量,=,表达式,程序框图,条件语句的一般格式,IF,条件,THEN,语句体,(,步骤,A),END IF,步骤,A,满足条件？,是,否,满足条件？,步骤,A,步骤,B,是,否,程序框图,条件语句的一般格式,IF,条件,THEN,语句体,1,(,步骤,A),ELSE,语句体,2,(,步骤,B),END IF,两种循环语句：,循环体,满足条件？,是,否,（,2,）,While,（,当型）循环,WHILE,条件,循环体,WEND,DO,循环体,LOOP UNTIL,条件,（,1,）,Until,（直到型）循环,循环体,满足条件？,否,是,2.,思考：,小学学过的求两个数的最大公约数的方法？,先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来,.,例：求下面两个正整数的最大公约数：,（,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,显然,37,是,148,和,37,的最大公约数，也就是,8251,和,6105,的最大公约数,例： 用辗转相除法求,225,和,135,的最大公约数,225=1351+90,135=901+45,90=452,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,思考,1,：从上面的两个例子中可以看出计算的规律是什么？,S1,：用大数除以小数,S2,：除数变成被除数，余数变成除数,S3,：重复,S1,，直到余数为,0,辗转相除法是一个反复执行直到余数等于,0,才停止的步骤，这实际上是一个循环结构。,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m = n q,r,用程序框图表示出右边的过程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,思考：,你能把辗转相除法编成一个计算机程序吗？,(1),、算法步骤：,第一步：输入两个正整数,m,n(m,n).,第二步：计算,m,除以,n,所得的余数,r.,第三步：,m=,n,n,=r.,第四步：若,r,0,则,m,n,的最大公约数等于,m,；,否则，返回第二步,.,第五步：输出最大公约数,m.,(2),、程序框图：,开始,输入,m,n,r=m MOD n,m=n,r=0?,是,否,n=r,输出,m,结束,(3),、程序：,INPUT,m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,二、更相减损术,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否都是偶数。若是，则用,2,约简；若不是则执行第二步。,第二步：,以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。,（,1,）、,九章算术,中的更相减损术：,1,、背景介绍：,（,2,）、现代数学中的更相减损术：,2,、定义：,所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。,例,:,用更相减损术求,98,与,63,的最大公约数,.,解：由于,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减,98,63,3563,35,2835,28,728,7,21,21,7,1,4,14,7,7,所以，,98,和,63,的最大公约数等于,7,3,、方法：,1,、用更相减损术求两个正数,84,与,72,的最大公约数,练习：,思路分析：先约简，再求,21,与,18,的最大公约数,然后乘以两次约简的质因数,4,。,2,、求,324,、,243,、,135,这三个数的最大公约数。,思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。,2,、求,324,、,243,、,135,这三个数的最大公约数,2,、求,324,、,243,、,135,这三个数的最大公约数,(1),、算法步骤,第一步：输入两个正整数,a,b(a,b);,第二步：若,a,不等于,b ,则执行第三步；否则转到第五步；,第三步：把,a-b,的差赋予,r;,第四步：如果,br,那么把,b,赋给,a,把,r,赋给,b;,否则把,r,赋给,a,，执行第二步；,第五步：输出最大公约数,b.,*思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？,(2),、程序框图,是,否,是,开始,输入,a,b,a,b,?,否,输出,b,结束,b=r,a=b,r=a-b,rr THEN,a=b,b=r,ELSE,a=r,END IF,WEND,PRINT b,END,比较辗转相除法与更相减损术的区别,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到。,小结,1,、求两个数的最大公约数的两种方法分别是,（,）和（,）。,2,、两个数,21672,，,8127,的最大公约数是 （ ）,A,、,2709 B,、,2606 C,、,2703 D,、,2706,辗转相除法,更相减损术,案例2 秦九韶算法,问题,怎样求多项式,f(x)=x,5,+x,4,+x,3,+x,2,+x+1,当,x=5,时的值呢？,计算多项式,(,),=,当,x,= 5,的值,算法,1,：,因为,(,),=,所以,(,5)=5,5,5,5,5,=,3125,625,125,25,5,=,3906,算法,2,：,(,5)=5,5,5,5,5,=,5(5,5,5,5,),=,5(5(5,5,5,),),=,5(5(5(,5,+,5,+,) +,) +,) +,=,5(5(5(,5,(,5,+,) +,)+,)+,) +,分析：两种算法中各用了几次乘法运算？和几次加法运算？,算法,1,：,因为,(,),=,所以,(,5)=5,5,5,5,5,=,3125,625,125,25,5,=,3906,算法,2,：,(,5)=5,5,5,5,5,=,5(5,5,5,5,),=,5(5(5,5,5,),),=,5(5(5(,5,+,5,+,) +,) +,) +,=,5(5(5(,5,(,5,+,) +,)+,)+,) +,共做了,1+2+3+4=10,次乘法运算，,5,次加法运算。,共做了,4,次乘法运算，,5,次加法运算。,数书九章,秦九韶算法,设,是一个,n,次的多项式,对该多项式按下面的方式进行改写：,思考：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个,n,次多项式,f,(x),的值转化成求,n,个一次多项式的值的方法，称为,秦九韶算法,。,思考：在求多项式的值上，这是怎样的一个转化？,算法步骤,：,第一步：输入多项式次数,n,、最高次项的系数,a,n,和,x,的值,.,第二步：将,v,的值初始化为,a,n,，将,i,的值初始化为,n-,1.,第三步：输入,i,次项的系数,a,i,第四步：,v=,vx+a,i,i,=i,-,1.,第五步：判断,i,是否小于或等于,0,，若是，则返回第三步；否则，输出多项式的值,v,。,程序框图：,这是一个在,秦九韶算法中反复执行的步骤，因此可用循环结构来实现。,输入,a,i,开始,输入,n,a,n,x,i,0,?,输出,v,结束,v=vx+a,i,i=i,-,1,Y,N,i=,n-,1,V=a,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,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,程序,特点：,通过一次式的反复计算，逐步得出高次多项式的值，对于一个,n,次多项式，只需做,n,次乘法和,n,次加法即可。,例,1:,用秦九韶算法求多项式,f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值,.,解法一,:,首先将原多项式改写成如下形式,: f(x),=(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.,然后由内向外逐层计算一次多项式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,当,x=5,时,多项式的值是,2677.,原多项式的系数,多项式的值,.,例,1:,用秦九韶算法求多项式,f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值,.,解法二,:,列表,2,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.,例,2,已知一个五次多项式为,用秦九韶算法求这个多项式当,x = 5,的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当,x = 5,时的值：,所以，当,x = 5,时，多项式的值等于14130,.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,程序框图：,开始,输入,f(x),的系数：,a,0,a,1,a,2,a,3,a,4,a,5,输入,x,0,n5?,输出,v,结束,v=vx,0,+a,5-n,n=n+1,Y,N,n=1,v=a,5,这是一个在,秦九韶算法中反复执行的步骤，因此可用循环结构来实现。,练习、已知多项式,f(x)=x,5,+5x,4,+10x,3,+10x,2,+5x+1,用,秦九韶算法求这个多项式当,x=-2,时的值。,课堂小结：,1,、秦九韶算法的方法和步骤,2,、秦九韶算法的程序框图,案例三进位制,问题,1,我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的,.,比如时间和角度的单位用六十进位制,电子计算机用的是二进制,.,那么什么是进位制,?,不同的进位制之间又有什么联系呢,?,进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制,;,满十进一,就是十进制,;,满十六进一,就是十六进制,;,等等,.,“满几进一”,就是几进制,几进制的,基数,就是几,.,可使用数字符号的个数称为基数,.,基数都是大于,1,的整数,.,如二进制可使用的数字有,0,和,1,基数是,2;,十进制可使用的数字有,0,1,2,8,9,等十个数字,基数是,10;,十六进制可使用的数字或符号有,09,等,10,个数字以及,AF,等,6,个字母,(,规定字母,AF,对应,1015),十六进制的基数是,16.,注意,:,为了区分不同的进位制,常在数字的右下脚标明基数,.,如,111001,(2),表示二进制数,34,(5),表示,5,进制数,.,十进制数一般不标注基数,.,问题,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,一般地,若,k,是一个大于,1,的整数,那么以,k,为基数的,k,进制数可以表示为一串数字连写在一起的形式,a,n,a,n-1,a,1,a,0(k),(0a,n,k,0a,n-1,a,1,a,0,n?,否,是,输出,b,结束,程序框图：,INPUT,a,k,n,i=1,b=0,DO,b=,b+t,*k(i-1),i=i+1,LOOP UNTIL,in,PRINT,b,END,t=a MOD 10,a=a10,t=a MOD 10,程序：,例3,:,把,89,化为二进制的数,.,分析,:,把,89,化为二进制的数,需想办法将,89,先写成如下形式,89=a,n,2,n,+a,n-1,2,n-1,+a,1,2,1,+a,0,2,0,.,89=64+16+8+1=12,6,+02,5,+12,4,+12,3,+02,2,+02,1,+12,0,=1011001,(2),.,但如果数太大,我们是无法这样凑出来的,怎么办,?,89=442+,1,44=222+,0,22=112+,0,11=52+,1,5=22+,1,2=12+,0,1=02+,1,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,44 1,例3,:,把,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,取余法,.,例4,:,把,89,化为五进制的数,.,解,:,以,5,作为除数,相应的除法算式为,:,17 4,5,89,余数,5,3 2,5,0 3,89=324,(5),.,开始,输入,a,k,求,a,除以,k,的商,q,求,a,除以,k,的余数,r,把得到的余数依次从右到左排列,否,结束,输出全部余数,r,排列得到的k进制数,a=q,q=0?,是,INPUT “,a,k,=” ;,a,k,b=0,i=0,DO,q=ak,r=a MOD k,b=,b+r,*10i,i=i+1,a=q,LOOP UNTIL q=0,PRINT b,END,问题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),.,小结,进位制的概念及表示方法,;,各种进位制之间的相互转化,.,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,.,作业,:,1.,课本,P45,页,A,组,T3.,下课了！,