Задание 13 · Анализ хода исполнения алгоритма
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — сколько программ из команд «+1» и «×2» ведут из 2 в 20 через 6 и мимо 9 — прошла через первые три подтемы, и каждая добавляла к решению новый шаг. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Команды и дерево»: дерево — на коротком участке. Точками отмечены новые строки.
- Подтема 2, «Таблица количеств»: таблица вместо дерева.
- Подтема 3, «Участки и запреты»: участки — умножить, запрет — ноль. Ответ задачи темы — 9.
Дальше та же таблица работает с другими командами: условными и новыми (подтема 4), убывающими и делением (подтема 5), а дополнительные уроки — с группами программ и длиной программы.
Карта темы
Каждая подтема дала одно правило таблицы, и любое решение собирается из них. Сверху — путь от команд к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Командыоткуда каждая ведёт в n
- Участкиразрез по обязательным, 0 в запретах
- Таблица1 в старте, ответ в цели
1Команды, программы и дерево
- программаномера команд по порядку: 12 и 21 — разные
f(x + 1, y) + f(x * 2, y)то же дерево рекурсией
2Таблица количества программ
- K(старт) = 1туда ведёт пустая программа
- K(n)сумма K чисел, из которых команды ведут в n
k[n] += k[n // 2]вклад «×2» — только для чётного n
3Обязательные и запрещённые числа
- через числоучастки перемножают
- без числав нём K = 0
- новый участокснова начинается с 1
4Новые и условные команды
- 2x + 1в нечётное n из (n − 1) / 2
- условная командавклад только там, где она выполняется
5Убывание и деление
- таблицасверху вниз, обрыв ниже цели
- ÷2 нацелов n ведут 2n и 2n + 1
6Группы программ и обратные вопросыдополнительный урок
- через A или Bчерез A + через B − через оба
7Длина и память программыдополнительный урок
- ровно L командв состоянии — остаток длины
- не подрядв состоянии — последняя команда
Как решать
Любое задание 13 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- 0 в старте
- K(старт) = 0 → K(старт) = 1. Спроси себя: не осталась ли вся таблица нулевой?подтема 2
- округлённое деление
- в 7 по «×2» ведёт 7 // 2 = 3 → у нечётного числа такого вклада нет. Спроси себя: 3 · 2 — это 7?подтема 2
- совпавшие переходы
- из 2 в 4 ведут «+2» и «×2», а K(2) взят раз → слагаемых столько, сколько команд ведут в n. Спроси себя: сколько команд ведут в это число?подтема 2
- сложили участки
- через 6: 3 + 6 → 3 · 6 — каждая первая часть с каждой второй. Спроси себя: сколько пар «первая часть — вторая»?подтема 3
- старое значение
- второй участок начали с K(6) = 3 → новый участок начинается с 1. Спроси себя: не умножу ли я на 3 дважды?подтема 3
- обнулён хвост
- после 9 обнулили всё до 20 → ноль только в 9: в 12 ведёт прыжок из 6. Спроси себя: есть ли путь в это число мимо 9?подтема 3
- отсечение при убывании
- при убывающих командах обрыв по x > y → обрывают, когда x < y. Спроси себя: в какую сторону идёт число?подтема 5
- «или» без поправки
- через 3 или 4: 2 + 2 → вычесть программы через оба. Спроси себя: нет ли программ, которые идут через оба?подтема 6
Итог
Тема пройдена: задача темы решена от дерева до ответа 9. Вот что взять с собой.
- ПорядокКоманды, участки, таблица, запреты, проверка.
- Таблица1 в старте, в n — сумма вкладов команд.
- УчасткиОбязательное число делит путь — участки перемножают.
- ЗапретыВ запрещённом числе 0, остальное как обычно.
- Задача темы3 программы до 6, 3 после — ответ 9.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Команды «+1» и «×2». Из каких чисел можно попасть в 14?
ОтветСкрыть ответ
Из 13 по «+1» и из 7 по «×2»: K(14) = K(13) + K(7).
Из 2 в 6 ведут 3 программы, из 6 в 20 — 6. Сколько программ из 2 в 20 через 6?
ОтветСкрыть ответ
3 · 6 = 18: каждая первая часть соединяется с каждой второй.
Траектория не должна содержать 9. Что ставят в таблицу в клетку 9?
ОтветСкрыть ответ
0: через 9 программ нет. Остальные клетки считают как обычно.
Команды «−1» и «÷2 нацело». Из каких чисел попадают в 5?
ОтветСкрыть ответ
Из 6 по «−1», из 10 и 11 по «÷2»: K(5) = K(6) + K(10) + K(11).
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Из 3 в 27
Команды: 1. Прибавить 1; 2. Умножить на 2. Сколько существует программ, для которых при исходном числе 3 результатом является число 27?
Введите число.
Подсказка
Таблица K(n) от 3 до 27.
Решение
K(n) = K(n − 1), а для чётного n ещё + K(n / 2). Таблица от K(3) = 1 до 27 даёт 34.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(3, 27))Ответ: 34
Из 2 в 15 через 8 без 11
Команды: 1. Прибавить 1; 2. Прибавить 2; 3. Умножить на 2. Сколько существует программ, для которых при исходном числе 2 результатом является число 15, и при этом траектория вычислений содержит число 8 и не содержит числа 11?
Введите число.
Подсказка
Разрежь путь в 8, запрет 11 — на втором участке.
Решение
Из 2 в 8 — 23 программы. Из 8 в 15 без 11 — 6. Ответ 23 · 6 = 138.
def f(x, y): if x == 11 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 2, y) + f(x * 2, y) print(f(2, 8) * f(8, 15))Ответ: 138
Из 13 в 70 с перестановкой
Команды: 1. Прибавить 1; 2. Поменять местами две младшие цифры, если цифра десятков меньше цифры единиц (иначе команда не выполняется). Сколько существует программ, для которых при исходном числе 13 результатом является число 70?
Введите число.
Подсказка
Перестановка — только при десятках меньше единиц.
Решение
Перестановка увеличивает число на 9(u − t), поэтому считают по возрастанию. Из 13 в 70 ведут 55 программ.
def f(x, y): if x > y: return 0 if x == y: return 1 t, u = x // 10 % 10, x % 10 total = f(x + 1, y) if t < u: total += f(x + 9 * (u - t), y) return total print(f(13, 70))Ответ: 55
Из 30 в 3 через 12
Команды: 1. Вычесть 1; 2. Разделить нацело на 2 (остаток отбрасывается). Сколько существует программ, для которых при исходном числе 30 результатом является число 3, и при этом траектория вычислений содержит число 12?
Введите число.
Подсказка
Разрежь путь в 12, у деления нацело два предшественника.
Решение
Из 30 в 12 — 8 программ, из 12 в 3 — 9. Ответ 8 · 9 = 72.
def f(x, y): if x < y: return 0 if x == y: return 1 total = f(x - 1, y) total += f(x // 2, y) return total print(f(30, 12) * f(12, 3))Ответ: 72
Из 1 в 29 без 9
Команды: 1. Прибавить 2; 2. Умножить на 3. Сколько существует программ, для которых при исходном числе 1 результатом является число 29, и при этом траектория вычислений не содержит числа 9?
Введите число.
Подсказка
Из 1 получаются только нечётные числа; обнули 9.
Решение
Числа остаются нечётными. С нулём в 9 таблица от 1 до 29 даёт 4 программы.
def f(x, y): if x == 9 or x > y: return 0 if x == y: return 1 return f(x + 2, y) + f(x * 3, y) print(f(1, 29))Ответ: 4