Алгоритъм на Евклид
от Уикипедия, свободната енциклопедия
Алгоритъмът на Евклид е алгоритъм за намиране на най-големия общ делител (НОД) на две естествени числа. Той е един от първите публикувани алгоритми. Описан е в книгата на Евклид „Елементи“ около 300 г. пр.н.е.
| Съдържание | 
[редактиране] Алгоритъм на Евклид (теория)
Нека a и b са естествени числа и редицата
е определена така, че всяко rk е остатък от делението на пред-предния член на предния член, т. е.
- a = bq0 + r1
- b = r1q1 + r2
- r1 = r2q2 + r3
 
- rn - 1 = rnqn
Тогава (a,b), най-големият общ делител на a и b, е равен на rn, последния ненулев член на редицата.
Верността на алгоритъма следва от съжденията:
- Нека a = bq + r, тогава (a,b) = (b,r).
- (0,r) = r. за всяко ненулево r.
[редактиране] Алгоритъмът (запис с думи)
- Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0.
- Ако да, числото a е търсеният най-голям общ делител.
- Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)
 
[редактиране] Рекурсивен запис
function gcd(a, b)
  if b = 0
     return a
  else
     return gcd(b, a mod b);
[редактиране] Процедурен запис
function gcd(a, b)
  while b ≠ 0
    var t := b
    b := a mod b
    a := t
  return a
[редактиране] Без използване на деление
function gcd(a, b)
  while a ≠ b
    if a > b
      a := a - b
    else
      b := b - a
  return a
[редактиране] Пример
Най-големия общ делител на числата 1071 и 1029 се пресмята по следния начин:
Следователно, търсения делител е 21.





