TheEuclideanalgorithmisusedtofindthegreatestcommondivisor(gcd)oftwopositiveintegers(继续)aandb.input(a)input(b)whileb>0beginr:=amodba:=bb:=rendgcd:=aoutput(gcd)Whenthealgorithmisusedtofin

Question

The Euclidean algorithm is used to find the greatest common divisor (gcd) of two positive integers
(继续)a and b.
input (a)
input (b)
while b>0
begin
r:=a mod b
a:=b
b:=r
end
gcd:=a
output(gcd)
When the algorithm is used to find the greatest common divisor of a =273 and b=110, which of the following is the sequence of computed values for r?
(A)2,26,1,0
(B)2,53,1,0
(C)53,2,1,0
(D)53,4,1,0
(E) 53,5,1,0
选D,怎么做的?
程序里的":="是什么意思?

Answer 1

这是求最大公约数的算法,在这个程序中":="应该就是赋值号,就是把符号右边变量的值赋给左边变量,mod是取余的函数,循环语句中
第一次 a=273 ,b=110 ,a/b的余数r=53
第二次 a=110 ,b=53 ,r=4
第三次 a=53 ,b=4 ,r=1
第四次 a= 4 ,b=1 ,r=0
因而r 的取值为 D