суббота, 3 апреля 2010 г.

НОД (Наибольший общий делитель)

Английский эквивалент этого понятия GCD(Greatest Common Divisor). Краткую теорию по этому вопросу читаем на Wikipedia. Сразу отметим, что наиболее эффективный и распространенный алгоритм нахождения НОДа является алгоритм Евклида, о котором очень популярно изложено сайте MAXimal. Обратите внимание на доказательство корректности алгоритма.
После ознакомления с этой статьей предлагаю перейти к практической части.
По мотивам введения первой главы книги Левитина
“Алгоритмы. Введение в разработку и анализ” рассмотрим несколько реализаций нахождения НОДа.
1. Рекурсивная реализация алгоритма Евклида:

  1. int gcd_Euclid(int a, int b)
  2. {
  3.   if (b == 0)
  4.     return a;
  5.   return gcd_Euclid(b,a%b);
  6. }