Преобразование записей чисел

Этот урок разбирает один подтип задания № 5: алгоритм получает натуральное число N, строит его запись в заданной системе счисления, изменяет цифры и получает число R. Другие формы задания № 5 могут использовать иных исполнителей — здесь мы не пытаемся охватить их все.

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

Одно количество можно записать по-разному: 13₁₀ = 1101₂ = 111₃. Нижний индекс сообщает основание системы.

1101₂ = 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 13, но 1101₃ = 1·3³ + 1·3² + 0·3¹ + 1·3⁰ = 37. Одинаковая строка в разных основаниях обозначает разные числа.

В системе с основанием bдопустимы цифры от нуля до b − 1. Маленькая b обозначает основание, а большая N — входное число.

Поэтому алфавиты таковы: в двоичной системе — 0, 1; в троичной — 0, 1, 2; в четверичной — 0, 1, 2, 3; в пятеричной — 0, 1, 2, 3, 4. Механика преобразования одна, но основание и допустимые цифры всегда нужно читать из условия.

Независимо от основания решение удобно вести по одной схеме. Она не заменяет чтение условия, но не даёт смешать число и строку.

n = 13s = bin(n)[2:]  # убираем только префикс 0b # Здесь алгоритм изменяет строку s. r = int(s, 2)

Для N = 13 вызов bin(13) возвращает строку '0b1101'. Срез [2:]удаляет только служебный префикс 0b, а не цифры числа. После преобразований int(s, 2)читает текущую строку именно как двоичную запись.

Приписывание — это склеивание строк: '1101' + '1' == '11011'. Справа пишут s += '1', слева — s = '1' + s. Порядок меняет результат.

s = '101101' last = s[-1]       # '1'last_two = s[-2:]  # '01'first_two = s[:2]  # '10' s += s[-2:]       # дописать две последние цифрыs = '112' + s[2:]  # заменить первые две цифрыs = s[1:]          # удалить первую цифруs = s[:-1]         # удалить последнюю цифру

Индексы начинаются с нуля. Поэтому после первых двух символов остаток начинается с s[2:], а отрицательные индексы считают позиции с конца.

Для строки '101101' выражения s[-1], s[-2], s[-2:] и s[-3:] дают соответственно '1', '0', '01' и '101'. С начала строки s[0], s[:2] и s[:3] дают '1', '10' и '101'.

Приписывание справа — и строковая операция, и разрядный сдвиг. В десятичной системе 375 = 37·10 + 5; в двоичной 11011₂ = 13·2 + 1 = 27; в троичной 1022₃ = 11·3 + 2 = 35.

Для одной цифры R = N·b + d. Для блока из k цифр: R = N·bᵏ + D, где D — значение блока в том же основании.

В одном из алгоритмов к двоичной строке дважды дописывают остаток от деления суммы её цифр на 2. Он показывает чётность количества единиц: нули сумму не меняют.

s = bin(n)[2:] s += str(sum(map(int, s)) % 2)s += str(sum(map(int, s)) % 2) r = int(s, 2)

Внутри выражения map(int, s) символы '1', '1', '0', '1' превращаются в числа 1, 1, 0, 1. Их сумма равна трём, а остаток3 mod 2 = 1. Поэтому это выражение показывает чётность количества единиц: нули сумму не меняют.

Чтобы найти минимальное N при R > 100, проверяйте кандидаты по возрастанию и останавливайтесь на первом успехе.

for n in range(1, 1000):    s = bin(n)[2:]    s += str(sum(map(int, s)) % 2)    s += str(sum(map(int, s)) % 2)    r = int(s, 2)     if r > 100:        print(n, r, s)        break

answers = [] for n in range(1, 351):    s = to_base(n, 3)     if n % 3 == 0:        s = '1' + s + '02'    else:        digit = str(n % 3)        s += digit * 2     r = int(s, 3)    if r <= 350:        answers.append(n) print(max(answers))

Программа выводит 38. Ручная проверка: 38₁₀ = 1102₃, затем ветвь «иначе» даёт 110222₃, а его десятичное значение равно 350.

Вывод — 25 102 1100110. Первое найденное N минимально не из-за обязательного роста R(N), а потому что сами кандидаты идут как 1, 2, 3, ….

Пусть к троичной записи числа, кратного трём, приписывают слева 1, а справа 02. Для остальных чисел справа дважды приписывают N mod 3. Условие относится к самому N, не к сумме цифр.

def to_base(n, base):    digits = ''     while n > 0:        digits = str(n % base) + digits        n //= base     return digits or '0'

При поиске максимального Nпервая неудача ничего не доказывает: разные ветви могут вернуть меньшее R для следующего числа. Проверьте весь обоснованный диапазон и примените max().

Если алгоритм только приписывает цифры, то R ≥ N. При условии R ≤ 500 достаточно проверить 1 ≤ N ≤ 500. При удалении или замене цифр это обоснование может не работать.

Конкретно здесь соседние результаты равны R(11) = 107, R(12) = 353 и R(13) = 121. После первой неудачи результат снова становится допустимым. Если алгоритм удаляет цифры, заменяет большие цифры меньшими или отбрасывает часть записи, возможно R < N; тогда границу нужно выводить из других свойств условия.

answers = [] for n in range(1, 501):    s = to_base(n, 3)     if n % 3 == 0:        s = '1' + s + '02'    else:        s += str(n % 3) * 2     r = int(s, 3)    if r <= 500:        answers.append(n) print(max(answers))

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

# Неверно: второй replace затронет и новые двойки.s = s.replace('0', '2').replace('2', '0') # Верно: каждый исходный символ рассматривается один раз.s = ''.join(    '2' if digit == '0'    else '0' if digit == '2'    else '1'    for digit in s) # Вместо блока выше можно использовать таблицу соответствия:# s = s.translate(str.maketrans('012', '210')) s = s.lstrip('0') or '0'r = int(s, 3)

s.lstrip('0') or '0' удаляет ведущие нули, но сохраняет корректную строку '0', если других цифр не осталось.

Например, одновременная замена превращает 10220 в 12002: каждая новая цифра получена из соответствующей исходной цифры, а не из промежуточной строки.

Всегда уточняйте, в какой записи считается сумма цифр. Для N = 14 сумма десятичных цифр равна пяти, а троичная запись 112₃ имеет сумму четыре.

Условия n % 3 == 0 и sum(map(int, s)) % 3 == 0 нельзя подменять: первое проверяет делимость самого числа, второе — делимость суммы цифр его текущей записи. Даже когда признак делимости связывает эти свойства, исполняйте буквально данное условие.

def to_base(n, base):    digits = ''    while n > 0:        digits = str(n % base) + digits        n //= base    return digits or '0' answers = [] for n in range(1, 10000):    s = to_base(n, 3)     if CONDITION:        s = TRANSFORMATION_1    else:        s = TRANSFORMATION_2     r = int(s, 3)     if RESULT_CONDITION:        answers.append((n, r))

В конце извлекайте ровно то, что спрашивают: min(n for n, r in answers), max(n for n, r in answers), min(r for n, r in answers) или max(r for n, r in answers). Минимальное N и минимальное R — разные вопросы.

N чётно                         n % 2 == 0N кратно 3                      n % 3 == 0сумма цифр чётна                sum(map(int, s)) % 2 == 0количество единиц чётно         s.count('1') % 2 == 0дописать 10 справа              s += '10'приписать 2 слева               s = '2' + sдописать последнюю цифру        s += s[-1]дописать две последние цифры    s += s[-2:]удалить последнюю цифру         s = s[:-1]заменить первую цифру на 12     s = '12' + s[1:]заменить две первые на 112      s = '112' + s[2:]