Алгоритм Евклида

Повторение

1. Какие циклы с условиями вы знаете?
2. В чем сходство и в чем отличие этих циклов?

Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Алгоритм Евклида нахождения НОД основан на следующих свойствах этой величины. Пусть x и y одновременно не равные нулю целые неотрицательные числа и пусть x>=y, тогда если y = 0, то НОД(x, y) = x, а если y не равен 0, то для чисел x, y и r, где r - остаток от деления x н аy выполняется равенство НОД(x, y) = НОД(y, r).

Например, пусть x = 48, а y = 18, найдем их наибольший общий делитель.

Таким образом, НОД(48, 18) = 6.

Пример

Написать программу нахождения наибольшего общего делителя (НОД) двух неотрицательных чисел.

Решение

Для решения данной задачи воспользуемся циклом с постусловием:

Program Example_11;
Var x, y: Integer;
Begin
Writeln('Введите два числа');
Readln(x,y); {вводим два целых числа}
If x>y Then x:=x Mod y
Else y:=y Mod x;
Until (x=0) Or (y=0);
{до тех пор, пока одно из чисел не станет равно нулю}
Writeln('НОД=', x+y)); {вывод НОД - без условного оператора, так как одно из чисел обязательно равно нулю}
Readln;
End.

Пример

Даны натуральные числа x и y, неравные нулю одновременно. Найти d = НОД(x, y) и такие целые q и w, что d=q*x + w*y.

Решение

Добавим в алгоритм Евклида переменные p, q, r, s, m и n такие, что m = p*a + q*b, n = r*a + s*b, где первоначально m = a = x, n = b = y.

Рассмотрим решение задачи для чисел 48 и 18.

Итак, d = НОД(48, 18) = 6 и 6 = 48*(-1) + 18*3.

Значения переменных p, q, r, s изменяются следующим образом:

	как только значение переменной m уменьшается на k*n, значение p уменьшается на k*r, а q уменьшается на k*s;
	аналогично, как только значение n уменьшается на k*m, значения переменных r и s уменьшаются соответственно на k*p и на k*q.

Учитывая всё, что сказано выше, составим программу:

Program Example_12;
Var x,y: Integer; {исходные данные}
p,q,r,s,m,n: Integer; {введённые вспомогательные переменные}
k: Integer; {для изменения значений p,q,r,s}
d: Integer; {значение наибольшего общего делителя}
Begin
Read(x,y);
m:=x; n:=y; p:=1; q:=0; r:=0; s:=1;
Repeat
If m>n Then Begin
k:=m Div n; m:=m Mod n;
p:=p-k*r; q:=q-k*s
End
Else Begin
k:=n Div m; n:=n Mod m; r:=r-k*p; s:=s-k*q End;
Until (m=0) Or (n=0);
If m=0 Then Begin
d:=n; q:=r; w:=s; End
Else Begin d:=m; q:=p; w:=q; End
Writeln(d,'=',q,'*',x,'+',w,'*',y);
End.

Решение задач

1. Найти НОД трех чисел.

Примечание. НОД(a, b, c)= НОД(НОД(a, b), c)

1. Проверить, являются ли два данных числа взаимно простыми. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.
2. Найти наименьшее общее кратное (НОК) чисел n и m, если

НОК(n, m) = n * m / НОД (n, m).

1. Даны натуральные взаимно простые числа n, p. Найдите m такое, что, во-первых, m<p, во-вторых, произведение чисел m и n при делении на p даёт остаток 1.

Примечание. Воспользуйтесь алгоритмом, описанным в примере 2.

1. От прямоугольника 324x141 отрезают квадраты со сторонами 141, пока это возможно. Затем вновь отрезают квадраты со стороной, равной 324 - 2*141 = 42 и т.д. На какие квадраты и на сколько квадратов будет разрезан треугольник?
2. Написать вариант алгоритма Евклида, основанный на соотношениях:

НОД(2a, 2b) = 2НОД(a, b);

НОД(2a, b) = НОД(a, b), при нечётном b,

не включающий деления с остатком, использующий лишь деление на 2 и проверку чётности.

1. Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что

p / q = m / n.