文档介绍：算法案例
第1课时辗转相除法与更相减损术、秦九韶算法
,了解其执行过程,并会求最大公约数.
,了解它提高计算效率的实质,并会求多项式的值.
.
(1)辗转相除法.
①算法步骤:
第一步,给定两个正整数m,n.
第二步,计算m除以n所得的余数r.
第三步,m=n,n=r.
第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.
②程序框图:
③程序:
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
(2)更相减损术.
算法分析:
第一步,任意给定两个正整数,,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,,直到所得的差与减数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
【做一做1】用更相减损术求156和48的最大公约数时,第一步是. 
答案:用2约简
(1)概念:求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求n个一次多项式的值,:
改写多项式为:
f(x)=anxn+an-1xn-1+…+a1x+a0
=(anxn-1+an-1xn-2+…+a1)x+a0
=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0
=…
=(…((anx+an-1)x+an-2)x+…+a1)x+a0.
设v1=anx+an-1,
v2=v1x+an-2,v3=v2x+an-3,…
vn=vn-1x+a0.
(2)算法步骤:
第一步,输入多项式的次数n、最高次项的系数an和x的值.
第二步,将v的值初始化为an,将i的值初始化为n-1.
第三步,输入i次项的系数ai.
第四步,v=vx+ai,i=i-1.
第五步,,则返回第三步;否则,输出多项式的值v .
(3)程序框图:
(4)程序:
INPUT “n=”;n
INPUT “an=”;a
INPUT “x=”;x
v=a
i=n-1
WHILE i>=0
PRINT “i=”;i
INPUT “ai=”;a
v=v􀆽 x+a 
i=i-1
WEND
PRINT v
END