Это статья для расширения кругозора и общей математической грамотности. Программисты, которые знают, как устроена математика, могут написать более крутой и изящный код, чем те, кто этого не знает. Мы хотим, чтобы вы писали крутой код и много зарабатывали.
Когда мы записываем любое число, например 1998, то пользуемся позиционной системой счисления. Позиционной — это когда значение каждого числа зависит от позиции в цифре. В десятичной, самой привычной нам системе, всё зависит от степени десятки: на какой позиции стоит цифра, в ту степень и возводим 10 и умножаем на это число. Отсчёт идёт с нуля, и работает всё это так:
В двоичной системе счисления всё точно так же, но в основании системы уже не 10, а 2:
Но есть системы счисления, которые устроены иначе. В них цифра означает всегда одно и то же независимо от того, где она стоит. Это — непозиционные системы счисления.
Римская система счисления — старая и декоративная
Самая известная сегодня непозиционная система счисления — римская. Она пришла к нам из древнего Рима, и в ней вместо цифр используются римские буквы:
I — 1
V — 5
X — 10
L — 50
C — 100
D — 500
M — 1000
Римскую систему счисления сейчас используют в декоративных целях: с её помощью обозначают цифры на часах, указывают в титрах год выпуска фильмов и главы книг:
В римской системе счисления все числа получаются с помощью хитрых комбинаций разных букв-цифр, и всё зависит от того, какие цифры стоят рядом друг с другом.
Общее правило сейчас такое:
- цифры могут повторяться, но не более трёх одинаковых подряд;
- если меньшая цифра стоит справа от такой же или большей, то они складываются друг с другом: VIII → 8;
- если меньшая цифра стоит слева от большей — вычитаем из большего меньшее: IV → 4.
Раньше, когда римская система только появилась, то вычитания не было — всё складывали, поэтому 4 записывалось не как IV, а как IIII. В античности всё поменялось, и система пришла к тому, как ей пользуются сейчас. Из-за этого добавились шесть новых комбинаций, которые при расчётах используются как единое целое:
IV = 4
IX = 9
XL = 40
XC = 90
CD = 400
CM = 900
Перевод десятичного числа в римское
Для примера покажем, как перевести число 1998 в римскую систему счисления. Для этого делаем так:
- Берём самое большое римское число и смотрим, наше число больше или нет.
- Если наше больше — вычитаем из нашего римское и записываем его.
- Если не больше — переходим к следующему римскому.
- Так делаем до тех пор, пока у нас в остатке не получится ноль.
Итак, делаем всё по шагам:
- 1998 и 1000 (M) — самое большое римское число. Наше больше, поэтому отнимаем и добавляем новую букву: M. Остаток — 998
- Снова проверяем с самым большим числом — 1000 (M). Наше число меньше, поэтому берём следующее: CM (900). Это уже подходит, поэтому вычитаем его из 998: 998 − 900 = 98. Запоминаем остаток и добавляем CM к нашему числу: MCM
- Берём остаток — 98 — и проверяем снова все римские числа сверху вниз. Первое римское число, которое меньше нашего, — это XC (90). Отнимаем, получаем остаток 8 и добавляем XC к нашему числу: MCMXC
- Берём остаток — 8 — и смотрим, какое минимальное римское число меньше него, это V (5). Отнимаем пятёрку, получаем 3 и добавляем V к римскому числу: VCVXCV.
- Из числа 3 последовательно отнимаем три единицы I (1), и дописываем их к римскому числу: MCMXCVIII.
- У нас в остатке 0, а значит, мы закончили с переводом. 1998 = MCMXCVIII.
Зачем сейчас это знать
Непозиционные системы счисления — это не только про красивые записи чисел ради эстетики, но и про алгоритмы их вычисления. А если есть алгоритм, можно написать к нему код и использовать в разных проектах.
Сейчас в математике используются две непозиционные системы счисления — биномиальная система счисления и система остаточных классов. В обеих из них всё зависит от алгоритмов расчёта, и если понимать их отличие от позиционных систем, то работать с ними становится гораздо проще.
Биномиальная система счисления — это когда число представляется в виде суммы биноминальных коэффициентов. Слово «биномиальный» означает, что система основана на биноме Ньютона — способе разложения одних чисел на другие.
Эта система счисления используется в комбинаторике — с её помощью можно быстро вычислить нужную комбинацию без перебора всех вариантов, которые идут перед ней. А ещё по этому же принципу производят тестирование ПО, контроль качества и анализ проведённой лотереи — находят такие комбинации и сочетания факторов, которые вероятнее всего могли привести к каким-то важным результатам.
Система остаточных классов основана на модулярной арифметике, когда числа сравниваются по модулю (дают ли при делении один и тот же остаток). Там всё состоит из базисов, модулей и похоже на работу с матрицами. Благодаря тому свойству, что некоторые вычисления имеют только одно решение, система остаточных классов используется в информационной безопасности, контроле за ошибками и для обеспечения надёжности космической или военной техники.
Что дальше
В следующей статье мы разберём хитрую задачку из собеседования, связанную как раз с римской системой счисления. Такое любят спрашивать при устройстве в разные крупные компании, чтобы оценить кругозор будущего сотрудника.
