Задача 76214
|
|
 |
Условие
Написать вариант алгоритма Евклида, использующий соотношения
НОД(2a, 2b) = 2·НОД(a,b),
НОД(2a,b) = НОД(a,b)
при нечётном b,
не включающий деления с остатком, а использующий лишь
деление на 2 и проверку чётности. (Число действий
должно быть порядка
log k для исходных данных,
не превосходящих k.)
Решение
m:= a; n:=b; d:=1;
{НОД(a,b) = d * НОД(m,n)}
while not ((m=0) or (n=0)) do begin
| if (m mod 2 = 0) and (n mod 2 = 0) then begin
| | d:= d*2; m:= m div 2; n:= n div 2;
| end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
| | m:= m div 2;
| end else if(m mod 2 = 1) and (n mod 2 = 0) then begin
| | n:= n div 2;
| end else if (m mod 2=1) and (n mod 2=1) and (m>=n) then begin
| | m:= m-n;
| end else if (m mod 2=1) and (n mod 2=1) and (m<=n) then begin
| | n:= n-m;
| end;
end;
{m=0 => ответ=d*n; n=0 => ответ=d*m}
Оценка числа действий: каждое второе действие делит хотя бы
одно из чисел m и n пополам.
