Формальное исполнение алгоритма

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

«На вход алгоритма подаётся натуральное число N. Строится его двоичная запись; если N чётное, к ней справа дописывается 10, если нечётное — 01. Полученная запись — двоичная запись числа R. Найди наименьшее N, для которого R больше 150».

Главное — различать число и его запись: алгоритм работает с цифрами записи, а спрашивают о числах. Сначала разберём, что сказано в условии:

Почти всё время будем смотреть на число 13 и его двоичную запись 1101, а для троичной системы — на число 29. Тема состоит из пяти подтем — у каждой своя страница. Идём по ним по порядку:

1. Число и его запись — ты сейчас здесь.
2. Дописывание цифр — что происходит с числом, когда к записи приписывают цифры.
3. Срезы, замены и сумма цифр — другие действия с записью.
4. Решение перебором — программа для задачи темы — ответ 38.
5. Решение от результата — та же задача без перебора N.

Каждое действие разобрано и вручную, и в программе на Python. На экзамене подойдёт любой способ, а второй пригодится для проверки.

Число и его запись — разные вещи. Рассмотрим 13₁₀ = 1101₂. Здесь записано одно и то же число, но двумя способами: 13 — его десятичная запись, 1101 — его двоичная запись. Нижний индекс показывает систему счисления. Запись 1101₂ нужно читать как «число, записанное цифрами 1101 в двоичной системе».

При переводе между системами значение числа не меняется. Меняется способ его записи.

Но если к двоичной записи 1101 дописать справа 0, получится 11010₂ = 26₁₀. Это уже другое число.

Поэтому в задании полезно мысленно разделять три объекта:

Алгоритм может выглядеть так:

N = 13 → s = 1101 → s = 11010 → R = 26.

В позиционной системе значение цифры зависит от её места. Начнём с привычной десятичной записи:

347 = 3 · 100 + 4 · 10 + 7 · 1 = 3 · 10² + 4 · 10¹ + 7 · 10⁰.

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

В двоичной системе принцип такой же, но соседние разряды отличаются по весу в два раза: 1, 2, 4, 8, 16, 32, … В троичной — в три раза: 1, 3, 9, 27, 81, …

Число, определяющее это отношение, называют основанием системы счисления. Дальше обозначим его q, чтобы не путать с исходным числом N.

В системе с основанием q значение каждой цифры меньше q. В двоичной системе цифры только 0 и 1, в троичной — 0, 1, 2, в восьмеричной — от 0 до 7. Поэтому 102 не может быть двоичной записью: цифра 2 в ней недопустима.

Разберём число 1101₂. Под каждой цифрой — вес её разряда, ниже — вклад цифры в число:

Для троичной записи: 1202₃ = 1 · 3³ + 2 · 3² + 0 · 3 + 2 = 27 + 18 + 2 = 47. Для восьмеричной: 157₈ = 1 · 64 + 5 · 8 + 7 = 111.

Отсчёт степеней начинается справа с нуля, потому что крайняя правая цифра показывает количество единиц: q⁰ = 1.

Перевод в другую систему через деление работает потому, что остаток раскрывает последнюю цифру. Возьмём десятичное число 347: 347 = 34 · 10 + 7. При делении на 10 целая часть частного равна 34, остаток равен 7. То есть остаток даёт последнюю десятичную цифру, а целая часть частного — число без неё.

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

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

Остатки получены в порядке 2, 0, 0, 1. Но сначала мы нашли последнюю цифру, затем предпоследнюю и так далее. Поэтому для обычной записи нужно прочитать остатки в обратном порядке: 29₁₀ = 1002₃. Проверим: 1002₃ = 27 + 2 = 29.

По длине записи видно, в каких пределах лежит число. Выпишем двоичные записи чисел от 1 до 15 и сгруппируем их по длине. Четырёхзначные записи идут от 1000 до 1111, то есть от 8 до 15. Самая маленькая из них — единица и нули, 1000 = 2³. Следующее число, 16 = 10000, уже пятизначное: 2⁴.

Нули в начале записи называют ведущими нулями: 00101₂ = 101₂ = 5. Значение одинаковое, но длина текста разная. Если следующий шаг зависит от длины или положения символов, это различие может оказаться существенным.

В Python удобно хранить число и его запись в разных переменных. Число n = 13 — целое, а запись s = '1101' — строка, то есть последовательность символов. Кавычки показывают, что перед нами текст. Сравни:

n = 13s = '1101'print(13 + 1)print('13' + '1')print(s + '0')

Для чисел + означает сложение, для строк — соединение. Соединение строк также называют конкатенацией. Для решения задания достаточно понимать его как «поставить одну запись вслед за другой».

Команда s = s + '0' означает: взять текущее содержимое s, дописать к нему символ 0 и сохранить получившуюся строку обратно в s. Знак = в программе означает присваивание: сначала вычисляется правая часть, затем результат сохраняется в переменной слева. Проверка равенства — двойной знак ==.

Готовые функции Python переводят число в запись — строку. В Python bin(13) возвращает строку '0b1101'. Первые два символа 0b — служебное обозначение двоичной записи. Они не являются её цифрами. Чтобы получить только цифры, берут bin(13)[2:] — строку начиная с символа с номером 2 и до конца. Номера символов и такие срезы подробно разберём в подтеме 3.

Для восьмеричной системы есть oct, для шестнадцатеричной — hex. Обратное преобразование делает int(s, q): читает строку s как запись в системе с основанием q.

print(bin(13)[2:], oct(13)[2:], hex(31)[2:])print(int('1101', 2), int('15', 8), int('1f', 16))print(int('1101'))

Важная тонкость: int('1101') даёт одну тысячу сто один, потому что без второго аргумента используется десятичная система. А int('1101', 2) даёт 13.

Для арифметики с цифрами нужны ещё три операции: остаток от деления n % q, целая часть частного n // q и длина строки len(s). Обычное / даёт дробь и здесь не нужно.

Само целое число в переменной не нужно считать «хранящимся в десятичной записи». Число и его текстовое представление — разные объекты. При обычном выводе целого числа Python показывает его десятичную запись.

Для троичной и других систем функцию перевода пишут сами. Готовой функции для троичной записи в Python нет. Но мы уже знаем, как переводить руками: делить на основание и ставить остатки справа налево. Функция to_base повторяет ровно эти действия. Её вызов to_base(29, 3) должен давать строку '1002'. Для оснований от 2 до 10 подойдёт такой код:

def to_base(n, q):    if n == 0:        return '0'     s = ''    x = n     while x > 0:        digit = x % q        s = str(digit) + s        x = x // q     return s  s = to_base(29, 3)print(s)print(int(s, 3))

Нажми «Запуск» в шапке блока и пройди программу по шагам: справа видно, как меняются x, digit и s, под кодом — что сделала каждая строка.

Разберём функцию по порядку. Она принимает два значения: n — переводимое неотрицательное целое число, q — основание системы.

Если число равно нулю, результат сразу готов: return возвращает строку '0' и завершает выполнение функции. Ноль обрабатывается отдельно, потому что цикл ниже для него не выполнится ни разу.

s = '' создаёт пустую строку — в неё будем собирать цифры. x = n создаёт рабочую переменную: её будем уменьшать, сохраняя исходное n. Цикл while x > 0 повторяет три действия, пока x больше нуля:

• digit = x % q находит последнюю цифру;
• s = str(digit) + s ставит найденную цифру слева от уже собранного результата. Почему слева? Потому что цифры извлекаются с конца: каждая следующая найденная цифра находится левее предыдущих;
• x = x // q удаляет последнюю цифру из числа, с которым мы работаем.

Это ровно шаги схемы перевода 29 выше: остатки 2, 0, 0, 1 становятся строками '2', '02', '002', '1002'. После этого x станет нулём, цикл завершится.

• Число и записьперевод меняет запись, а не число; дописанная цифра меняет число
• Разрядего вес — степень основания, отсчёт справа с нуля
• Перевод делениемостатки — цифры справа налево
• Длина записизадаёт диапазон чисел: четыре двоичные цифры — от 8 до 15
• Pythonbin(n)[2:], int(s, q), своя to_base(n, q)