Алгоритм Евклида
Повторение
- Какие циклы с условиями вы знаете?
- В чем сходство и в чем отличие этих циклов?
Алгоритм Евклида - это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.
Алгоритм Евклида нахождения НОД основан на следующих свойствах этой величины. Пусть 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, найдем их наибольший общий делитель.
| X | Y | Результаты | |
| 48 | 18 | ||
| 48 mod 8 = 12 | 18 | x>y | НОД(48, 18) = НОД(12, 18) |
| 12 | 18 mod 12 = 6 | x<y | НОД(48, 18) = НОД(12, 6) |
| 12 mod 6 = 0 | 6 | x>y | НОД(12, 6) = НОД(0, 6) |
| 0 | 6 | x=0 | НОД(0, 6) = 6 |
Таким образом, НОД(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.
| M | N | P | Q | R | S | Результаты | |
| 48 | 18 | 1 | 0 | 0 | 1 | 48 = 48*1 + 18*0, 18 = 48*0 + 18*1 | |
| 48 mod 8 = 12 | 18 | 1 | -2 | 0 | 0 | m>n | 12 = 48*1 + 18*(-2) |
| 12 | 18 mod 12 = 6 | 1 | -2 | -1 | 3 | m<n | 6 = 18*1 + 12*(-1) =, 48*(-1) + 18*3 |
| 12 mod 6 = 0 | 6 | 3 | -8 | -1 | 3 | m>n | 0 = 12*1 + 6*(-2)=, 48*3 + 18*(-8) |
| 0 | 6 | m = 0 | d = n e = r w = s |
Итак, 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.
Решение задач
- Найти НОД трех чисел.
Примечание. НОД(a, b, c)= НОД(НОД(a, b), c)
- Проверить, являются ли два данных числа взаимно простыми. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.
- Найти наименьшее общее кратное (НОК)
чисел n и m, если
НОК(n, m) = n * m / НОД (n, m).
- Даны натуральные взаимно простые числа n,
p. Найдите m такое, что, во-первых, m<p,
во-вторых, произведение чисел m и n
при делении на p даёт остаток 1.
Примечание. Воспользуйтесь алгоритмом, описанным в примере 2.
- От прямоугольника 324x141 отрезают квадраты со сторонами 141, пока это возможно. Затем вновь отрезают квадраты со стороной, равной 324 - 2*141 = 42 и т.д. На какие квадраты и на сколько квадратов будет разрезан треугольник?
- Написать вариант алгоритма Евклида,
основанный на соотношениях:
НОД(2a, 2b) = 2НОД(a, b);
НОД(2a, b) = НОД(a, b), при нечётном b,
не включающий деления с остатком, использующий лишь деление на 2 и проверку чётности.
- Даны натуральные числа m и n.
Найти такие натуральные p и q, не
имеющие общих делителей, что
p / q = m / n.
