Умение анализировать ход исполнения алгоритма · 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 Первая к…
Анализ алгоритмов и исполнители
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Прибавить 1
В. Прибавить 4
С. Умножить на 2
Программа для исполнителя - это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 24, при этом траектория вычислений не содержит числа 11 и не содержит числа 17? Траектория вычислений программы - это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 7 траектория будет состоять из чисел 14, 18, 19.
Правильный ответ
298
Пояснение
Решение:
Все команды только увеличивают число на экране, поэтому траектория строго возрастает и ни одно число не может встретиться в ней дважды.
Пусть f(x,y) — количество программ, переводящих x в y: f(x,x)=1 (пустая программа), f(x,y)=0 при x>y (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 1», «прибавить 4» или «умножить на 2»):
f(x,y)=f(x+1,y)+f(x+4,y)+f(2x,y).
Числа 11 и 17 траектория содержать не должна, поэтому переходы в них запрещаем — соответствующие слагаемые отбрасываем.
from functools import lru_cache
@lru_cache(None)
def f(x, y): # сколько программ переводят число x в число y
if x == y:
return 1
if x > y:
return 0 # перескочили - назад команд нет
s = 0
for z in (x + 1, x + 4, x * 2):
if z not in (11, 17):
s += f(z, y)
return s
print(f(3, 24))
Программа выводит 298.
Ответ: 298