算法初步复习课.ppt

算法初步复习课,辗转相除法（欧几里得算法）:就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。,更相减损术:就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。,1.求324，243，270三个数的最大公约数.,27,将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。,2.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.,解1:f(x)=(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=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,所以,当x=5时,多项式的值是2677.,2-5-4 3-6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,当x=5时,多项式的值是2677.,原多项式的系数,多项式的值,解2:,2,2.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.,练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.,解:f(x)=2x6-5x5+0 x4-4x3+3x2-6x+0,V4=404,4.将五进制数30241（5）转化为七进制数.,30241（5）=354+252+45+1=1946.,30241（5）=5450（7）,“K进制”,把八进制数2376（8）化为五进制数.,2376（8）=1278=20103（5）,条件结构的程序表示,IF 条件 THEN 语句1ELSE 语句2END IF,IF 条件 THEN 语句END IF,WHILE 条件 循环体WEND,DO 循环体LOOP UNTIL 条件,While（当型）循环,Until（直到型）循环,5.阅读下列程序：若输入的两个数m=428，n=284，求计算机输出的数.,4,6.如图所示，程序框图（算法流程图）的输出结果是,15,7.执行右面的程序框图，如果输入的n是4，则输出的P是A8；B5；C3；D2,C,B,