Задание 5 · Формальное исполнение алгоритма
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — наименьшее N, для которого R больше 150, — прошла через подтемы, и каждая добавляла к решению новый шаг. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Число и его запись»: число и запись — bin и int. Точками отмечены новые строки.
- Подтема 2, «Дописывание цифр»: две цифры справа — R растёт вчетверо.
- Подтема 4, «Решение перебором»: первое N с R > 150.
- Подтема 5, «Решение от результата»: перебор R: хвост и остаток. Ответ задачи темы — 38.
Задача не менялась — менялся способ: запись числа, дописывание, программа перебором и решение без программы, от результата. Срезы и замены из подтемы 3 в задаче темы не понадобились — они нужны, когда алгоритм переставляет или заменяет цифры.
Карта темы
Каждая подтема дала несколько приёмов, и любое решение собирается из них. Сверху — путь от числа к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- ЗаписьN → строка цифр в нужной системе
- Действиякаждая команда — одна строка кода
- Ответперебором или от результата
1Число и его запись
bin(n)[2:]двоичная запись без приставки 0bint(s, q)запись в системе q → числоto_base(n, q)запись в троичной и других системах
2Дописывание цифр
s + '01'дописать справа: в двоичной R = 4N + 1'10' + sдописать слева: старшие разряды- блок 01две цифры, а не одна
3Срезы, замены и сумма цифр
s[-2:]две последние цифрыs[::-1]переворотs.count('1')сумма двоичных цифр- обмен 0 и 1через третий символ, не двумя replace
4Решение перебором
- наименьшее Nпервое подходящее, затем break
- наименьшее Rперебрать всё, хранить лучшие R и N
- границаR ≥ N, если цифры только дописывают
5Решение от результата
- хвост Rсовпадает с дописанным блоком
- остаток слеваэто запись N — проверь её свойство
Как решать
Любое задание 5 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Порог из условия переводят буквально: «больше T» — это r > T, «не меньше T» — r >= T, «не превышает T» — r <= T.
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- str вместо перевода
str(n)→bin(n)[2:]. Спроси себя: в какой системе нужна запись?подтема 1- чётность не того
- проверили чётность N → проверяют то, что названо: например, сумму цифр. Спроси себя: какую величину проверяет условие?подтема 2
- старая сумма
- второй шаг считает по старой записи → каждый шаг — по текущей записи. Спроси себя: к какой версии записи относится шаг?подтема 2
- два replace
s.replace('0','1').replace('1','0')→ обмен через третий символ. Спроси себя: не заменились ли новые символы повторно?подтема 3- маленький диапазон
- range(1, 100) без обоснования → граница из свойств алгоритма. Спроси себя: почему ответ точно не больше границы?подтема 4
- первый R
- наименьшее R — первое найденное → перебрать всё и хранить лучшее. Спроси себя: растёт ли R вместе с N?подтема 4
- > и >=
r >= 150→r > 150. Спроси себя: «больше» или «не меньше»?подтема 4- r вместо n
print(r)→print(n). Спроси себя: что спрашивает последняя строка условия?подтема 5
Итог
Тема пройдена: задача темы решена и программой, и от результата — ответ 38. Вот что взять с собой.
- ПорядокЗапись, действия, пример, поиск, ответ.
- ЗаписьАлгоритм работает с цифрами, спрашивают о числах.
- ДействияКаждая команда — строка кода по текущей записи.
- ПоискПеребор с обоснованной границей или от результата.
- Задача темыN = 38: 100110 + 10 = 10011010, R = 154.
Проверьте себя
Ответь сначала сам, потом открой ответ.
К двоичной записи N справа дописали 01. Как R выражается через N?
ОтветСкрыть ответ
R = 4N + 1: две цифры справа сдвигают запись на два разряда, а 01 добавляет 1.
Почему в задаче темы перебор можно остановить на первом N с R больше 150?
ОтветСкрыть ответ
Цифры только дописываются, поэтому больший N даёт больший R: первое подходящее N и есть наименьшее.
R = 153, запись 10011001. Мог ли алгоритм задачи темы его выдать?
ОтветСкрыть ответ
Нет: хвост 01 дописывают к нечётным, а слева остаётся 100110 = 38 — чётное.
Спрашивают наименьшее R, а алгоритм иногда уменьшает число. Можно ли остановиться на первом найденном?
ОтветСкрыть ответ
Нет: R не растёт вместе с N. Нужно перебрать весь диапазон и хранить наименьшее R.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Наибольшее R не больше 150
На вход алгоритма подаётся натуральное число N. Строится двоичная запись N. Если N чётное, слева к ней дописывается 10; если нечётное, слева дописывается 1, а справа — 11. Полученная запись — двоичная запись числа R. Укажи наибольшее R, не превышающее 150.
Введите число.
Подсказка
R ≥ N, поэтому хватает перебора N до 150.
Решение
127 при N = 15: 1111₂ → 1111111₂. Алгоритм только дописывает, R ≥ N, поэтому хватает N ≤ 150.
Решение программой
best = 0for n in range(1, 151): s = bin(n)[2:] if n % 2 == 0: s = '10' + s else: s = '1' + s + '11' r = int(s, 2) if r <= 150: best = max(best, r)print(best)Ответ: 127
Дважды дописать остаток суммы на 3
На вход алгоритма подаётся натуральное число N. Строится троичная запись N. Затем два раза подряд к текущей записи справа дописывается остаток от деления суммы её цифр на 3. Полученная запись — троичная запись числа R. Укажи наименьшее N, для которого R больше 400.
Введите число.
Подсказка
Сумма цифр каждый раз считается по текущей троичной записи.
Решение
45 = 1200₃, сумма цифр 3, дважды дописывается 0, R = 120000₃ = 405.
Решение программой
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 n = 1while True: s = to_base(n, 3) for _ in range(2): total = 0 for c in s: total += int(c) s += str(total % 3) if int(s, 3) > 400: print(n) break n += 1Ответ: 45
Переворот и единица справа
На вход алгоритма подаётся натуральное число N. Двоичная запись N переворачивается (читается справа налево), затем справа дописывается 1. Полученная запись — двоичная запись числа R. Укажи наименьшее N, для которого R больше 1000.
Введите число.
Подсказка
R не растёт вместе с N, но перебор по возрастанию N найдёт наименьшее.
Решение
R больше 1000 только у записей из 10 и более цифр, то есть у N ≥ 256. 319 = 100111111₂ → 1111110011₂ = 1011.
Решение программой
n = 1while True: s = bin(n)[2:][::-1] + '1' if int(s, 2) > 1000: print(n) break n += 1Ответ: 319
Восьмеричный алгоритм
На вход алгоритма подаётся натуральное число N. Строится восьмеричная запись N. Если N чётное, справа к ней дописывается её первая цифра; иначе остаток от деления N на 5 записывается в восьмеричной системе и дописывается слева. Полученная запись — восьмеричная запись числа R. Укажи такое N, при котором R — наименьшее среди чисел, больших 600.
Введите число.
Подсказка
Восьмеричная запись — oct(n)[2:]; храни и N, и R.
Решение
91 = 133₈, нечётное, 91 mod 5 = 1, R = 1133₈ = 603. R ≥ N, поэтому входы больше 603 не нужны.
Решение программой
best_r = Nonebest_n = Nonefor n in range(1, 604): s = oct(n)[2:] if n % 2 == 0: s = s + s[0] else: s = oct(n % 5)[2:] + s r = int(s, 8) if r > 600 and (best_r is None or r < best_r): best_r = r best_n = nprint(best_n)Ответ: 91
Без нулей и задом наперёд
На вход алгоритма подаётся натуральное число N ≥ 10. Из десятичной записи N удаляются все нули, оставшиеся цифры записываются в обратном порядке, и получившаяся запись — десятичная запись числа R. Сколько различных значений R получается при N от 10 до 999?
Введите число.
Подсказка
Различные результаты собирает множество.
Решение
Программа ниже строит R для каждого N от 10 до 999 и складывает результаты в множество: одинаковые значения учитываются один раз. Различных результатов 819.
Решение программой
results = set()for n in range(10, 1000): s = str(n).replace('0', '')[::-1] results.add(int(s))print(len(results))Ответ: 819