Задание 13

Умение анализировать ход исполнения алгоритма · 26 заданий

Задание №13
№13
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A) Прибавить 1 B) Прибавит…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: 1) Прибавить 1 2) Умножить на 2 Програ…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1) Прибавить 1 2) Умножить на 2 Первая команда увел…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: А) Прибавить 5 В) Прибавить 4 С) Умнож…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: А) Прибавить 3 В) Прибавить 4 С) Умнож…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: А) Прибавить 2 В) Умножить на 2 С) Умн…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Вычти 1 В) Найди целую часть от дел…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: А) Прибавить 2 В) Умножить на 2 С) Умн…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Вычти 1 В) Найди целую часть от дел…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Прибавить 2 В) Прибавить 10 Первая…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Прибавить 2 В) Прибавить 10 Первая…
Анализ алгоритмов и исполнители
Задание №13
№13
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Прибавить 2 В) Прибавить 7 Первая к…
Анализ алгоритмов и исполнители

Задание №13 — Поиск количества программ

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.

Правильный ответ

Пояснение

Решение:

Все три команды строго увеличивают число (при исходном числе 2 прибавление единицы, удвоение и возведение в квадрат дают большее число), поэтому траектория растёт и «перепрыгнуть» цель, а потом вернуться к ней невозможно. Значит, количество программ удобно считать рекурсивно с конца.

Обозначим через $R(a)$ число программ, переводящих $a$ в 20 так, чтобы дальше по траектории не встретилось 11. Тогда $R(20) = 1$ (пустая программа), $R(a) = 0$ при $a \gt 20$ (цель проскочена) и $R(11) = 0$ — запрещённое число обнуляет весь путь, ведь если траектория попала в 11, программа уже не годится. В остальных случаях первый шаг делается одной из трёх команд, и варианты складываются: $R(a) = R(a + 1) + R(2a) + R(a^2)$ .

Считая от больших чисел к меньшим (или просто с кэшированием), получаем $R(2) = 37$ . Запрет на 11 существенно режет перебор: например, ветка $10 \to 11$ полностью отбрасывается, и из 10 в 20 остаётся только удвоение.

from functools import lru_cache

@lru_cache(None)
def R(a):
    if a == 11 or a > 20:
        return 0
    if a == 20:
        return 1
    return R(a + 1) + R(2 * a) + R(a * a)

print(R(2))   # 37

Ответ: 37