Подтема 4 из 7
Новые и условные команды
Другие команды — 2x + 1, дописать цифру, квадрат, перестановка: из какого числа они ведут в n.
Новая команда
Что меняется, если вместо «×2» у исполнителя другая команда — например, «умножь на 2 и прибавь 1»?
Метод тот же: K(n) — сумма по командам, которые ведут в n. Новое только одно: для каждой команды нужно понять, из какого числа она даёт n. Такое число называют предшественником.
Спроси: «Из какого числа p команда даёт n?» — и реши это как уравнение. Для «2x + 1» и n = 9: 2p + 1 = 9, p = 4. Если p не целое или команда к нему неприменима, слагаемого нет: 2p + 1 = 10 даёт p = 4,5 — в 10 эта команда не ведёт.
| Команда | Из какого числа | Пример |
|---|---|---|
| +k | n − k | «+2»: 7 из 5 |
| ×k | n / k, если делится | «×3»: 12 из 4, в 13 не ведёт |
| 2x + 1 | (n − 1) / 2, если n нечётное | 9 из 4 |
| дописать цифру d | n без последней цифры, если она d | d = 4: 154 из 15 |
| x² | √n, если n — точный квадрат | 16 из 4 |
Составная команда
Команды «+1» и «2x + 1». Сколько программ переводят 1 в 13?
«2x + 1» — это одна команда, а не две: из 4 она сразу даёт 9. И чётное число она дать не может. Значит, в нечётное n она ведёт из (n − 1) / 2, а в чётное — ниоткуда. Поэтому K(n) = K(n − 1) для чётного n и K(n) = K(n − 1) + K((n − 1) / 2) для нечётного.
В 7 ведут «+1» из 6 и «2x + 1» из 3: K(7) = 3 + 2 = 5. В 13 — из 12 и из 6: K(13) = 10 + 3 = 13. В 8 «2x + 1» не ведёт, поэтому K(8) = K(7) = 5.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(2 * x + 1, y) print(f(1, 13))Цифра справа и квадрат
Из какого числа команда «дописать справа 4» могла получить 154? А 153?
Дописать цифру d — значит получить 10x + d. Поэтому в n эта команда ведёт, только если n оканчивается на d. 154 получено из 15, а 153 этой командой получить нельзя. Не ищи предшественника делением 153 // 10 = 15: команда из 15 даёт 154, а не 153. С командами «+1» и «дописать 4» из 1 в 40 ведут 4 программы.
Квадрат даёт предшественника только точному квадрату: 16 — из 4, а 18 квадратом не получить. С командами «+1» и «x²» из 2 в 20 ведут 5 программ.
Тонкости:деление и направление
«Разделить на 2, если число чётное» и «разделить на 2 нацело» — разные команды: у результата 3 в первом случае один предшественник (6), во втором два (6 и 7). Подробно — в подтеме 5.
Квадрат увеличивает число только при x ≥ 2: из 1 он снова даёт 1, и программ становится бесконечно много.
Перестановка цифр
Команды «+1» и «поменяй местами две младшие цифры, если цифра десятков меньше цифры единиц». Сколько программ переводят 10 в 24?
Условную команду сначала проверяют по текущему числу: если условие не выполнено, такой ветки нет вовсе. Из 12 перестановка даёт 21, а из 21 её нет: 2 не меньше 1. Перестановка всегда увеличивает число (12 → 21 — на 9), поэтому таблицу, как обычно, заполняют по возрастанию.
В 10 и 11 перестановка запрещена, из 12 даёт 21, из 13–19 — числа 31 и больше, из 20–22 запрещена, из 23 — 32. Значит, программ две: четырнадцать «+1» или 12 → 21 и дальше прибавления.
Перестановку проще выполнить вперёд, чем искать предшественника: таблица переносит количество из x в каждый результат команд. Цифра единиц — x % 10, десятков — x // 10 % 10; прибавляет к уже накопленному:
k = [0] * 25k[10] = 1for x in range(10, 25): results = [x + 1] t, u = x // 10 % 10, x % 10 if t < u: results.append(x + 9 * (u - t)) for y in results: if y <= 24: k[y] += k[x]print(k[24])Итого
- Предшественникиз равенства команда(p) = n
- 2x + 1(n − 1) / 2 для нечётного n
- Цифра dn оканчивается на d
- Квадраттолько точный квадрат
- Условнаяне выполнена — ветки нет
- Pythonрезультаты вперёд, k[y] += k[x]
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Команда 2x + 1
Команды «+1» и «получить 2x + 1». Сколько программ переводят 1 в 13, если траектория не содержит 8?
Введите число.
Подсказка
У команды 2x + 1 предшественник (n − 1) / 2 — только для нечётного n.
Решение
K(n) = K(n − 1), а для нечётного n ещё + K((n − 1) / 2). С нулём в 8: K от 1 до 13 — 1, 1, 2, 2, 3, 3, 5, 0, 2, 2, 5, 5, 8.
def f(x, y): if x == 8 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(2 * x + 1, y) print(f(1, 13))Ответ: 8
Команда 3x + 2
Команды «+1» и «получить 3x + 2». Сколько программ переводят 1 в 30?
Введите число.
Подсказка
Предшественник по 3x + 2 — (n − 2) / 3, если делится.
Решение
K(n) = K(n − 1) и ещё K((n − 2) / 3), если n − 2 делится на 3. Таблица от 1 до 30 даёт 17.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(3 * x + 2, y) print(f(1, 30))Ответ: 17
Дописать цифру 4
Команды «+1» и «дописать справа цифру 4». Сколько программ переводят 1 в 40?
Введите число.
Подсказка
Дописать 4 — это x → 10x + 4.
Решение
Дописывание 4 из 1, 2 и 3 даёт 14, 24 и 34, из 4 — уже 44. Программы: только прибавления и по одной через 14, 24, 34 — всего 4.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 10 + 4, y) print(f(1, 40))Ответ: 4
Квадрат
Команды «+1» и «возвести в квадрат». Сколько программ переводят 2 в 20?
Введите число.
Подсказка
Квадрат даёт предшественника только точному квадрату.
Решение
Квадратом из 2, 3, 4 получаются 4, 9, 16. Программы: только прибавления, через 4 (из 2), через 9, через 16 и через 4 и 16 сразу (2 → 4 → 16) — пять.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * x, y) print(f(2, 20))Ответ: 5
Перестановка цифр: из 12 в 45
Команды «+1» и «переставь две младшие цифры, если цифра десятков меньше цифры единиц». Сколько программ переводят 12 в 45?
Введите число.
Подсказка
Перестановка разрешена только при цифре десятков меньше цифры единиц.
Решение
Перестановка увеличивает число на 9(u − t), поэтому считают по возрастанию. С условной перестановкой из 12 в 45 ведут 13 программ.
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(12, 45))Ответ: 13
Перестановка цифр
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1; 2. Поменять местами две младшие цифры числа, если цифра десятков меньше цифры единиц (иначе команда не выполняется). Сколько существует программ, для которых при исходном числе 15 результатом является число 60?
Введите число.
Подсказка
Сначала проверь условие перестановки для текущего числа.
Решение
Из каждого числа с десятками меньше единиц — ещё одна ветка: x + 9(u − t). Таблица от 15 до 60 даёт 14 программ.
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(15, 60))Ответ: 14
Из 101 в 135
Исполнитель преобразует число на экране. Команды: 1. Прибавить 1; 2. Поменять местами две младшие цифры числа, если цифра десятков меньше цифры единиц (иначе команда не выполняется). Сколько существует программ, для которых при исходном числе 101 результатом является число 135?
Введите число.
Подсказка
Меняются только две младшие цифры, сотни остаются.
Решение
Цифры десятков и единиц у 101–135 те же, что у 1–35, а сотня не меняется. Таблица от 101 до 135 даёт 13 программ.
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(101, 135))Ответ: 13