Подтема 2 из 7
Таблица количества программ
Как посчитать программы без дерева: таблица K от старта к цели — вручную и на Python.
Сумма по последней команде
Сколько программ переводят 6 в 20 — второй участок задачи темы? Дерево здесь уже слишком большое, поэтому считаем таблицей K.
Начнём с одного числа — 12. Любая программа, которая заканчивается в 12, сделала последнюю команду:
- либо «+1» — тогда перед ней на экране было 11;
- либо «×2» — тогда перед ней было 6.
Значит, K(12) = K(11) + K(6): программ в 12 столько, сколько в 11 и в 6 вместе. Ни одна программа не посчитается дважды — последняя команда у неё одна.
С любым числом n так же: «+1» ведёт в него из n − 1 всегда, а «×2» — из n / 2, только если n чётное. Нечётное число умножением на 2 не получить.
| Число n | Количество K(n) |
|---|---|
| нечётное | K(n) = K(n − 1) |
| чётное | K(n) = K(n − 1) + K(n / 2) |
Остаётся старт: K(6) = 1. Мы уже стоим в 6, и туда ведёт одна программа — пустая, без команд. Числа меньше 6 получить нельзя, для них K = 0.
Таблица
Таблицу заполняют по порядку, от старта к цели, — так оба слагаемых для очередного числа уже готовы. Посмотри по шагам, как заполняется таблица от 6 до 20: оранжевая рамка — текущее число, обведены клетки, которые складывают.
- K(6) = 1: в старте одна пустая программа.
- K(7) = K(6) = 1: в 7 ведёт только «+1».
- K(8) = K(7) = 1: в 8 ведёт только «+1».
- K(9) = K(8) = 1: в 9 ведёт только «+1».
- K(10) = K(9) = 1: в 10 ведёт только «+1».
- K(11) = K(10) = 1: в 11 ведёт только «+1».
- K(12) = K(6) + K(11) = 1 + 1 = 2.
- K(13) = K(12) = 2: в 13 ведёт только «+1».
- K(14) = K(7) + K(13) = 1 + 2 = 3.
- K(15) = K(14) = 3: в 15 ведёт только «+1».
- K(16) = K(8) + K(15) = 1 + 3 = 4.
- K(17) = K(16) = 4: в 17 ведёт только «+1».
- K(18) = K(9) + K(17) = 1 + 4 = 5.
- K(19) = K(18) = 5: в 19 ведёт только «+1».
- K(20) = K(10) + K(19) = 1 + 5 = 6.
От 7 до 11 в каждое число ведёт только «+1» — по одной программе. В 12 приходят из 11 и из 6: 1 + 1 = 2. В 20 — из 19 и из 10: 5 + 1 = 6. Ответ второго участка: 6 программ.
Таблица в коде — : номер ячейки — число на экране, значение — количество программ. Ячейки ниже старта остаются нулевыми и ничего не добавляют:
k = [0] * 21k[6] = 1for n in range(7, 21): k[n] = k[n - 1] if n % 2 == 0: k[n] += k[n // 2]print(k[20])n % 2 == 0 — проверка чётности: в нечётное n команда «×2» не ведёт, и округлять n / 2 нельзя.
Три команды
Команды «+1», «+2» и «×2». Сколько программ переводят 1 в 10?
Каждая команда даёт своё слагаемое — даже если две команды ведут в n из одного и того же числа. В n ведут «+1» из n − 1, «+2» из n − 2 и «×2» из n / 2, если n чётное. В 4 ведут и «+2», и «×2» — обе из 2, поэтому K(2) входит в сумму дважды: это разные программы.
| n | Слагаемые | K(n) |
|---|---|---|
| 1 | старт | 1 |
| 2 | K(1) + K(1) | 2 |
| 3 | K(2) + K(1) | 3 |
| 4 | K(3) + K(2) + K(2) | 7 |
| 5 | K(4) + K(3) | 10 |
| 6 | K(5) + K(4) + K(3) | 20 |
| 7 | K(6) + K(5) | 30 |
| 8 | K(7) + K(6) + K(4) | 57 |
| 9 | K(8) + K(7) | 87 |
| 10 | K(9) + K(8) + K(5) | 154 |
Ответ 154. Если в 4 взять K(2) один раз, получится 5 вместо 7 — и всё дальше будет занижено.
Недостижимые числа
Команды «+2» и «×3», старт 2. Сколько программ ведут в 13?
Иногда ответ 0 виден сразу: если каждая команда сохраняет какое-то свойство числа — например, чётность. 2 чётное; чётное + 2 — снова чётное, чётное · 3 — тоже. На экране всегда чётные числа, и 13 не появится: ответ 0.
Из 1 те же команды дают только нечётные числа, и в 15 ведут 6 программ.
Итого
- K(n)сумма по командам, ведущим в n
- СтартK = 1: одна пустая программа
- Порядокот старта к цели
- ×2только для чётного n, без округления
- Две команды из одного числадва разных слагаемых
- Python
k[n] = k[n - 1] + k[n // 2]
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Таблица от 2 до 8
Команды «+1» и «×2». Сколько программ переводят 2 в 8?
Введите число.
Подсказка
K(n) = K(n − 1), а для чётного n ещё + K(n / 2).
Решение
Таблица от 2: K = 1, 1, 2, 2, 3, 3, 5 для чисел от 2 до 8. В 8 ведут 7 (3 программы) и 4 (2 программы): 3 + 2 = 5.
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, 8))Ответ: 5
Таблица до 16
Команды «+1» и «×2». Сколько программ переводят 1 в 16?
Введите число.
Подсказка
Нечётное число получает столько же программ, сколько предыдущее.
Решение
У нечётного n только вклад «+1», поэтому K(n) = K(n − 1), и значения идут парами: 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36.
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(1, 16))Ответ: 36
Из 3 в 25: +1 и ×3
Команды «+1» и «×3». Сколько программ переводят 3 в 25?
Введите число.
Подсказка
Умножение на 3 работает только для n, кратного 3.
Решение
K(n) = K(n − 1), а для n, кратного 3, ещё + K(n / 3). Умножать можно из 3–8; таблица до 25 даёт 7 программ.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 3, y) print(f(3, 25))Ответ: 7
Из 3 в 20
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1; 2. Умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20?
Введите число.
Подсказка
Заполни таблицу K(n) от 3 до 20.
Решение
Таблица от K(3) = 1: в каждое чётное n добавляется K(n / 2). K(20) = K(19) + K(10) = 14 + 4 = 18.
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, 20))Ответ: 18
Присваивание вместо прибавления
В табличной программе вместо прибавления += написали присваивание =. Что выведет программа?
def count(start, finish): dp = [0] * (finish + 1) dp[start] = 1 for x in range(start, finish + 1): for y in (x + 1, x * 2): if y <= finish: dp[y] = dp[x] return dp[finish] print(count(2, 12))Введите число.
Подсказка
Каждое присваивание стирает то, что пришло в ячейку раньше.
Решение
Присваивание оставляет в ячейке только последний вклад: в 12 последним приходит dp[11], а туда — dp[10] и так далее, и всё сводится к 1. С += ответ был бы 10.
def count(start, finish): dp = [0] * (finish + 1) dp[start] = 1 for x in range(start, finish + 1): for y in (x + 1, x * 2): if y <= finish: dp[y] = dp[x] return dp[finish] print(count(2, 12))Ответ: 1
Три команды: из 1 в 9
Команды «+1», «+2» и «×2». Сколько программ переводят 1 в 9?
Введите число.
Подсказка
Из 1 в 2 ведут две программы: «+1» и «×2».
Решение
K(n) = K(n − 1) + K(n − 2) и ещё K(n / 2) для чётного n. Значения от 1 до 9: 1, 2, 3, 7, 10, 20, 30, 57, 87. В 4 и «+2», и «×2» ведут из 2 — это два разных вклада.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 2, y) + f(x * 2, y) print(f(1, 9))Ответ: 87
Из 2 в 14: три команды
Исполнитель преобразует число на экране. У исполнителя есть три команды: 1. Прибавить 1; 2. Прибавить 2; 3. Умножить на 3. Сколько существует программ, для которых при исходном числе 2 результатом является число 14?
Введите число.
Подсказка
Слагаемых три: из n − 1, из n − 2 и из n / 3 для кратного 3 числа.
Решение
K(n) = K(n − 1) + K(n − 2) и ещё K(n / 3), если n делится на 3. Таблица от K(2) = 1 до 14 даёт 279.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 2, y) + f(x * 3, y) print(f(2, 14))Ответ: 279
Три команды: из 1 в 10
Команды «+1», «+2» и «×2». Сколько программ переводят 1 в 10?
Введите число.
Подсказка
Три слагаемых: n − 1, n − 2 и n / 2 для чётного n.
Решение
Значения от 1 до 10: 1, 2, 3, 7, 10, 20, 30, 57, 87, 154. Ячейка k[0] остаётся нулевой, поэтому при n = 2 вклад k[0] равен 0.
k = [0] * 11k[1] = 1for n in range(2, 11): k[n] = k[n - 1] + k[n - 2] if n % 2 == 0: k[n] += k[n // 2]print(k[10])Ответ: 154
Из 2 в 13: чётность
Команды «+2» и «×3». Сколько программ переводят 2 в 13?
Введите число.
Подсказка
Посмотри на чётность чисел, которые можно получить из 2.
Решение
Из чётного числа обе команды дают чётное: 2 + 2 и 2 · 3 — чётные. Значит, 13 получить нельзя, программ 0.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 2, y) + f(x * 3, y) print(f(2, 13))Ответ: 0