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

Рассмотрим обратный процесс – сколько существует программ (последовательностей команд), преобразующих число 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, н...