Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Январь 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru
Олимпиадные задачи и алгоритмы на C++

Олимпиадные задачи и алгоритмы на C++

Наибольший общий делитель

Постановка задачи

Пусть даны два целых положительных числа a и b. Целое число c называется их общим делителем, если оба числа a и b делятся на c без остатка (a%c=0, b%c=0). Наибольший общий делитель - это максимальный из общих делителей двух чисел. Задача: научиться быстро искать наибольший общий делитель.

Замечание. По-английски наибольший общий делитель называется greatest common divisor, поэтому функцию его поиска обычно называют gcd.

Решение

Самый простой известный мне алгоритм выглядит так: 


int gcd(int a, int b)
{
  int c = min(a, b);
  while (a % c + b % c) --c;
  return c;
}

Сложность работы данного алгоритма O(n). Такая сложность приемлема, если числа a и b небольшие. Но что делать, если, например, a и b больше миллиарда. Для таких a и b нужен алгоритм O(log n).

И такой алгоритм существует. Он называется алгоритмом Евклида и основывается на следующем свойстве: gcd(a, b) = gcd(a mod b, b). Суть алгоритма в следующем: пока меньшее из двух чисел не равно нулю, мы заменяем большее из чисел на остаток от его деления на меньшее из чисел. Это реализовано в следующей рекурсивной функции: 


int gcd(int a, int b)
{
  if (b == 0) return a;
  else return gcd(b, a mod b);
}

Рекурсия здесь нужна только для наглядности. Нетрудно реализовать поиск gcd итеративно. Я не буду приводить здесь доказательство того, что сложность алгоритма O(log n). Вы можете посмотреть его в специальной литературе.

Существует так называемый расширенный алгоритм Евклида, который помимо c = gcd(a, b) позволяет найти пару чисел x и y, таких что a * x + b * y = c. Такая задача часто возникает в теории чисел, например, при поиска обратного элемента по модулю. Ниже приведена реализация расширенного алгоритма Евклида, рекурсивная для наглядности. 


int gcd(int a, int b, int& x, int &y)
{
  if (b == 0) { x = 1; y = 0; return a; }
  int c, x1, y1;
  c = gcd(b, a mod b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return c;
}

С уважением, Виктор Журавлев, accepted@narod.ru.

http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: comp.soft.prog.accepted		 Отписаться
В избранное