The Euclidean algorithm is used to find the greatest common divisor (gcd) of two positive integers
问题描述：
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,怎么做的?
程序里的":="是什么意思?
答
这是求最大公约数的算法,在这个程序中":="应该就是赋值号,就是把符号右边变量的值赋给左边变量,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