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

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

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

1760

Пояснение

Решение:

Обе команды только уменьшают число на экране, поэтому траектория строго убывает и одно и то же число не может встретиться в ней дважды. Значит, каждая подходящая программа однозначно разбивается на две независимые части: сначала число $60$ превращается в $20$ , затем $20$ превращается в $1$ . По правилу умножения искомое количество равно произведению количеств программ для этих двух участков.

Пусть $f(x, y)$ — количество программ, переводящих $x$ в $y$ . Если $x = y$ , подходит только пустая программа, то есть $f(x, x) = 1$ ; если $x \lt y$ , то $f(x, y) = 0$ — увеличивать число команды не умеют. Иначе первая команда переводит $x$ либо в $x - 1$ , либо в $\left\lfloor x/2 \right\rfloor$ , поэтому

$f(x, y) = f(x - 1,\, y) + f\big(\left\lfloor x/2 \right\rfloor,\, y\big).$

Число $4$ в траектории появляться не должно, поэтому переход в него просто запрещаем — соответствующее слагаемое не учитываем.

from functools import lru_cache

@lru_cache(None)
def f(x, y):          # сколько программ переводят x в y, минуя число 4
    if x == y:
        return 1
    if x < y:
        return 0
    s = 0
    for z in (x - 1, x // 2):
        if z != 4:
            s += f(z, y)
    return s

print(f(60, 20) * f(20, 1))

Получаем

f(60, 20) = 22

f(20, 1) = 80

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

22 \cdot 80 = 1760

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