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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Алгоритъмът на Евклид е алгоритъм за намиране на най-големия общ делител (НОД) на две естествени числа. Той е един от първите публикувани алгоритми. Описан е в книгата на ЕвклидЕлементи“ около 300 г. пр.н.е.

Теория[редактиране | edit source]

Нека a и b са естествени числа и редицата

 a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n

е определена така, че всяко r_k е остатък от делението на пред-предния член на предния член, т. е.

a = bq_0 + r_1
b = r_1q_1 + r_2
r_1 = r_2q_2 + r_3
\cdots
r_{n-1} = r_nq_n

Тогава (a,b) - най-големият общ делител на a и b, е равен на r_n - последния ненулев член на редицата.

Верността на алгоритъма следва от съжденията:

  • Нека a = bq + r, тогава (a,b)=(b,r).
  • (0,r)=r. за всяко ненулево r.

Запис с думи[редактиране | edit source]

Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0.
Ако да, числото a е търсеният най-голям общ делител.
Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)

Рекурсивен запис[редактиране | edit source]

function gcd(a, b)
  if b = 0
     return a
  else
     return gcd(b, a mod b);

Процедурен запис[редактиране | edit source]

function gcd(a, b)
  while b ≠ 0
    var t := b
    b := a mod b
    a := t
  return a

Без използване на деление[редактиране | edit source]

function gcd(a, b)
  while a ≠ b
    if a > b
      a := a - b
    else
      b := b - a
  return a

Пример[редактиране | edit source]

Най-големият общ делител на числата 1071 и 1029 се пресмята по следния начин:

1071 = 1 \cdot 1029 + 42
1029 = 24 \cdot 42 + 21
42 = 2 \cdot 21 + 0

Следователно търсеният делител е 21.

Виж още[редактиране | edit source]