第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数， 只要求出6105和2146的公约数就可以了。
第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。
否
2020年9月28日
333=148×2+37
148=37×4+0
5
思考：你能把辗转相除法编成一个计算机程序吗？
程序框图：
开始 输入m,n r=m MOD n
m=n
n=r
否 r=0?
是
输出m
2020年9月28日
6
结束
程序：
INPUT “m,n=”;m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
20例20年：9月2如8日何算出8251和6105的最大公约数？
2
一、辗转相除法（欧几里得算法）
1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以 较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续 上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的 最大公约数。 2、步骤（以求8251和6105的最大公约数的过程为例）
f(x ) 2 x 5 5 x 4 4 x 3 3 x 2 6 x 7
当x=5时的值的算法，并写出程序。 （2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的 求解问题？
引导学生把多项式变形为：
f(x)2x55x44x33x26x7
((2(x(5)x4)x3)x6)x7
思考：从内到外，如果把每一个括号都看成一个常数，那么变形 后的式子中有哪些“一次式”？x的系数依次是什么？
解：由于63不是偶数，把98和63以大数减小数，并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7
所以，98和63的最大公约数等于7
2020年9月28日
8
INPUT m, n IF m<n THEN
a=m m=n n=a
END IF
K=0
WHILE m MOD 2=0 AND n MOD 2=0
第一章 算法初步
1.3 算法案例
2020年9月28日
1
辗转相除法与更相减损术
例：求下面两个正整数的最大公约数：
（1）求25和35的最大公约数 （2）求49和63的最大公约数
（1）5 25 35 57
所以，25和35的最大公 约数为5
（2）7 49 63 79
所以，49和63的最大公 约数为7
思考：除了用这种方法外还有没有其它方法？
( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
2020年9思月28考日 ：当知道了x的值后该如何求多项式的值？
12
f ( x ) ( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
2020年9月28日
3
完整的过程
例： 用辗转相除法求225和135
8251=6105×1+2146
的最大公约数 225=135×1+90
6105=2146×2+1813
135=90×1+45
2146=1813×1+333
90=45×2
1813=333×5+148
显然45是90和45的最大公约数， 也就是225和135的最大公约数
的一种改 写方式？ 最后的结
f(x ) a n x n a n 1 x n 1 a 1 x a 0 果是什么？
(a n x n 1 a n 来自1 x n 2 a 1 )x a 0
(a n ( x n 2 a n 1 x n 3 a 2 ) x a 1 ) x a 0
PRINT m
2020年9月28日
END
7
二、更相减损术
1.定义：所谓更相减损术，就是对于给定的两个数，用较大的数减去较 小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较 小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数 便为原来两个数的最大公约数。
2、方法：
例: 用更相减损术求98与63的最大公约数.
辗转相除法是一个反复执行直到余数等于0才停 止的步骤，这实际上是一个循环结构。
用程序框图表示出右边的过程 m = n × q ＋ r
8251=6105×1+2146
r=m MOD n m=n n=r
6105=2146×2+1813 2146=1813×1+333 1813=333×5+148
r=0? 是
m=m/2 n=n/2 k=k+1
WEND
d=m-n
WHILE d<>n IF d>n THEN
2020年9月28日
m=d
思考：你能根据更相 减损术设计程序，求 两个正整数的最大公 约数吗？
ELSE
m=n n=d
END IF
d=m-n
WEND
d=2 k*d
PRINT d END
9
三、秦九韶算法
（1）设计求多项式
（4）用秦九韶算法求多项式的值，与多项式组成有直接关 系吗？用秦九韶算法计算上述多项式的值，需要多少次乘
？ 法运算和多少次加法运算
2020年9月28日
计算只与多项式的 系数有关，
11
《数书九章》——秦九韶算法
设f (x) 是一个n 次的多项式
这是怎样
f(x ) a n x n a n 1 x n 1 a 1 x a 0 对该多项式按下面的方式进行改写：
2020年9月28日
10
（3）若将x的值代入变形后的式子中，那么求值的计算过程是怎样 的？
将变形前x的系数乘以x的值，加上变形前的第2个系数，得到一个新 的系数；将此系数继续乘以x的值，再加上变形前的第3个系数，又得到一 个新的系数；继续对新系数做上面的变换，直到与变形前的最后一个系数 相加，得到一个新的系数为止。这个系数即为所求多项式的值。这种算法 即是“秦九韶算法”
333=148×2+37
思考：从上面的两个例子中可 以看出计算的规律是什么？
148=37×4+0
S1：用大数除以小数
显然37是148和37的最大 S2：除数变成被除数，余数 公约数，也就是8251和 变成除数
61020520的年9月最28日大公约数
S3：重复S1，直到余数为04
思考：辗转相除法中的关键步骤是哪种逻辑结构？