算法初步复习课.ppt

《算法初步复习课.ppt》由会员分享，可在线阅读，更多相关《算法初步复习课.ppt（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法初步复习课 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）:就是对于给定的两个就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。数的最大公约数。更相减损

2、术更相减损术:就是对于给定的两个数，用较大的数减就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。的最大公约数。1.1.求求324324，243243，270270三个数的最大公约数三个数的最大公约数.2727将求一个将求一个n n次多项式次多项式f f(x)(x)的值的值转化成求转化成求n n个一次个一次多项式的值多项式的

3、值的方法，称为的方法，称为秦九韶算法秦九韶算法。2.2.用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x f(x)=2x5 5-5x-5x4 4-4x-4x3 3+3x+3x2 2-6x+7-6x+7当当x=5x=5时的值时的值.解解1:f(x)=(2x-5)x-4)x+3)x-6)x+71:f(x)=(2x-5)x-4)x+3)x-6)x+7v v0 0=2 =2 v v1 1=v=v0 0 x-5=25-5=5x-5=25-5=5v v2 2=v=v1 1x-4=55-4=21x-4=55-4=21v v3 3=v=v2 2x+3=215+3=108x+3=215+3=108v v

4、4 4=v=v3 3x-6=1085-6=534x-6=1085-6=534v v5 5=v=v4 4x+7=5345+7=2677x+7=5345+7=2677所以所以,当当x=5x=5时时,多项多项式的值是式的值是2677.2677.2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,当当x=5时时,多项式的值是多项式的值是2677.原多项式的系数原多项式的系数多项式的值多项式的值解解2:2:22.2.用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x f(x)=2x5 5-5x-5x4 4-4x-4x3 3+3x+3x2 2-6x+7-

5、6x+7当当x=5x=5时的值时的值.练一练练一练:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2xf(x)=2x6 6-5x-5x5 5-4x-4x3 3+3x+3x2 2-6x-6x当当x=5x=5时的值时的值.解解:f(x)=2x:f(x)=2x6 6-5x-5x5 5+0 0 xx4 4-4x-4x3 3+3x+3x2 2-6x+-6x+0 02 -5 0 -4 3 -6 0 x=510525251251216056083040303421517015170 3.3.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-

6、1n-1+a+a1 1x+ax+a0 0的值，令的值，令v0=an，v vk k=v=vk-1k-1x+ax+an-kn-k(k=1(k=1，2 2，n).n).若若f(x)=3xf(x)=3x5 5+4x+4x4 4+5x+5x3 3+2x+2x2 2+2x+1,+2x+1,当当x=3x=3时，求时，求v v4 4的值的值.V V4 4=404=404 4.4.将五进制数将五进制数3024130241（5 5）转化为七进制数转化为七进制数.3024130241（5 5）=35=354 4+25+252 2+45+1=1946.+45+1=1946.0757397278719460545余数余

7、数3024130241（5 5）=5450=5450（7 7）“K K进制进制”把八把八进制数进制数23762376（8 8）化为五进制数化为五进制数.23762376（8 8）=1278=20103=1278=20103（5 5）条件结构的程序表示条件结构的程序表示IF 条件条件 THEN 语句语句1ELSE 语句语句2END IF满足条件？满足条件？语句语句1语句语句2是是否否IF 条件条件 THEN 语句语句END IF满足条件？满足条件？语句语句是是否否WHILE 条件条件 循环体循环体WENDDO 循环体循环体LOOP UNTIL 条件条件 是是AP 否否AP 是是 否否While（

8、当型）循环（当型）循环Until（直到型）循环（直到型）循环5.5.阅读下列程序：若输入的两个数阅读下列程序：若输入的两个数m=428m=428，n=284n=284，求计算机输出的数，求计算机输出的数.INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND4 46.6.如图所示，程序框如图所示，程序框图（算法流程图）的图（算法流程图）的输出结果是输出结果是 15 7.7.执行右面的程序框图，执行右面的程序框图，如果输入的如果输入的n n是是4 4，则输出的，则输出的P P是是A A8 8；B B5 5；C C3 3；D D2 2C C8.阅读右边的程序框图，若输出的值为，则判断框内可填写（）9.如右框图，当时，等于（）(A)7 (B)8 (C)10 （D）11B B