§ Разложение числа

Этот волшебный алгоритм я узнал еще давно, наверное, где-то в 3-4 классе начальной школы, и был потрясен до глубины души его простотой. Он описывался вот таким образом:
int NOD(int a, int b) {
    return b == 0 ? a : NOD(b, a % b);
}
Сказать то, что я был в шоке — мало. Я был в ступоре! Я не мог понять, каким именно таким образом с помощью всего лишь, можно сказать, одной строки высчитывается наибольший общий делитель! Как так? Я думал, что нужно перебирать все числа подряд, чтобы найти, а тут такой простой алгоритм это делает без проблем. Это была настоящая магия, понять которую можно только лишь магам, или богам.
И совершенно недавно, в возрасте 31 года, я понял. Я понял только лишь в этом возрасте. И попытаюсь объяснить, как именно это работает.
Итак, начнем с самого-самого простого, с разложения числа. Нам нужно найти НОД от a, b, это пишется так НОД(a, b) = d, где a и b - это числа, которые мы ищем, а "d" - это и есть наибольший общий делитель. Давайте сделаем так. Мы число "a" представим в виде вот такой формулы:
a = bq + r
Почему именно такой? Ответ простой – просто так нужно, если мы не сделаем такое представление, то ничего не докажем и не выведем. И это будет работать, спросите вы? Конечно! Абсолютно любое целое число "a" можно разложить в эту формулу.
Пример: возьмем числа a = 10, b = 3, просто для проверки. Чтобы найти q и r, требуется сделать очень простые вещи:
q = [\frac{a}{b}]
r = a - bq = a - b[\frac{a}{b}]
Все, что находится вот в таких скобках [ ] в математике означает, что мы берем ЦЕЛОЕ число от результата, например [12.421] = 12 . Итак: разделить нацело мы можем всегда, и результат этого деления будет в "q" (quotient), а остаток окажется в "r" (remainder). Значит, что формула выше абсолютно справедлива и возможна.
Что дальше? А дальше важно доказать вот что. Возьмем то же самое отношение, просто поменяем вместо "q" и "r" на g, s. Не знаю, зачем. Наверное, для смеха ради.
a = bg + s
Самое смешное вот в чем. Оказывается НОД от чисел a, b будет в точности равен НОД от b, s! Это как? Да вот я сам в начале не понял, как это так, пока не разобрал далее... Давайте докажем, что НОД(a, b) = НОД(b, s). Как видно, число g тут просто так, чтобы было и ни на что не влияет сейчас.
Итак. Допустим, у нас нашелся НОД(a, b) и он равен d1. Это означает то, что есть такие целые числа u, v, умножая на которые, мы получим значения a и b:
a = d_1u
b = d_1v
И причем тут u, v? Давайте сразу к примеру. Вот есть у нас a=18, b=12, какой у них наибольший делитель? НОД(18,12) = 6, т.е. d1 = 6. Проверим:
\frac{a}{d1} = \frac{18}{6} = 3, u = 3
\frac{b}{d1} = \frac{12}{6} = 2, v = 2
Вот тут u = 3, v = 2, то есть если умножить u на d1, то мы получим "a", и если v на d1 - то "b". Это означает, что если есть НОД(a, b), то u, v будут точно целыми числами.
Поехали дальше. Давайте теперь поставим вот сюда "a = bg + s" наши предполагаемые a, b, выраженные через u, v:
d_1u = d_1vg + s
s = d_1u - d_1vg
s = d_1(u - vg)
Что видим? Видим, что справа у нас (u - vg), которое является целым числом. И что слева у нас "s", которое тоже целое число, мы это вначале доказали. Ну и d1 тоже целое. Какой вывод? Вывод такой, что "s" делится на d1 без остатка.

§ Важный вывод

И "a", и "b" и "s" у нас делятся без остатка на тот же самый НОД(a, b). Это получается, что у них один и тот же делитель, что у "a, b" что у "b, s", что и у "a, s", так что НОД(a, b) = НОД(a,s) = НОД(b,s), все делятся на одно и тоже число d1.
Вот теперь происходит самый большой в мире фокус. Вот мы видим такую формулу:
a = bq + r
Тут мы видим, что НОД(a, b) на самом деле (смотри выше доказательство) равен НОД(b, r). Теперь давайте попробуем что-нибудь поискать, например НОД(18,12). Тут у нас a=18, b=12. Раскладываем:
18 = 12q + r
q = [\frac{18}{12}] = 1
r = 18 - 12*1 = 6
Вот мы нашли q=1, и r = 6. Но нам q не нужен. Мы доподлинно знаем, что НОД(b, r) = НОД(a, b), и что это значит? Это значит, что нам пора искать НОД(12, 6) - потому что r = 6. Ну что же, поищем:
12 = 6*q + r
q = [\frac{12}{6}] = 2
r = 12 - 6*2 = 0
Отлично! У нас остаток r = 0, то есть, мы все-таки да поделили так, что нашли что-то без остатка. И поделили в последний раз мы на число 6. Значит, что NOD(18,12) = NOD(12,6) = 6 , поскольку остатка при делении нет, а значит, НОД был найден.
Вся магия поиска НОД заключается в том, что NOD(a, b) = NOD(b, s) , и что можно разложить число "a" через число "b" по формуле a = bq + r. В итоге у нас получается, что при поиске НОД мы делаем вот такие вот запросы: d = NOD(a, b) = NOD(b, a \ mod \ b) где a mod b - это поиск остатка (числа r). Все доказано!
4 апр, 2018
© 2007-2022 Все дрова отлично колючие