Задание 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
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 60 результатом является число 2, и при этом траектория вычислений содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы АВВ при исходном числе 10 траектория состоит из чисел 9, 4, 2.

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

1956

Пояснение

Решение:

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

Пусть $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).$

from functools import lru_cache

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

print(f(60, 10) * f(10, 2))

Получаем

f(60, 10) = 163

f(10, 2) = 12

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

163 \cdot 12 = 1956

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