суббота, 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. }

Есть аналогичная реализация этой функции, только вместо операции “остаток от деления” используется операция “вычитание”. Она представляет для нас чисто академический интерес, поэтому не будем ее разбирать отдельно. Достаточно понимать, что приведенная реализация работает быстрее.
2. Нерекурсивная реализация алгоритма Евклида:

  1. int gcd_Euclid2(int a, int b)
  2. {
  3.   while (b!=0)
  4.   {
  5.     int tmp = a%b;
  6.     a = b;
  7.     b = tmp;
  8.   }
  9.   return a;
  10. }

Любую рекурсивную функцию можно заменить на цикл while. Вопрос только каких усилий стоит поддерживать стек переменных. В данном случае это сделать несложно.
3. Первый алгоритм, который приходит в голову:

  1. int gcd_Naive(int a,int b)
  2. {
  3.   int gcd = min(a,b);
  4.   while (gcd != 1)
  5.   {
  6.     if (a%gcd == 0 & b%gcd == 0)
  7.       return gcd;
  8.     gcd--;
  9.   }
  10.   return gcd;
  11. }

Как можно заметить данная реализация менее эффективна, по сравнению с предыдущими. Особенно это остро будет ощущаться если a = 1e9, b = 1.
4. Школьный метод разложения на простые множители:
Идея метода заключается в следующем. Раскладываем на простые множители числа а и b. Затем находим общие множители в обоих разложениях. Их произведение даст нужный ответ.

  1. void findDivisors(int n,vector<int> &devs, vector<int> primes)
  2. {
  3.   // в массиве devs на i-ой позиции будет находится степень простого числа primes[i],
  4.   // которое встречается в разложении числа n
  5.   devs.resize(primes.size());
  6.   for (int i = 0;i<primes.size();i++)
  7.     while (n%primes[i]==0)
  8.     {
  9.       n/=primes[i];
  10.       devs[i]++;
  11.     }
  12. }
  13. int gcd_schoolMethod(int a, int b)
  14. {
  15.   // решето Эратосфена для чисел [2,1e4]
  16.   const int size = 1e4;
  17.   bitset<size> met;
  18.   int len = sqrt((double)size);
  19.   for (int i=2;i<=len;i++)
  20.     for (int j=i*i;j<size;j+=i)
  21.       met[j] = true;
  22.   // копирование простых чисел в отдельный массив primes
  23.   vector<int> primes;
  24.   for (int i=2;i<size;i++)
  25.     if (!met[i])
  26.       primes.push_back(i);
  27.  
  28.   // поиск степеней простых чисел, встречающихся в разложении чисел a и b
  29.   vector<int> divsA, divsB;
  30.   findDivisors(a,divsA,primes);
  31.   findDivisors(b,divsB,primes);
  32.   int gcd = 1;
  33.   for (int i=0;i<divsA.size();i++)
  34.     gcd *= pow(primes[i],min(divsA[i],divsB[i]));
  35.  
  36.   return gcd;
  37. }

В данной реализации условимся, что числа a и b находятся в интервале [1,10000].
1) Сначала находим все простые числа в интервале от [2,10000]
2) Затем формируем массив primes, который содержит только эти простые числа
3) Раскладываем числа a и b на простые множители. При этом получаем массивы divsA и divsB, в которых на i-ой позиции находится степень простого множителя, содержащегося в разложении. 
Разберем пример с числом 126.
126 = 2^1 * 3^2 * 5^0 * 7^1, где ^ – возведение в степень.
primes = {2,3,5,7,…}
divs   = {1,2,0,1,…}
4) Нахождение ответа осуществляется в цикле(33-34).

Очень удачно подмечено в сборнике лекций Михаила Густокашина, что имея разложение чисел в виде массивов степеней простых множителей, можно без труда сделать операцию сложения и вычитания первоначальных чисел.

7 комментариев:

  1. Анонимный6 июня 2010 г., 6:50

    Как можно заметить данная реализация менее эффективна, по сравнению с предыдущими. Особенно это остро будет ощущаться если a = 1e9, b = 1.

    В приведенном выше решении для GCD за 1 шаг будет ответ :-).. пункт 3

    ОтветитьУдалить
  2. Удачное замечание. Стоит заменить b=1, на b=2)

    ОтветитьУдалить
  3. Как вариант быстрая форма записи с оператором ?:
    Исповедаю..
    int gcd_Euclid(int a, int b)
    {
    return b?gcd_Euclid(b,a%b):a;
    }

    Дело вкуса конечно.

    ОтветитьУдалить
  4. Анонимный16 июня 2013 г., 3:49

    I couldn't resist commenting. Perfectly written!

    My web page ... shooting games unblocked

    ОтветитьУдалить
  5. Анонимный17 июня 2013 г., 4:43

    Τhanks for yοur marvelous pоsting!

    Ι truly enjoyеd геadіng it, yοu cаn be a great author.
    I will be sure to bookmark yοur blog and maу come baсk sometіme sοon.
    I want to enсourage you to definitely continuе уour great ωогk, have a niсe ωеekend!



    Feel free to suгf to my weblog: 3d tattoos picturеs - -

    ОтветитьУдалить
  6. Анонимный17 июня 2013 г., 7:29

    Рlaying With Fire 2: This is a fun game that you саn play againѕt a friend οг the computer.
    Not considerably mess can bе brought on by sіttіng аt the computer.

    There arе computеr games that arе spеcifіcally baѕeԁ around educatіοnal learning standards.

    Various adventurе gameѕ are ԁesigned foг this purpose fοг letting
    them have moгe fun while alѕo stimulating theiг іmаgination.
    Any sеttіng yоu can think of has been creatеԁ for
    the system.

    Ѕtop by my sitе: Mundebaba

    ОтветитьУдалить