《13算法案例》由会员分享，可在线阅读，更多相关《13算法案例（26页珍藏版）》请在金锄头文库上搜索。
1、算算 法法 案案 例例案例一：案例一：辗转相除法辗转相除法与与更相减损术更相减损术设问一：如何求两个正整数225、135 的最大公约数？所以，225、135的最大公约数为45. 设问一：如何求两个正整数设问一：如何求两个正整数225、135 的最大公约数？的最大公约数？方法二：辗转相除法：最后的余数45即为225、135的最大公约数.定理：定理：设问一：如何求两个正整数设问一：如何求两个正整数225、135 的最大公约数？的最大公约数？【练习练习】应用辗转相除法求下应用辗转相除法求下列各组数的最大公约数：列各组数的最大公约数： （1）153，119（2）72，168（3）8251，6105（4
2、）168，56，264设问二设问二你能把辗转相除法你能把辗转相除法编成一个计算机程序吗？编成一个计算机程序吗？ INPUT m,nIF mn THEN x=m m=n n=xEND IFDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND案例二：秦九韶算法案例二：秦九韶算法方法一:直接代入，共做了1+2+3=6 次乘法，4次加法运算。 秦九韶算法秦九韶算法在这个运算过程中，共进行了几次乘法运算？几次加法运算？例例1：应用秦九韶算法求多项式：应用秦九韶算法求多项式f(x)=5x5+2x4+3.5x3-2.6x2-0.8当当x=5时的值时的值.V0=5V1=55
3、+2=27V2=275+3.5=138.5V3=138.55-2.6=689.9V4=689.95+0=3449.5V5=3449.55-0.8=17246.7练习练习1：应用秦九韶算法求多项式：应用秦九韶算法求多项式f(x)=0.83x5+0.41x4+0.33x2+0.5x+1当当x=3时的值时的值.V0=0.83V1=0.833+0.41=2.9V2=2.93+0=8.7V3=8.73+0.33=26.43V4=26.433+0.5=79.79V5=79.793+1=240.37练习练习2：应用秦九韶算法求多项式：应用秦九韶算法求多项式f(x)=5x5+4x4+3x3+2x2+x当当x=
4、1的值的值时，求时，求v3.V0=5V1=51+4=9V2=91+3=12V3=121+2=14秦九韶算法算法分析：秦九韶算法算法分析：INPUT “n=,an=,x=”; n,a,xv=ai=n-1DO PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1LOOP UNTIL in是否成是否成 立？立？ 若是，则输出若是，则输出b b； 否则，返回否则，返回S3.INPUT INPUT a,k,na,k,nb=0b=0i=1i=1DODO t=a MOD 10 t=a MOD 10 b= b=b+tb+t*k(i-1)*k(i-1) a=a10 a=a10 i=i
5、+1 i=i+1LOOP UNTIL inLOOP UNTIL inPRINT bPRINT bEND例例3.(1)将将89化为二进制数。化为二进制数。二、十进制转化为二、十进制转化为k进制（除进制（除k取余法）取余法）(2)将将65化为化为7进制数。进制数。练习：练习：完成下列进位制之间的转化：完成下列进位制之间的转化：例例4.设计一个程序，实现设计一个程序，实现“除除k取余法取余法”.S1:S1:输入输入a,ka,kS2:b=0,i=1S2:b=0,i=1S3:t=a MOD kS3:t=a MOD kS4:b=S4:b=b+tb+t*10(i-1)*10(i-1)S5:a=akS5:a=akS6:i=i+1S6:i=i+1S7:S7:判断判断a=0a=0是否成立？是否成立？ 若是，则输出若是，则输出b b； 否则，返回否则，返回S3.INPUT INPUT a,ka,kb=0b=0i=1i=1DODO t=a MOD k t=a MOD k b= b=b+tb+t*10(i-1)*10(i-1) a=ak a=ak i=i+1 i=i+1LOOP UNTIL a=0LOOP UNTIL a=0PRINT bPRINT bEND
