Сложная задача по информатике У исполнителя Увеличитель две команды, которым присвоены номера:

1. прибавь 1
,

2. возведи в квадрат.

Первая из них увеличивает число на экране на 1
, вторая заменяет число на экране его квадратом.

Программа для Увеличителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2
результатом является число 107
и при этом траектория вычислений не содержит число 26
?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121
при исходном числе 5
траектория будет состоять из чисел 6,36,37
.

Выберите один или несколько ответов:

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом динамического программирования. Подсчитаем количество программ для каждого числа от 2 до 107, исключая число 26. Для этого будем последовательно применять к каждому числу команды "прибавь 1" и "возведи в квадрат", и только в том случае, если результат не равен 26.

Начнем с числа 2. Для него есть две программы: "прибавь 1" и "прибавь 1" (результат 4) и "возведи в квадрат" (результат 4). Таким образом, для числа 2 есть две программы.

Далее будем идти по возможным путям увеличения числа, и на каждом шаге проверять, не является ли число равным 26. Если число равно 107 и при этом не равно 26, то добавляем эту программу в общий счетчик.

Таким образом, нужно построить все возможные программы для числа 2, 3, 4, ..., 107, исключая программы, которые содержат число 26. После этого подсчитать общее количество программ.

Получится вариантов программ не очень много, т.к. решение можно найти методом пристального взгляда без необходимости написания кода.