Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды: Прибавь 1 Умножь на 2 Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является

6 ноября 2025
Программирование

Условие:

Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды:

Прибавь 1

Умножь на 2

Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является число 18?

Решение:

Рассмотрим обратный процесс – сколько существует программ (последовательностей команд), преобразующих число 5 в число 18, используя только команды «Прибавь 1» и «Умножь на 2». Обозначим через f(n) число программ, переводящих 5 в n. Базис: f(5)=1 (начальное число). Заметим, что любая команда увеличивает число, поэтому можно строить f(n) для n5 по рекуррентной схеме: f(n) = f(n-1) + (если n чётное, то f(n/2), если n/2 ≥ 5). Пошагово вычислим: 1. n = 6. Команды: 6 получается прибавлением единицы к 5. Если попытаться получить 6 умножением на 2, то требуется, чтобы предыдущим числом было 3, н...