Умение анализировать ход исполнения алгоритма · 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 Первая к…
Анализ алгоритмов и исполнители
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А) Прибавить 2
В) Умножить на 2
С) Умножить на 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья умножает его на 3.
Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 28 и при этом траектория вычислений программы содержит число 6?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы АСВ при исходном числе 4 траектория будет состоять из чисел 6, 18, 36.
Правильный ответ
30
Пояснение
Решение:
Все три команды увеличивают число, поэтому траектория строго возрастает и число 6 может встретиться в ней не больше одного раза. Значит, любая подходящая программа однозначно разбивается на две части: сначала она переводит 2 в 6, а потом 6 в 28. По правилу умножения общее количество программ равно произведению количеств программ на каждом участке.
Участок 2→6 даёт три программы: АА (2 → 4 → 6), ВА (2 → 4 → 6) и С (2 → 6). Участок 6→28 удобно посчитать той же рекурсией: обозначим через R(a,b) число программ, переводящих a в b; тогда R(b,b)=1, R(a,b)=0 при a>b и R(a,b)=R(a+2,b)+R(2a,b)+R(3a,b) в остальных случаях. Получаем R(6,28)=10.
Итого 3⋅10=30 программ. Для сравнения, всего программ из 2 в 28 без условия про шестёрку было бы 48, так что требование пройти через 6 действительно отсекает часть вариантов.
from functools import lru_cache
@lru_cache(None)
def R(a, b):
if a > b:
return 0
if a == b:
return 1
return R(a + 2, b) + R(2 * a, b) + R(3 * a, b)
print(R(2, 6) * R(6, 28)) # 3 * 10 = 30
Ответ: 30