Срезы, замены и сумма цифр

Алгоритм: в двоичной записи 46 = 101110 первые две цифры заменяют на 110. Что получится? Такие команды берут часть записи по её месту — первые или последние цифры — и переставляют, удаляют, заменяют.

Все такие команды собираются из срезов строки и соединения. Здесь же — переворот и инверсия записи и сумма цифр, по которой многие алгоритмы выбирают дописываемую цифру.

Нужную часть записи берут по номерам символов — индексам и срезам. Каждый символ строки имеет номер — индекс. В Python нумерация начинается с нуля: первая цифра записи s = '101110' — это s[0], вторая — s[1]. Отрицательные индексы считают с конца: s[-1] — последний символ, s[-2] — предпоследний.

Чтобы получить несколько символов, используют срез s[a:b]. Он берёт символы с индексами от a включительно до b не включительно. Например, s[1:4] берёт индексы 1, 2, 3 и даёт '011'.

Если граница не указана, срез идёт от начала или до конца строки. Выбери срез, чтобы увидеть, что он берёт:

s[:2]

'10'первые два символа

s[-2:]

'10'последние два

s[2:]

'1110'всё, кроме первых двух

s[:-2]

'1011'всё, кроме последних двух

s[::-1]

'011101'строка в обратном порядке

Если позиции в условии считают справа, нельзя без проверки применять срезы для позиций слева. «Вторая справа цифра» — это s[-2], а не s[1].

Почти любое действие задания собирается из срезов и соединения строк. Пусть s — текущая запись. Каждую команду условия можно перевести одной строкой:

скопировать последние две цифры в конец

s = s + s[-2:]

скопировать первые две цифры в конец

s = s + s[:2]

удалить первые две цифры

s = s[2:]

удалить последние две цифры

s = s[:-2]

первые две цифры заменить на 110

s = '110' + s[2:]

последние две цифры заменить на 01

s = s[:-2] + '01'

перевернуть запись

s = s[::-1]

перенести первую цифру в конец

s = s[1:] + s[0]

перенести последнюю цифру в начало

s = s[-1] + s[:-1]

В строке s = s + s[-2:] обе части справа вычисляются по старому значению s. После этого результат присваивается переменной.

Если после нескольких изменений нужно обратиться именно к исходной записи, сохрани её: original = s. Теперь original содержит исходный текст, а s можно дальше изменять. Сравни два алгоритма:

n = 46original = bin(n)[2:]s = original + '1's = s + original[-2:]print(s) s = bin(n)[2:]s = s + '1's = s + s[-2:]print(s)

В первом варианте последние две цифры взяты из исходной записи (10), во втором — уже из изменённой (01). Это два разных алгоритма, и условие всегда говорит, какой из них нужен.

Перевернуть запись и инвертировать её — разные действия. Перевернуть запись — прочитать её справа налево. Инвертировать двоичную запись — заменить каждый 0 на 1, а каждый 1 на 0. Например, для 1100 переворот даёт 0011, и инверсия тоже даёт 0011. На этом числе результаты случайно совпали. На другом уже нет: для 10110 переворот даёт 01101, а инверсия — 01001.

Поэтому ориентироваться нужно на смысл команды, а не на один пример.

Инверсию проще понять через число из одних единиц. Возьмём пятизначную двоичную запись 10110. После замены каждого 0 на 1 и каждого 1 на 0 получится 01001. Если сложить значения исходной и изменённой записей, в каждом разряде получится единица:

Длина записи здесь важна: инверсия трёх цифр 101 даёт 010 = 2, а восьми цифр 00000101 — уже 11111010 = 250. Сколько цифр брать, говорит условие.

Если символы меняют одновременно, уже заменённые нельзя заменять ещё раз. Пусть нужно поменять местами нули и единицы. Кажется, что можно написать s.replace('0', '1').replace('1', '0'). Но это ошибка.

Метод replace создаёт строку с указанными заменами. В цепочке второй вызов работает с результатом первого. Для строки '10' получится 10 → 11 → 00, а правильная инверсия — 10 → 01.

s = '10110'print(s.replace('0', '1').replace('1', '0'))

После первой замены в строке одни единицы, и вторая замена превращает их все в нули.

Надёжный способ — читать исходную строку и собирать новую: на каждом шаге анализируется символ исходной строки, поэтому уже заменённые символы больше не трогаются. Запусти программу по шагам и следи, как растёт new_s:

s = '10110'new_s = ''for digit in s:    if digit == '0':        new_s = new_s + '1'    else:        new_s = new_s + '0'print(new_s)

Ведущие нули не меняют число, но могут изменить следующие действия со строкой. Python корректно прочитает int('0011', 2) и получит 3. Поэтому перед окончательным переводом специально удалять ведущие нули обычно не нужно.

Но рассмотрим два последовательных шага: получить строку 0011, затем дописать слева 1. Если сохранить строку, 0011 → 10011, то результат равен 19. Если самовольно убрать нули между шагами, 0011 → 11 → 111, то результат равен 7. Алгоритмы получились разными.

Удаляй ведущие нули в тот момент, когда этого требует условие, либо при окончательном переходе от записи к числу, если промежуточных действий больше нет.

Также помни: строка '0' — корректная запись нуля, а пустая строка '' — не запись числа, и int('', 2) вызовет ошибку. Если операция удаляет все символы, нужно проверить, допускает ли условие такой случай и как он трактуется.

Чётность самого числа видна по последней двоичной цифре, а сумма цифр зависит от всей записи. Чётное число делится на 2 без остатка. Для двоичной записи чётность самого числа определяется последней цифрой: 0 — число чётное, 1 — нечётное.

Но сумма двоичных цифр зависит от всей записи:

Из таблицы видно: эти свойства могут совпадать, а могут различаться.

В двоичной записи сумма цифр равна количеству единиц: 1 + 1 + 0 + 1 = 3. Нули ничего не добавляют, каждая единица добавляет 1. Поэтому условия «сумма двоичных цифр чётная» и «количество единиц в двоичной записи чётное» равносильны. Но они не равносильны условию «N чётное».

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

Сумму цифр считают в той системе, которую называет условие. Для двоичной строки s.count('1') — одновременно количество единиц и сумма цифр. Для троичной строки — s.count('1') + 2 * s.count('2'). Более общий вариант для систем с цифрами 0–9 проходит по строке циклом for digit in s: он по очереди подставляет в переменную digit каждый символ строки.

s = to_base(23, 3)print(s, s.count('1') + 2 * s.count('2')) total = 0for digit in s:    total = total + int(digit)print(total)

Здесь 23 = 212₃. Цикл прибавляет 2, затем 1, затем 2. Преобразование int(digit) нужно потому, что символ '2' — текст, а для сложения требуется число 2.

Если шаг повторяют, второй раз его применяют уже к новой записи. Рассмотрим важный алгоритм:

1. строится двоичная запись N;
2. вычисляется сумма её цифр;
3. остаток от деления суммы на 2 дописывается справа;
4. для получившейся записи то же действие выполняется ещё раз.

Возьмём N = 13, s = 1101. Первая сумма 1 + 1 + 0 + 1 = 3. Остаток от деления 3 на 2 равен 1: 1101 → 11011. Теперь считаем сумму новой записи: 1 + 1 + 0 + 1 + 1 = 4. Остаток равен 0: 11011 → 110110. Получаем R = 110110₂ = 54.

Почему второй дописанный разряд всегда равен нулю? Возможны два случая. Если единиц было чётное количество, первым дописывается 0 и количество остаётся чётным. Если нечётное, первым дописывается 1 и количество становится чётным. В обоих случаях перед вторым шагом единиц чётное количество, и второй разряд — 0.

Следовательно, итоговый хвост — 00, если исходное количество единиц чётное, и 10, если нечётное. Отсюда:

R = 4N, если количество единиц чётное; R = 4N + 2, если нечётное.

Это свойство именно последовательного пересчёта. Если алгоритм говорит «найти остаток один раз и дописать его дважды», результаты другие: 00 или 11. Различие всего в нескольких словах условия, а числа на выходе меняются. Запусти обе версии по шагам и сравни, сколько раз считается count:

def parity_twice(n):    s = bin(n)[2:]    s = s + str(s.count('1') % 2)    s = s + str(s.count('1') % 2)    return int(s, 2)  def parity_copied(n):    s = bin(n)[2:]    bit = str(s.count('1') % 2)    return int(s + bit + bit, 2)  print(parity_twice(13), parity_copied(13))

В parity_twice второй count считает единицы уже новой строки — это и есть пересчёт. В parity_copied остаток посчитан один раз, поэтому к 13 дописывается 11, и R = 4 · 13 + 3 = 55.

Десятичную запись обрабатывают так же, как двоичную, — через строку. Сумма десятичных цифр числа — это сумма цифр строки str(n). В задачах с десятичной записью могут рассматриваться и все соседние пары или тройки цифр.

Пусть N = 30042. Все тройки соседних цифр: 300, 004, 042. Они перекрываются: после каждой тройки начало сдвигается на одну позицию. Как числа это 300, 4, 42. Если результат — разность максимального и минимального значения, R = 300 − 4 = 296. В программе по шагам видно, как i пробегает начала троек, а список values пополняется:

def transform_windows(n):    s = str(n)    values = []     for i in range(len(s) - 2):        part = s[i:i + 3]        values.append(int(part))     return max(values) - min(values)  print(transform_windows(30042))

Здесь values = [] создаёт пустой список, append добавляет в его конец новое значение, а max и min находят наибольшее и наименьшее. Функция предполагает, что в записи не меньше трёх цифр.

Почему range(len(s) - 2)? При длине 5 тройка может начинаться с индекса 0, 1 или 2. Начать с индекса 3 нельзя: останется только два символа. В общем случае для фрагментов длины k число возможных начал равно L − k + 1. Поэтому используют range(len(s) - k + 1).

Перед числовым сравнением фрагменты нужно превратить в числа. Например, строки '11' и '100' сравниваются посимвольно. Это не то же самое, что сравнение чисел 11 и 100 или двоичных чисел 11₂ и 100₂.

• Срезs[a:b] — от a до b − 1; s[-2:] — две последние
• Заменасрез без старых цифр плюс новый блок
• Переворот и инверсияразные действия; длину записи для инверсии задаёт условие
• Одновременная заменапо исходной строке, а не цепочкой replace
• Сумма цифрпо той записи, которую называет условие; при повторном шаге — по новой