算法案例课件.ppt

1、算法案例算法案例1.31.3主要内容1.3.1辗转相除法与更相减损术1.3.2秦九韶算法1.3.3进位制辗转相除法辗转相除法更相减损术更相减损术1.1.11、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求225和和135的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1）55357所以，所以，25和和35的最大公约数为的最大公约数为5所以，所以，225和和135的最大公约数为的最大公约数为533=45课前复习225（2）545135273159知识回顾：知识回顾：先用先用两个数公有的质两个数公

2、有的质因数连续去除，因数连续去除，一直除到所得的一直除到所得的商是互质数为止，商是互质数为止，然后把所有的除然后把所有的除数连乘起来数连乘起来335辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得用两数中较大的数除以较小的数，求得商商和和余数余数8251=61051+2146结论：结论：8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2

3、146的公约数的公约数就可以了。就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大的最大公约数。公约数。完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的

4、最大公约数，也就是数，也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计：从上面的两个例子可以看出计算的规律是什么？算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是停止的步骤，这实际上是一个循环结构。一个循环结构。m=n q r用程序框图

5、表示出右边的过程用程序框图表示出右边的过程否r=m MOD nm=nn=rr=0?是辗转相除法的程序框图辗转相除法的程序框图开始开始输入输入m,nr=m MOD nm=nn=rr=0?输出输出m结束结束是是否否INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND 1、用辗转相除法求下列两数的最大公约数：（1）（123，48）（2）（72，168）（3）（153，119）（4）（4081,20723）3532417课堂练习：课堂练习：2、下面是求115与276的最大公约数的程序，把程序补充完整。a=115b=276DO r=_ a=b b=r

6、LOOP UNTIL r=_PRINT aEND更相减损术更相减损术算理算理：可半者半之，不可半者，副置分母、子之数，以少可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。减多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是任意给定两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2 2约简；若不是，则执行第二步。约简；若不是，则执行第二步。第二步：第二步：以以较大的数减较小的数较大的数减较小的数，接着把所得的差与，接着把所得的差与较小的数比较，并以较小的数比较，并以大数减小数大数减小数。继续这个操作，直。继续这个

7、操作，直到所得的到所得的减数和差相等为止减数和差相等为止，则这个等数或这个等数，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。与约简的数的乘积就是所求的最大公约数。例例1 1、用更相减损术求、用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减，即：即：986335;633528;35287;28721;21714;1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习：用更相减损术求两个正数练习：用更相减损术求两个正数8484与

8、与7272的最大的最大公约数。公约数。(12)(12)二者算理相似，有异曲同工之妙二者算理相似，有异曲同工之妙1 1、都是求最大公约数的方法，计算上辗转相除、都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明两个数字大小区别较大时计算次数的区别较明显。显。2 2、从结果体现形式来看，辗转相除法体现结果、从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减则得到，而

9、更相减损术则以减数与差相等而得到（差为数与差相等而得到（差为0 0）辗转相除法与更相减损术的区别辗转相除法与更相减损术的区别2、求、求324、243、135这三个数的最大公约数这三个数的最大公约数.27135243324.2713581,022754,2715481,54181135.812433240381243811243324的最大公约数为、所以，三个数的最大公约数为与则又的最大公约数为与则1、用辗转相除法求、用辗转相除法求 294 与与84的最大公约数，再用的最大公约数，再用更相减损术验证。更相减损术验证。课堂练习：课堂练习：秦九韶算法1.3.2问题问题1怎样求多项式怎样求多项式f(x

10、)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值？时的值？方法一：把方法一：把5代人多项式代人多项式f(x)，计算各项的值，然后把，计算各项的值，然后把它们加起来，这时我们一共做了它们加起来，这时我们一共做了5+4+3+2+1=15次乘法次乘法运算运算,5次加法运算次加法运算.方法二：先计算方法二：先计算x2,然后依次计算然后依次计算的值，这样每次都可以利用上一次计算的结果，这时的值，这样每次都可以利用上一次计算的结果，这时我们一共需要我们一共需要9次乘法运算次乘法运算,5次加法运算次加法运算.222,(),()xx xxxxxxx问题问题2能否探索更好的算法能否探索更好的算法,来

11、解决任意多项式来解决任意多项式的求值问题的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677这种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法.0111)(axaxaxaxfnnnn设设)(xf是一个是一个n次

12、的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn这是怎样的一种改写方式？最后的结果是什么？0121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一项是什么？这种将求一个这种将

13、求一个n次多项式次多项式f（x）的值转化成求）的值转化成求n个一次多项式的值的个一次多项式的值的方法，称为方法，称为秦九韶算法秦九韶算法。点评点评:秦九韶算法是求一元多项式的秦九韶算法是求一元多项式的值的一种方法值的一种方法.它的特点是它的特点是:把求一个把求一个n次多项式的值次多项式的值转化为求转化为求n个一次多项式的值个一次多项式的值,通过这种转通过这种转化化,把运算的次数由至多把运算的次数由至多n(n+1)/2次乘法次乘法运算和运算和n次加法运算次加法运算,减少为减少为n次乘法运算次乘法运算和和n次加法运算次加法运算,大大提高了运算效率大大提高了运算效率.v1=anx+an-1,v2=v

14、1x+an-2,v3=v2x+an-3,vn=vn-1x+a0.观察上述秦九韶算法中的观察上述秦九韶算法中的n个一次式个一次式,可见可见vk的计算要用到的计算要用到vk-1的值的值.若令若令v0=an,得得v0=an,vk=vk-1x+an-k (k=1,2,n)这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步骤骤,因此可用循环结构来实现因此可用循环结构来实现.程序框图程序框图v=vx+aiINPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILE i=0 PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1W

15、ENDPRINT vEND否否开始开始输入输入n,an,x的值的值i0?i=n-1v=ani=i-1输出输出v结束结束是是输入输入ai765432765432()f xxxxxxxx 1、用秦九韶算法求多项式、用秦九韶算法求多项式当当x=3时的值时的值.课堂练习课堂练习f(3)=213247654321()()f xxxxxxxx当当x=5时时,多项式的值是多项式的值是15170.2、用秦九韶算法求多项式、用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当当x=5时的值时的值.解解:原多项式先化为原多项式先化为:f(x)=2x6-5x5+0 x4-4x3+3x2-6x+0

16、注意注意:n次多项式有次多项式有n+1项项,因此缺少哪一项应因此缺少哪一项应将其系数补将其系数补0.进位制1.3.3 问题问题11我们常见的数字都是十进制的我们常见的数字都是十进制的,但是并不是生但是并不是生活中的每一种数字都是十进制的活中的每一种数字都是十进制的.比如时间和角度的比如时间和角度的单位用六十进位制单位用六十进位制,电子计算机用的是二进制电子计算机用的是二进制.那么什那么什么是进位制么是进位制?不同的进位制之间又有什么联系呢不同的进位制之间又有什么联系呢?进位制是人们为了计数和运算的方便而约定的一种进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一记数系统，约定满

17、二进一,就是二进制就是二进制;满十进一满十进一,就就是十进制是十进制;满十六进一满十六进一,就是十六进制就是十六进制;等等等等.“满几进一满几进一”,就是几进制就是几进制,几进制的几进制的基数基数就是几就是几.可使用数字符号的个数称为基数可使用数字符号的个数称为基数.基数基数都是大于都是大于1 1的整数的整数.例如：二进制可使用的数字有例如：二进制可使用的数字有0和和1,基数是基数是2;十进制可使用的数字有十进制可使用的数字有0,1,2,8,9等十个数字等十个数字,基基数是数是10;十六进制可使用的数字或符号有十六进制可使用的数字或符号有09等等10个数字个数字以及以及AF等等6个字母个字母(

18、规定字母规定字母AF对应对应1015),十六进十六进制的基数是制的基数是16.注意注意:为了区分不同的进位制为了区分不同的进位制,常在数字的右下常在数字的右下脚标明基数脚标明基数,.,.如如111001111001(2)(2)表示二进制数表示二进制数,34,34(5)(5)表示表示5 5进制数进制数.十进制数一般不标注基数十进制数一般不标注基数.问题问题2十进制数十进制数3721中的中的3表示表示3个千个千,7表示表示7个百个百,2表示表示2个十个十,1表示表示1个一个一,从而它可以写成下面的形式从而它可以写成下面的形式:3721=3103+7102+2101+1100.想一想二进制数想一想二

19、进制数1011(2)可以类似的写成什么形式可以类似的写成什么形式?1011(2)=123+022+121+120.同理同理:3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162 +1161+6160.一般地一般地,若若k是一个大于是一个大于1的整数的整数,那么以那么以k为基数的为基数的k进制数可以表示为一串数字连写在一起的形式进制数可以表示为一串数字连写在一起的形式anan-1a1a0(k)(0ank,0an-1,a1,a0n?输出输出b结束结束 否否是是INPUT a,k,ni=1b=0t=a MOD 10DO b=b+t*k(i-1)a=a1

20、0 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND程序程序:程序框图：程序框图：输入输入a,k,n例例2:把把89化为二进制的数化为二进制的数.分析分析:把把89化为二进制的数化为二进制的数,需将需将89先写成如下形式先写成如下形式89=an2n+an-12n-1+a121+a020.89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).但如果数太大但如果数太大,我们是无法这样凑出来的我们是无法这样凑出来的,怎么办怎么办?89=442+1,44=222+0,22=112+0,11=52+1,5=22+1,2=

21、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=126+025+124+123+022+021+120=1011001(2).可以用可以用2连续去除连续去除89或所或所得商得商(一直到商为一直到商为0为止为止),然后取余数然后取余数-除除2取余法取余法.2=12+0,1=02+1,44 1例例2:把把89化为二进制的数化为二

22、进制的数.我们可以用下面的除法算式表示除我们可以用下面的除法算式表示除2取余法取余法:289 余数余数222 0211 025 122 121 020 1把算式中各步所得的余数把算式中各步所得的余数从下到上排列从下到上排列,得到得到89=1011001(2).这种方法也可以推广为把这种方法也可以推广为把十进制数化为十进制数化为k进制数的进制数的算法算法,称为称为除除k取余法取余法.解解:以以5作为除数作为除数,相应的除法算式为相应的除法算式为:17 4589 余数余数53 250 3 89=324(5).例例3:把把89化为五进制的数化为五进制的数.问题问题5你会把三进制数你会把三进制数102

23、21(3)化为二进制数吗化为二进制数吗?解解:第一步第一步:先把三进制数化为十进制数先把三进制数化为十进制数:10221(3)=134+033+232+231+130 =81+18+6+1=106.第二步第二步:再把十进制数化为二进制数再把十进制数化为二进制数:106=1101010(2).10221(3)=106=1101010(2).例例 设计一个程序，实现设计一个程序，实现“除除k k取余法取余法”（kNkN，2k92k9）第一步：给定的十进制正整数第一步：给定的十进制正整数a a和转化后的数的基数和转化后的数的基数k k 第二步：求出第二步：求出a a除以除以k k所得的商所得的商q

24、q，余数，余数r.r.第三步：把得到的余数依次从右到左排列第三步：把得到的余数依次从右到左排列.第四步：若第四步：若q0q0，则，则a=qa=q，返回第二步；否则，输出全，返回第二步；否则，输出全部余数部余数r r排列得到的排列得到的k k进制数进制数.程序框图：程序框图：开始开始输入输入a,k求求a除以除以k的商的商q求求a除以除以k的余数的余数ra=qq=0?输出全部余数输出全部余数r排列得到的排列得到的k进制数进制数结束结束把得到的余数依次从把得到的余数依次从右到左排列右到左排列是是否否INPUT “a,k=”;a,kb=0i=0DO q=ak r=a MOD k b=b+r*10i i

25、=i+1 a=qLOOP UNTIL q=0PRINT bEND程序程序:例例 设计一个程序设计一个程序,实现实现“除除k k取余法取余法”.课堂练习课堂练习1、完成下列进位制之间的转化：、完成下列进位制之间的转化：（1）10231（4）=（10）；（2）235（7）=（10）；（3）137（10）=（6）；（4）1231（5）=（7）；（5）213（4）=（3）；（6）1010111（2）=（4）。301124345362111011132 2、已知已知10b110b1（2 2）=a02=a02（3 3）,求数字求数字a a，b b的值的值.所以所以2b+9=9a+22b+9=9a+2，即，即9a-2b=7.9a-2b=7.10b110b1（2 2）=1=12 23 3+b+b2+1=2b+9.2+1=2b+9.a02a02（3 3）=a=a3 32 2+2=9a+2.+2=9a+2.故故a=1a=1，b=1.b=1.