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

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
А) Прибавить 2
В) Прибавить 10
Первая команда увеличивает число на экране на 2, вторая увеличивает это число на 10. Программа для исполнителя - это последовательность команд. Сколько существует программ, которые число 7 преобразуют в число 71?

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

4085

Пояснение

Решение:

Команда А увеличивает число на $2$ , команда В — на $10$ ; порядок команд на итоговое число не влияет, важно лишь, сколько раз использована каждая. Всего надо прибавить $71 - 7 = 64$ . Если команда А использована $n$ раз, а команда В — $k$ раз, то

$2 n + 10 k = 64.$

Отсюда подходят только $k = 0, 1, 2, 3, 4, 5, 6$ (при остальных $k$ остаток $64 - 10k$ не делится на $2$ нацело или отрицателен).

Программа — это последовательность команд, поэтому при фиксированных $n$ и $k$ количество программ равно числу способов расставить $k$ команд В среди всех $n + k$ команд, то есть $C_{n+k}^{\,k}$ .

$k$ — команд В	$n$ — команд А	Количество программ $C_{n+k}^{\,k}$
0	32	$C_{32}^{0} = 1$
1	27	$C_{28}^{1} = 28$
2	22	$C_{24}^{2} = 276$
3	17	$C_{20}^{3} = 1140$
4	12	$C_{16}^{4} = 1820$
5	7	$C_{12}^{5} = 792$
6	2	$C_{8}^{6} = 28$

Складываем: $1 + 28 + 276 + 1140 + 1820 + 792 + 28 = 4085$ .

Тот же результат даёт короткая программа:

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

print(f(7, 71))

Ответ: 4085