Question

用辗转相除法和更相减损之术求两个正数a，b(a＞b)的最大公约数，写出算法.

Answer 1

分析：辗转相除法的理论依据是a=nb+r,∴r=a-nb得a，b与b，r有相同的公约数，更相减损之术的理论依据是a-b=r,∴a=b+r,即a，b与b，r有相同公约数.

解：辗转相除法：

S1  输入两个正数a，b(a＞b)；

S2  如果a除以b的余数不等于0执行S3,否则转到S4；

S3  把a÷b的余数赋予r，把b赋予a，把r赋予b，重新执行S2；

S4  输出最大公约数b.

更相减损之术：

S1  输入两个正数a，b(a＞b)；

S2  如果a≠b，则执行S3,否则转到S5；

S3  将a-b的差赋予r；

S4  若b＞r，则把b赋予a，把r赋予b，否则把r赋予a，重新执行S2；

S5  输出最大公约数b.

绿色通道

    通过上例可以发现用辗转相除法和更相减损之术求得的最大公约数是相同的，但用辗转相除法的步骤较少，而用更相减损之术运算简单，却步骤较多，在解题时应灵活选择解法.

专题5秦九韶算法

总结:用秦九韶算法求多项式的值时，首先要对多项式f(x)=a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀进行整理成f(x)=(… ((a_nx+a_n-1)x+a_n-2)x+…+a₁)x+a₀，然后由内向外逐次计算，直到结束 .