Подтема 3 из 7
Обязательные и запрещённые числа
Как учесть обязательное и запрещённое число — и ответ задачи темы.
Обязательное число
Сколько программ из 2 в 20 проходят через 6? Запрет 9 пока не учитываем.
Обязательное число делит программу на две части, и количества частей перемножают. Любая такая программа сначала переводит 2 в 6, а потом 6 в 20:
- первую часть можно выбрать 3 способами — подтема 1;
- вторую — 6 способами — подтема 2;
- любая первая часть подходит к любой второй.
Значит, программ 3 · 6 = 18.
Обрати внимание: второй участок считают заново — в 6 ставят 1. Если продолжить общую таблицу от 2 со значением K(6) = 3 и потом ещё умножить на 3, первые части посчитаются дважды.
Запрещённое число
Теперь 9 запрещено. Сколько программ из 6 в 20 его обходят?
В запрещённое число ставят K = 0: ни одна программа не может через него пройти. Остальное считают как обычно: ноль просто ничего не добавляет к сумме.
В 10 и 11 из 6 можно попасть только через 9, поэтому там тоже 0. А в 12 можно перепрыгнуть 9 умножением: 6 · 2 = 12. Значит, K(12) = 1, и дальше счёт продолжается.
| n | Слагаемые | K(n) |
|---|---|---|
| 6 | старт | 1 |
| 7, 8 | только «+1» | 1 |
| 9 | запрещено | 0 |
| 10, 11 | только через 9 | 0 |
| 12 | K(11) + K(6) | 1 |
| 13 | K(12) | 1 |
| 14 | K(13) + K(7) | 2 |
| 15 | K(14) | 2 |
| 16 | K(15) + K(8) | 3 |
| 17 | K(16) | 3 |
| 18 | K(17) + K(9) | 3 |
| 19 | K(18) | 3 |
| 20 | K(19) + K(10) | 3 |
Ответ задачи темы
Итак, сколько программ в задаче темы?
Запрет учитывают на каждом участке, а участки перемножают: 3 · 3 = 9 — ответ задачи темы. На первом участке 9 не встречается: оно больше 6.
Три программы второго участка можно выписать:
- 6 · 2 = 12, затем «+1» до 20;
- 6 + 1 = 7, 7 · 2 = 14, затем «+1» до 20;
- 6 → 7 → 8, 8 · 2 = 16, затем «+1» до 20.
Проверка вычитанием: через 6 всего 18 программ, через 6 и 9 — 3 · 1 · 3 = 9 (участки 2 → 6, 6 → 9, 9 → 20), значит, без 9 — 18 − 9 = 9.
Запрет — это ещё одна проверка в начале функции: если x равно 9, программ нет — условия соединяем через . А обязательное число — два вызова, перемноженные между собой:
def f(x, y): if x == 9 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 6) * f(6, 20))Проверку запрета ставят перед проверкой цели: иначе запрещённая цель засчиталась бы как успех.
Несколько условий
Что делать, если обязательных чисел два — например, 4 и 8 на пути из 2 в 16?
Каждое обязательное число — ещё один разрез пути. Участков становится больше, а запрет обнуляет своё число на том участке, где оно встречается. Команды только увеличивают число, поэтому порядок 2 → 4 → 8 → 16: 2 · 2 · 2 = 8 программ.
Тонкости:запрет по свойству числа
Запрет может быть задан свойством: «траектория не содержит чисел, оканчивающихся на 7». На пути из 2 в 20 обнуляют и 7, и 17 — остаётся 6 программ из 30. Последняя цифра числа — остаток от деления на 10: x % 10 == 7.
Если запрещённое число совпадает с обязательным или с целью, программ нет: ответ 0.
Итого
- Обязательноепроизведение участков
- Новый участокзаново с единицы
- Запрещённое0 в таблице, перепрыгнуть можно
- Задача темы3 · 3 = 9
- Проверкавсе через 6 минус через 6 и 9
- Python
f(2, 6) * f(6, 20)
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Через 5
Команды «+1» и «×2». Сколько программ переводят 2 в 12, если траектория содержит 5?
Введите число.
Подсказка
Посчитай участки 2 → 5 и 5 → 12 и перемножь.
Решение
Из 2 в 5 две программы (111 и 21), из 5 в 12 три: 12 (5 → 6 → 12), 211 (5 → 10 → 11 → 12) и семь прибавлений. Каждая первая часть сочетается с каждой второй: 2 · 3 = 6.
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(2, 5) * f(5, 12))Ответ: 6
Без 5
Команды «+1» и «×2». Сколько программ переводят 2 в 12, если траектория не содержит 5?
Введите число.
Подсказка
Поставь 0 в 5 и продолжи таблицу.
Решение
Всего из 2 в 12 десять программ, через 5 — 2 · 3 = 6, без 5 — 10 − 6 = 4. В таблице это K(5) = 0.
def f(x, y): if x == 5 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 12))Ответ: 4
Через 6 без 9
Команды «+1» и «×2». Сколько программ переводят 2 в 16, если траектория содержит 6 и не содержит 9?
Введите число.
Подсказка
Разрежь путь в 6, запрет учитывай на втором участке.
Решение
Из 2 в 6 три программы. Из 6 в 16 без 9 — три: через 12 (6 · 2), через 14 (7 · 2) и через 16 (8 · 2). Ответ 3 · 3 = 9.
def f(x, y): if x == 9 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 6) * f(6, 16))Ответ: 9
Из 1 в 20 через 10
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1; 2. Умножить на 2. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10 и не содержит числа 15?
Введите число.
Подсказка
Разрежь путь в 10; 15 встречается только на втором участке.
Решение
Из 1 в 10 четырнадцать программ. Из 10 в 20 без 15 — одна: 10 · 2 = 20, прибавления проходят через 15. Ответ 14 · 1 = 14.
def f(x, y): if x == 15 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(1, 10) * f(10, 20))Ответ: 14
Из 3 в 30 через 12 без 20
Исполнитель преобразует число на экране. Команды: 1. Прибавить 1; 2. Умножить на 2. Сколько существует программ, для которых при исходном числе 3 результатом является число 30, и при этом траектория вычислений содержит число 12 и не содержит числа 20?
Введите число.
Подсказка
Разрежь путь в 12, запрет 20 учитывай на втором участке.
Решение
Из 3 в 12 шесть программ. Из 12 в 30 без 20 — четыре: удвоить 12, 13, 14 или 15 и дальше прибавлять. Из 16 и больше удвоение перепрыгивает 30, а одни прибавления до 30 проходят через 20. Ответ 6 · 4 = 24.
def f(x, y): if x == 20 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(3, 12) * f(12, 30))Ответ: 24
Из 2 в 40 через 10 без 25
Команды «+1» и «×2». Сколько программ переводят 2 в 40, если траектория содержит 10 и не содержит 25?
Введите число.
Подсказка
Разрежь путь в 10, запрет 25 — на втором участке.
Решение
Из 2 в 10 семь программ, из 10 в 40 без 25 — девять. Ответ 7 · 9 = 63.
def f(x, y): if x == 25 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 10) * f(10, 40))Ответ: 63
Порядок проверок
В функции, которая должна считать программы без числа 6, проверки поставили в таком порядке. Что выведет программа?
def g(x, y): if x == y: return 1 if x == 6 or x > y: return 0 return g(x + 1, y) + g(x * 2, y) print(g(2, 6))Введите число.
Подсказка
Какая проверка сработает первой, когда x равен 6?
Решение
Цель 6 проверяется раньше запрета, поэтому g(6, 6) возвращает 1, и функция считает все 3 программы из 2 в 6. При правильном порядке запрещённая цель дала бы 0.
def g(x, y): if x == y: return 1 if x == 6 or x > y: return 0 return g(x + 1, y) + g(x * 2, y) print(g(2, 6))Ответ: 3
Через 4 и 8
Команды «+1» и «×2». Сколько программ переводят 2 в 16, если траектория содержит и 4, и 8?
Введите число.
Подсказка
Число растёт, поэтому порядок 4 → 8 — единственный.
Решение
Три участка: 2 → 4, 4 → 8 и 8 → 16 — по две программы на каждом (прибавления или одно удвоение). 2 · 2 · 2 = 8.
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(2, 4) * f(4, 8) * f(8, 16))Ответ: 8
Без чисел, оканчивающихся на 7
Команды «+1» и «×2». Сколько программ переводят 2 в 20, если траектория не содержит чисел, оканчивающихся на 7?
Введите число.
Подсказка
Запрещены сразу 7 и 17.
Решение
Обнуляем K(7) и K(17). Всего из 2 в 20 было бы 30 программ, без чисел на 7 остаётся 6: программы, доходящие до 20 прибавлениями, проходят через 17.
def f(x, y): if x % 10 == 7 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 20))Ответ: 6