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