Задание 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 — Поиск количества программ

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А) Прибавить 3
В) Прибавить 4
С) Умножить на 3
Первая из них увеличивает число на экране на 3, вторая увеличивает его на 4, третья умножает его на 3.
Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 1 в число 30 и при этом траектория вычислений программы содержит число 7?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы АСВ при исходном числе 2 траектория будет состоять из чисел 5, 15, 19.

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

Пояснение

Решение:

Все команды только увеличивают число на экране, поэтому траектория строго возрастает и ни одно число не может встретиться в ней дважды.

Траектория обязана содержать число $7$ , поэтому каждая подходящая программа однозначно распадается на две части: $1 \to 7$ и $7 \to 30$ . По правилу умножения ответ равен произведению количеств программ для этих участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$ : $f(x, x) = 1$ (пустая программа), $f(x, y) = 0$ при $x \gt y$ (число уже «перескочило» цель, а уменьшать команды не умеют). В остальных случаях перебираем первую команду («прибавить 3», «прибавить 4» или «умножить на 3»):

$f(x, y) = f(x + 3,\, y) + f(x + 4,\, y) + f(3x,\, y).$

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 + 3, x + 4, x * 3):
        s += f(z, y)
    return s

print(f(1, 7) * f(7, 30))

Получаем

f(1, 7) = 2

f(7, 30) = 29

, то есть всего

2 \cdot 29 = 58

программ. Ответ: 58