《算法案例一课时.ppt》由会员分享,可在线阅读,更多相关《算法案例一课时.ppt(45页珍藏版)》请在三一办公上搜索。
1、算 法 案 例,案例1 辗转相除法与更相减损术,1.回顾算法的三种表述:,自然语言,程序框图,程序语言,(三种逻辑结构),(五种基本语句),2.思考:,小学学过的求两个数最大公约数的方法?,先用两个公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.,1、求两个正整数的最大公约数,(1)求25和35的最大公约数(2)求49和63的最大公约数,所以,25和35的最大公约数为5,所以,49和63的最大公约数为7,2、除了用这种方法外还有没有其它方法?,算出8256和6105的最大公约数.,辗转相除法(欧几里得算法),观察用辗转相除法求8251和6105的最大公约数的过程,
2、第一步 用两数中较大的数除以较小的数,求得商和余数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,例
3、2 用辗转相除法求225和135的最大公约数,225=1351+90,135=901+45,90=452,显然37是148和37的最大公约数,也就是8251和6105的最大公约数,显然45是90和45的最大公约数,也就是225和135的最大公约数,思考1:从上面的两个例子可以看出计算的规律是什么?,S1:用大数除以小数,S2:除数变成被除数,余数变成除数,S3:重复S1,直到余数为0,辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是一个循环结构。,m=n q r,用程序框图表示出右边的过程,r=m MOD n,m=n,n=r,r=0?,是,否,思考2:辗转相除法中的关键步骤是哪种逻
4、辑结构?,1、辗转相除法(欧几里得算法),(1)算理:所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数。,(2)算法步骤,第一步:输入两个正整数m,n(mn).第二步:计算m除以n所得的余数r.第三步:m=n,n=r.第四步:若r0,则m,n的最大公约数等于m;否则转到第二步.第五步:输出最大公约数m.,(3)程序框图,(4)程序,INPUT“m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND,九章算术
5、更相减损术,算理:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。,第一步:任意给定两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步。,第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数。,2、更相减损术,(1)算理:所谓更相减损术,就是对于给定的两个数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,再用较大的数减去较小的数,反复执行此步骤直到差数和较小的数相等,此时相等的两数便为原来两个数的最大公约数。,(2)算法步骤,第一步:
6、输入两个正整数a,b(ab);第二步:若a不等于b,则执行第三步;否则转到第五步;第三步:把a-b的差赋予r;第四步:如果br,那么把b赋给a,把r赋给b;否则把r赋给a,执行第二步;第五步:输出最大公约数b.,(3)程序框图,(4)程序,INPUT“a,b=“;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND,输入a,b,是,否,b=r,a=b,r=a-b,a=r,否,是,例3 用更相减损术求98与63的最大公约数,解:由于63不是偶数,把98和63以大数减小数,并辗转相减,98633563352835287
7、28721217211477,所以,98和63的最大公约数等于7,先约简,再求21与18的最大公约数,然后乘以两次约简的质因数4,例3、求324、243、135这三个数的最大公约数。,思路分析:求三个数的最大公约数可以先求出两个数的最大公约数,第三个数与前两个数的最大公约数的最大公约数即为所求。,比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到
8、,小结,案例2 秦九韶算法,1.回顾算法的三种表述:,自然语言,程序框图,程序语言,(三种逻辑结构),(五种基本语句),案例2、秦九韶算法,问题,怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?,计算多项式()=当x=5的值,算法1:,因为()=,所以(5)=55555,=3125625125255,=3906,算法2:,(5)=55555,=5(5555),=5(5(555),=5(5(5(5+5+)+)+)+,=5(5(5(5(5+)+)+)+)+,分析:两种算法中各用了几次乘法运算?和几次加法运算?,算法1:,算法2:,共做了1+2+3+4=10次乘法运算,5次加法
9、运算。,共做了4次乘法运算,5次加法运算。,数书九章秦九韶算法,对该多项式按下面的方式进行改写:,思考:当知道了x的值后该如何求多项式的值?,这是怎样的一种改写方式?最后的结果是什么?,要求多项式的值,应该先算最内层的一次多项式的值,即,然后,由内到外逐层计算一次多项式的值,即,最后的一项是什么?,这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法。,思考:在求多项式的值上,这是怎样的一个转化?,算法步骤:,第一步:输入多项式次数n、最高次项的系数an和x的值.,第二步:将v的值初始化为an,将i的值初始化为1.,第三步:输入i次项的系数an-i.,第四步:v=
10、vx+an-i,i=i+1.,第五步:判断i是否小于或等于n,若是,则返回第三步;否则,输出多项式的值v。,程序框图:,这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。,特点:通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可。,例2 已知一个五次多项式为,用秦九韶算法求这个多项式当x=5的值。,解:,将多项式变形:,按由里到外的顺序,依此计算一次多项式当x=5时的值:,所以,当x=5时,多项式的值等于17255.2,你从中看到了怎样的规律?怎么用程序框图来描述呢?,程序框图:,这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实
11、现。,课堂小结:1、秦九韶算法的方法和步骤2、秦九韶算法的程序框图,k进制化十进制,知识探究(一):进位制的概念,思考1:进位制是为了计数和运算方便而约定的记数系统,如逢十进一,就是十进制;每七天为一周,就是七进制;每十二个月为一年,就是十二进制,每六十秒为一分钟,每六十分钟为一个小时,就是六十进制;等等.一般地,“满k进一”就是k进制,其中k称为k进制的基数.那么k是一个什么范围内的数?,如二进制可使用的数字有0和1,基数是2;十进制可使用的数字有0,1,2,8,9等十个数字,基数是10;十六进制可使用的数字或符号有09等10个数字以及AF等6个字母(规定字母AF对应1015),十六进制的基
12、数是16.,注意:为了区分不同的进位制,常在数字的右下脚标明基数,.,如111001(2)表示二进制数,34(5)表示5进制数.,十进制数一般不标注基数.,思考2:十进制使用09十个数字,那么五进制、七进制分别使用哪些数字?,思考3:在十进制中10表示十,在二进制中10表示2.一般地,若k是一个大于1的整数,则以k为基数的k进制数可以表示为一串数字连写在一起的形式:anan-1a1a0(k).其中各个数位上的数字an,an-1,a1,a0的取值范围如何?,思考4:十进制数4528表示的数可以写成4103+5102+2101+8100,依此类比,二进制数110011(2),八进制数 7342(8
13、)分别可以写成什么式子?,110011(2)=125+124+023+022+121+120,7342(8)=783+382+481+280.,思考5:一般地,如何将k进制数 anan-1a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式?,思考6:在二进制中,0+0,0+1,1+0,1+1的值分别是多少?,知识探究(二):k进制化十进制的算法,思考1:二进制数110011(2)化为十进制数是什么数?,110011(2)=125+124+023+022+121+120=32+16+2+1=51.,思考2:二进制数右数第i位数字ai化为十进制数是什么数?,练习:C7A16(16)=12
14、164+7163+10162+1161+6160.,思考3:把二进制数 化为十进制数b的算法步骤如何设计?,第二步,令b=0,i=1.,第四步,判断in 是否成立.若是,则输 出b的值;否则,返回第三步.,第一步,输入a和n的值.,第三步,i=i+1.,思考4:按照上述思路,把k进制数 化为十进制数b的算法步骤如何设计?,第四步,判断in 是否成立.若是,则输出b的值;否则,返回第三步.,第一步,输入a,k和n的值.,第二步,令b=0,i=1.,第三步,i=i+1.,思考5:上述把k进制数 化为十进制数b的算法的程序框图如何表示?,思考6:该程序框图对应的程序如何表述?,INPUT a,k,n
15、,b=0,i=1,t=a MOD10,DO,b=b+t*k(i-1),a=a10,t=a MOD10,i=i+1,LOOP UNTIL in,PRINT b,END,例1 将下列各进制数化为十进制数.(1)10303(4);(2)1234(5).,理论迁移,10303(4)=144+342+340=307.,1234(5)=153+252+351+450=194.,例2 已知10b1(2)=a02(3),求数字a,b的值.,所以2b+9=9a+2,即9a-2b=7.,10b1(2)=123+b2+1=2b+9.,a02(3)=a32+2=9a+2.,故a=1,b=1.,1.k进制数使用0(k-1)共k个数字,但左侧第一个数位上的数字(首位数字)不为0.,小结,2.用 表示k进制数,其中k称为基数,十进制数一般不标注基数.,3.把k进制数化为十进制数的一般算式是:,