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

Что получится, если к двоичной записи 11 = 1011 дописать справа 01? А если первые две цифры заменить или посчитать сумму цифр? Задание 5 состоит из таких действий.

Каждое действие с записью — это строка программы и понятное изменение числа: дописанная справа цифра сдвигает старые цифры. Здесь — дописывание; срезы, замены и сумма цифр — в подтеме 3. Функция to_base из подтемы 1 нам ещё понадобится.

Дописанная справа цифра сдвигает все старые цифры на разряд влево. В десятичной системе 37 → 374. Что произошло с числом? 374 = 37 · 10 + 4. Все исходные цифры сдвинулись на один разряд влево. Их вклад увеличился в десять раз. В освободившийся разряд единиц поставили 4.

В двоичной системе 1011₂ → 10110₂. Поскольку 1011₂ = 11, получаем R = 11 · 2 + 0 = 22. Если дописать единицу, 1011₂ → 10111₂, то R = 11 · 2 + 1 = 23.

Дописали 0 — число удвоилось, дописали 1 — удвоилось и выросло на 1.

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

Например, к 1011₂ = 11 дописываем 01: 1011₂ → 101101₂. Дописали две цифры: старое число умножилось на 4, и к нему прибавилось значение блока — 44 + 1 = 45.

Особенно внимательно обращайся с нулями в начале дописываемого блока. У блоков 1, 01, 001 одинаковое числовое значение — 1. Но разная длина:

1

R = 2N + 1один разряд: N · 2¹

01

R = 4N + 1два разряда: N · 2²

001

R = 8N + 1три разряда: N · 2³

Например, для N = 11: 11 · 8 + 1 = 89. И действительно, 1011₂ → 1011001₂ = 89.

Нули в начале отдельного блока нельзя выкидывать, если условие требует дописать именно этот блок.

Если дописать цифры слева, их вес зависит от длины прежней записи. Пусть N = 11 = 1011₂. Дописали слева 10: 1011 → 101011. Исходные цифры остались на своих местах. Новый блок оказался левее четырёх исходных разрядов. Поэтому R = 10₂ · 2⁴ + 11 = 2 · 16 + 11 = 43.

В программе дописывание — это соединение строк. Дописать справа 01 — s = s + '01', слева 10 — s = '10' + s. Скопировать в конец последние две цифры — s = s + s[-2:]: срез s[-2:] берёт два последних символа. Так любая команда условия становится одной строкой программы.

Чаще всего блок выбирают по условию на N. Например: если N чётное, слева дописать 1, а справа 0; если нечётное — слева 11, а справа 1.

Проверим руками на двух входах. 6 = 110₂, оно чётное: 1 + 110 + 0 = 11100. Справа одна цифра, поэтому старое число удвоилось: 12. Слева единица встала над четырьмя разрядами: 2⁴ = 16. R = 16 + 12 = 28. Число 7 = 111₂ нечётное: 11 + 111 + 1 = 111111, R = 63.

В программе выбор ветви — if с else, а чётность — остаток n % 2. Запусти её по шагам и посмотри, какую ветвь проходит каждый вызов:

def transform(n):    s = bin(n)[2:]    if n % 2 == 0:        s = '1' + s + '0'    else:        s = '11' + s + '1'    return int(s, 2)  print(transform(6))print(transform(7))

Для чётного 6 выполняется строка 4 и пропускается строка 6, для нечётного 7 — наоборот. Посмотрим на результаты подряд:

for n in range(4, 9):    print(n, transform(n))

Обрати внимание: при N = 8 результат меньше, чем при N = 7. Результат не обязан расти вместе с N, если ветви дописывают разные блоки. Как с этим жить при поиске ответа, разберём в подтеме 4.

Дописать результат вычисления — не всегда значит применить str. Предположим, алгоритм требует:

1. найти остаток от деления N на 3;
2. умножить его на 7;
3. перевести произведение в троичную систему;
4. дописать эту запись справа.

Если остаток равен 2, то 2 · 7 = 14. Но дописывать нужно не 14, а троичную запись: 14₁₀ = 112₃.

n = 14s = to_base(n, 3)extra = n % 3 * 7print(s + to_base(extra, 3))print(s + str(extra))

Первая строка правильная: дописана троичная запись 112. Вторая неправильная: str(14) даёт десятичную строку '14'. Более того, цифра 4 вообще недопустима в троичной записи.

Применять str можно, когда дописывается одна допустимая цифра нужной системы, например str(n % 2). Например, остаток от деления на 2 — это 0 или 1.

Каждый раз задавай себе вопрос: я дописываю одну цифру или запись некоторого числа в указанной системе?

• Дописать справастарые цифры сдвигаются: одна двоичная цифра — число удвоилось, две — умножилось на 4
• Блок 01 и 001длина блока важна вместе с нулями в его начале
• Дописать слевастарые цифры не двигаются, блок встаёт над ними
• Блок по условиюif и else по условию на N; результат может не расти вместе с N
• Записанное числодописывают его запись в нужной системе, а не str