Позиционная запись числа и её преобразования

Запись числа показывает, сколько единиц каждого разряда в нём содержится. Поэтому изменение цифр можно описать двумя способами: собрать новую строку символов или вычислить её значение арифметически. Связь между этими способами помогает проверять алгоритм и объяснять, почему выбранного диапазона поиска достаточно.

Исходное число обозначается N, результат преобразования — R.

Основание и значение разряда

В позиционной системе счисления каждый следующий разряд слева имеет вес в несколько раз больше предыдущего. Этот множитель называется основанием. Для двоичной системы он равен 2, для троичной — 3.

Чтобы получить значение записи, каждая цифра умножается на вес своей позиции. Полученные числа складываются:

11001_2=16+8+1=25_{10}.

Единицы стоят в разрядах с весами 16, 8 и 1. Разряды с весами 4 и 2 содержат нули и ничего не добавляют к сумме.

102_3=1\cdot9+0\cdot3+2\cdot1=11_{10}.

Нижние индексы обозначают основание записи. Индекс 3 не означает умножение на 3: запись 102_3 содержит девятки, тройки и единицы.

Как получается запись в другом основании

Последняя цифра — остаток от деления числа на основание. Целая часть от деления содержит оставшиеся цифры. Для числа 11 в троичной системе:

Остатки получены от младшего разряда к старшему, поэтому читаются снизу вверх: 102_3. Ноль в середине занимает свою позицию и не пропускается.

Для двоичной записи Python предоставляет bin(n)[2:]. Для троичной записи тот же процесс деления можно записать так:

def ternary(n):
    if n == 0:
        return '0'
    s = ''
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s

Функция рассчитана на неотрицательные целые числа. n % 3 даёт остаток, n // 3 — целое частное. Новая цифра добавляется слева, поэтому переворачивать результат отдельно не нужно. Проверка: ternary(11) возвращает '102', а int('102', 3) возвращает 11.

Дописывание справа

Если справа появился один новый разряд, все прежние цифры сдвинулись на одну позицию. Их веса умножились на основание. Два новых разряда умножают старую часть на квадрат основания.

Например, добавление 01 к двоичной записи 101_2 даёт:

101\underbrace{01}_{\text{два разряда}}{}_2=5\cdot2^2+1=21.

Добавленное число равно 1, но добавленных разрядов два. Ноль перед единицей определяет сдвиг исходной записи.

В общем виде пусть b — основание, k — число добавляемых цифр, а D — значение добавляемого фрагмента. Тогда:

R=N\cdot b^k+D.

Для добавления троичного фрагмента 101_3 к 102_3 длина фрагмента равна 3, а его значение равно 10. Поэтому R=11\cdot3^3+10=307. Именно такое преобразование присутствует в задании EGE-05-0004 ↗.

Справа может добавляться запись переменной длины. Например, если исходное число не делится на 3, остаток после умножения на 3 даёт либо 3_{10}=11_2, либо 6_{10}=110_2. В первом случае сдвиг составляет два разряда, во втором — три.

Дописывание слева и замена цифр

Добавление слева зависит от того, сколько цифр уже находится справа. Например, перед записью 101_2 добавляется единица. Справа от неё три разряда, поэтому новая единица имеет вес 2^3=8:

\underbrace{1}_{8}101_2=8+5=13.

Если исходная запись имеет длину m, а значение добавляемого слева фрагмента равно P, то R=P\cdot b^m+N. При последовательных добавлениях длина записи меняется: сначала учитывается первый шаг, затем следующий.

Замена имеет другой смысл: старые цифры удаляются, а новые занимают их места. Если у строки '1100' первые две цифры заменяются на '10', остаётся хвост '00' и получается '1000'. В Python это '10' + s[2:]. Запись '10' + s дала бы '101100' — добавление двух новых разрядов.

Чётность числа и чётность суммы цифр

В двоичной системе все веса, кроме последнего, делятся на 2. Поэтому чётность числа определяется последней цифрой: 0 — чётное, 1 — нечётное. В Python это проверка n % 2.

Чётность суммы цифр определяется количеством единиц во всей двоичной записи. Например, 6_{10}=110_2 и 4_{10}=100_2 — два чётных числа. Но суммы их двоичных цифр равны 2 и 1, то есть имеют разную чётность. Для строки используется s.count('1') % 2.

Добавление бита, равного этой чётности, делает общее число единиц чётным:

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

Когда перебор достаточно полный

Найденный подходящий вход ещё не доказывает, что результат минимален или максимален. Важны порядок проверки и ограничение остальных вариантов.

• Для минимального N можно проверять входы по возрастанию и остановиться на первом подходящем.
• Для минимального R сравниваются результаты: рост входа сам по себе не гарантирует рост выхода.
• Если правило только дописывает цифры справа к положительному числу, то R>N. Найденный допустимый результат R_0 ограничивает поиск минимума: входы N\geq R_0 не дадут меньший результат.
• Для максимума при ограничении R\leq T то же доказанное свойство R>N даёт конечный диапазон N<T. В нём сравниваются допустимые входы или результаты — в зависимости от вопроса.

Последнее рассуждение использует конкретное свойство алгоритма. После удаления или замены разрядов неравенство R>N нельзя переносить автоматически: оно требует отдельного доказательства. Произвольный предел вроде 1000 не объясняет, почему все нужные варианты попали в перебор.

Применение в заданиях

Как два последовательных бита чётности помогают найти наименьший вход? Почему при поиске наименьшего результата иногда приходится продолжать перебор после первого удачного значения?

Эти вопросы разобраны на примерах в статье «Задание №5. Преобразование записи числа».