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

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




Скачати 63.73 Kb.
НазваНаибольший общий делитель
Дата конвертації01.02.2013
Розмір63.73 Kb.
ТипДокументи

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ


Каждый из нас в школе изучал, что такое наибольший общий делитель (далее НОД) двух чисел a и b. Конечно же, это наибольшее целое число d, на которое a и b делятся без остатка. Без труда каждый ученик может сказать, например, что НОД(12, 18) = 6. Но что если одно из чисел равно 0? А если a или b отрицательно? Над этим вопросом на школьных уроках, наверное, не каждый из нас задумывался. Для того чтобы ответить на поставленные вопросы, приведем определение – что же такое наибольший общий делитель.


Определение 1. Наибольшим общим делителем (далее НОД) двух целых чисел a и b, одновременно не равных нулю, называется такое наибольшее целое число d, на которое a и b делятся без остатка. Этот факт обозначается так: d = НОД(a, b). Если оба числа равны нулю, то положим НОД(0, 0) = 0.

Исходя из определения, имеют место следующие равенства:

НОД(a, b) = НОД(b, a),

НОД(a, b) = НОД(-a, b)

НОД(a, 0) = |a|


Почему, скажете вы, НОД(-12, 18) равен 6, а не -6? Ведь и -12, и 18 делятся нацело на 6 и на -6. Ответ прост: ведь НОД – это же наибольший общий делитель, а число 6 больше -6.


С понятием наибольшего общего делителя тесно связано понятие наименьшего общего кратного.


Определение 2. Наименьшим общим кратным (далее НОК) двух целых чисел a и b называется наименьшее положительное целое число, кратное как a, так и b.


Основная теорема арифметики утверждает, что любое натуральное число n можно представить в виде произведения простых чисел:

n =

Такое разложение натурального числа называется каноническим. Из него следует, что если a = , b = , то

НОД(a, b) = ,

НОК(a, b) =


Пример 1. Рассмотрим числа a = 24 и b = 18. Разложим их на простые множители: 24 = 23 * 3, 18 = 2 * 32. Следовательно

НОД(24, 18) = 2min(3,1) * 3min(1,2) = 21 * 31 = 6,

НОК(24, 18) = 2max(3,1) * 3max(1,2) = 23 * 32 = 8 * 9 = 72


Именно такой метод, с использованием канонического разложения чисел, мы изучали в школе для нахождения НОД и НОК. Однако этот метод не эффективен для реализации алгоритмов их вычисления.


Рассмотрим следующий очевидный факт. Если НОД(a, b) = d, то a и b делятся на d. Следовательно, их разница ab также делится на d. Имеет место следующее рекуррентное соотношение для вычисления НОД:

НОД(a, b) =


Пример 2. Пусть a = 32, b = 12. Тогда

НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =

НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4


Приведенный метод вычисления не является оптимальным. Например, для нахождения НОД(1000000, 2) следует выполнить 500000 операций вычитания. Для ускорения вычисления НОД операцию вычитания заменим операцией взятия остатка от деления:

НОД(a, b) =


Пример 3. Пусть a = 78, b = 14. Тогда

НОД(78, 14) = НОД(78 mod 14, 14) = НОД(8, 14) = НОД(8, 14 mod 8) = НОД(8, 6) =

НОД(8 mod 6, 6) = НОД(2, 6) = НОД(2, 6 mod 2) = НОД(2, 0) = 2


Упростим приведенную выше рекуррентность, сократив количество условий до двух:

НОД(a, b) =

Если a < b, то НОД(a, b) = НОД(b, a mod b) = НОД(b, a), то есть аргументы функции переставляются. При последующих вызовах функции НОД первый аргумент всегда больше второго. Нулем может стать только второй аргумент b.


Пример 4. Пусть a = 14, b = 78. Тогда

НОД(14, 78) = НОД(78, 14) = НОД(14, 8) = НОД(8, 6) = НОД(6, 2) = НОД(2, 0) = 2


Реализуем на языке программирования Си функцию gcd (^ Greatest Common Divisor) вычисления НОД, используя последнюю рекуррентность. Знак % в Си обозначает операцию взятия остатка от деления.


int gcd(int a, int b)

{

if (b == 0) return a;

return gcd(b, a % b);

}


Напомним, что условный оператор в Си имеет следующий синтаксис:

if (<условное выражение >) <выражение 1>; else <выражение 2>;

Если <условное выражение> истинно, то выполняется <выражение 1>, иначе выполняется <выражение 2>.


Тернарный условный оператор имеет синтаксис:

<условное выражение > ? <выражение 1> : <выражение 2>;

и семантически немного отличается от оператора if..then..else. Если <условное выражение> истинно, то оператор возвращает значение, которое возвращает <выражение 1>, иначе возвращается значение выражения <выражение 2>.


Используя тернарный оператор, функцию gcd можно записать следующим образом:


int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}


Теорема. Между НОД и НОК двух чисел имеет место соотношение:

a * b = НОД(a, b) * НОК(a, b)


Функция lcm (Lowest Common Multiple) вычисления НОК имеет вид:


int lcm(int a, int b)

{

return a / gcd(a, b) * b;

}


Заметим, что при вычислении выражения a * b / gcd(a, b) может возникнуть переполнение, а при a / gcd(a, b) * b нет. Здесь подразумевается, что значения a, b и lcm(a, b) лежат в границах типа int.


Задача

При делении числа n на d получается частное q и остаток r. При этом q – максимально возможное целое, для которого qdn, а r = nqd. Для любого множества целых чисел {a1, …, ak} всегда существует такое целое d, что числа ai mod d равны.

Вход. Каждая строка является отдельным тестом и содержит последовательность целых чисел a1, …, ak, заканчивающуюся нулем. Последний ноль не принадлежит самой последовательности. Последовательность содержит не менее 3 и не более 1000 чисел. Не все числа в последовательности равны между собой. Признаком конца входных данных является строка с одним нулем.

Выход. Для каждой входной последовательности a1, …, ak вывести максимальное d, для которого при делении ai на d будут получаться равные остатки.

Пример входа

Пример выхода

701 1059 1417 2312 0

179

14 23 17 32 122 0

3

14 -22 17 -31 -124 0

3

0





Решение. Из условия задачи следует, что

a1 = d * r1 + rest

a2 = d * r2 + rest



ak = d * rk + rest

Поскольку d максимально , то НОД(r1, r2, …, rn) = 1. Далее имеем:

a2a1 = d * (r2r1)

a3a2 = d * (r3r2)



akak-1 = d * (rkrk-1)

Откуда d – наибольшее целое, которое делит a2a1, a3a2, …, akak-1. То есть

d = НОД(|a2a1|, |a3a2|, …, |akak-1|).

Реализация. Основной цикл программы состоит в чтении последовательности чисел {a1, …, ak} и последовательном вычислении значения НОД(|a2a1|, |a3a2|, …, |akak-1|).


#include

#include


int a, b, res;


int gcd(int a, int b) { ... } // код функции gcd приведен выше


void main(void)

{

while (scanf("%d %d", &a, &b), a)

{

res = abs(a - b); a = b;

while(scanf("%d", &b), b)

{

res = gcd(res, abs(a - b));

a = b;

}

printf("%d\n", res);

}

}



Схожі:

Наибольший общий делитель iconРасширенный алгоритм евклида
Ля (нод) был открыт древнегреческими математиками и известен как алгоритм “взаимного вычитания”. И хотя упоминание об этом алгоритме...
Наибольший общий делитель iconНачало Предложение
Предложение по входу что стерпит многое +/-300 в и Скорректирован имеющийся делитель на выходе ад8065 для совпадения со стандартной...
Наибольший общий делитель iconПамятка как задавать вопросы? В английском языке существует 4 типа вопросов: Общий (yes/no), требующий ответа «да» или «нет», начинается с вспомогательного глагола
Общий (yes/no), требующий ответа «да» или «нет», начинается с вспомогательного глагола
Наибольший общий делитель iconС1-92 делитель входной на 1: 10 и 1: 100 на керамическом носителе как у Тека
Емкость, почти на порядок больше чем обычно принято даже в бывшем отечестве нашем. Заграничные значения еще меньше 2 0 раза
Наибольший общий делитель iconОбщий вид: породная; голова: породная; зубн система
«общий вид: породная; голова: породная; зубн система: N; корпус: физически развита,, хор. Линия верха; пер кон.: Отличн.; задн кон.:...
Наибольший общий делитель iconОтдых в горах карпат ы укра и на
Яремче. Они находятся в п. Яблуница, п. Ворохта и наибольший в данном регионе горнолыжный центр т/к «Буковель» в п. Паляница, где...
Наибольший общий делитель iconОтдых в горах карпат ы укра и на
Яремче. Они находятся в п. Яблуница, п. Ворохта и наибольший в данном регионе горнолыжный центр т/к «Буковель» в п. Паляница, где...
Наибольший общий делитель iconОтдых в горах карпат ы укра и на
Яремче. Они находятся в п. Яблуница, п. Ворохта и наибольший в данном регионе горнолыжный центр т/к «Буковель» в п. Паляница, где...
Наибольший общий делитель iconПрикус: N; Зубы: N. Общий вид: Породная. Правильные линии и пропорции
Прикус: N; Зубы: N. Общий вид: Породная. Правильные линии и пропорции. Голова: Правильные линии и пропорции. Правильный выход шеи....
Наибольший общий делитель iconОбщий список продуктов для 1 человека на 20 дней

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи