Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика БУ
Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

Тема 23. Оператор присваивания и ветвления

23.04 Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела оператор присваивания и ветвления

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#60492Максимум баллов за задание: 1

Исполнитель Обычный преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 3

Программа для исполнителя Обычный – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 36, и при этом траектория вычислений не содержит число 24?

Показать ответ и решение

Решение рекурсией

Мы решаем задачу рекурсивно, определяя функцию f(n, m), которая подсчитывает количество программ, преобразующих число $n$ в число $m$ . Идея состоит в том, чтобы на каждом шаге проверять текущую позицию и принимать решение:

1. Если текущее число $n$ совпадает с целевым $m$ , то найден корректный путь, и функция возвращает $1$ .

2. Если текущее число $n$ больше $m$ или равно запрещённому числу 24, путь невозможен, возвращаем $0$ .

3. В остальных случаях мы применяем все возможные команды:

- n + 1, что соответствует команде «прибавить 1»;

- n * 3, что соответствует команде «умножить на 3»;

После чего суммируем результаты рекурсивных вызовов для этих двух вариантов.

Таким образом, вызов функции f(3, 36) рекурсивно переберёт все допустимые последовательности команд и вернёт общее количество программ.

# Определяем функцию f(n, m) для подсчета количества программ
def f(n, m):
    # Если текущее число совпало с целевым,
    # значит найден корректный путь, возвращаем 1
    if n == m:
        return 1
    # Если текущее число стало больше целевого или равно запрещённому числу 24,
    # путь невозможен, возвращаем 0
    if n > m or n == 24:
        return 0
    # В остальных случаях считаем все возможные варианты:
    # применяем команду +1 и команду *3, складываем количество путей
    return f(n+1, m) + f(n*3, m)

# Запускаем функцию от 3 до 36 и выводим результат
print(f(3, 36))

—

Решение динамикой

Мы можем решить задачу динамически, создав массив a, где индекс соответствует числу, а значение по этому индексу — количество программ, которые приводят к этому числу.

1. Сначала создаём массив длиной 37 (чтобы включить число 36), все элементы равны 0.

2. В ячейку с индексом 3 записываем 1, так как стартуем с числа 3 и существует ровно один способ быть в этом положении.

3. Перебираем числа от 4 до 36. Для каждого числа $i$ :

- Добавляем количество способов из $i− 1$ , так как можно прийти командой «прибавить 1»;

- Если $i$ делится на 3, то добавляем количество способов из $i∕∕3$ , так как можно прийти командой «умножить на 3»;

- Если $i$ равно 24, обнуляем значение, так как траектория не должна содержать это число.

В результате, значение a[36] будет содержать количество всех программ, которые из числа 3 приводят к числу 36 без прохождения через 24.

# Создаем массив для хранения количества программ до каждого числа
a = [0] * 37
# Исходное число 3: только один способ быть в этом положении
a[3] = 1
# Перебираем числа от 4 до 36
for i in range(4, 37):
    # Количество программ, ведущих в i, равно сумме:
    # 1) способов прийти из i-1 командой +1
    # 2) способов прийти из i//3 командой *3, если i делится на 3
    a[i] = a[i - 1] + a[i // 3] * (i % 3 == 0)
    # Пропускаем запрещённое число 24, обнуляем количество программ
    a[24] = 0

# Выводим количество программ, ведущих от 3 к 36
print(a[36])

Ответ: 9

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#63842Максимум баллов за задание: 1

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Сделай нечётное

Выполняя первую команду, исполнитель увеличивает число на 1, а выполняя вторую – из числа x получает число 2x+1. Сколько существует программ, для которых при исходном числе 1 результатом является число 25 и при этом траектория вычислений не содержит число 21?

Показать ответ и решение

Решение рекурсией

Мы используем рекурсивный метод для подсчета всех программ, которые приводят от числа 1 к числу 25, избегая числа 21. Для этого мы определяем функцию f(n, m), которая возвращает количество таких программ. Основная логика функции строится на проверках текущего числа $n$ относительно целевого числа $m$ и запрещённого числа 21:

1. Сначала проверяем, равно ли текущее число $n$ целевому $m$ .

- Если $n == m$ , значит мы нашли корректный путь, поэтому возвращаем 1.

2. Затем проверяем, превысило ли текущее число $n$ целевое $m$ или равно запрещённому числу 21.

- Если $n > m$ или $n == 21$ , путь невозможен, возвращаем 0.

3. Если ни одно из этих условий не выполнено, мы рассматриваем два возможных действия, которые может выполнить исполнитель:

- Выполнить команду "прибавить 1 что соответствует рекурсивному вызову f(n+1, m).

- Выполнить команду "сделай нечётное что соответствует рекурсивному вызову f(n*2 + 1, m).

Мы складываем результаты этих двух рекурсивных вызовов, чтобы получить общее количество программ для текущего числа $n$ . Начальный вызов функции f(1, 25) перебирает все возможные последовательности команд от 1 до 25, соблюдая условие исключения числа 21.

# Определяем рекурсивную функцию f(n, m) для подсчета количества программ
def f(n, m):
    # Если текущее число совпало с целевым, возвращаем 1
    if n == m:
        return 1
    # Если текущее число больше целевого или равно запрещенному числу 21, возвращаем 0
    if n > m or n == 21:
        return 0
    # В остальных случаях считаем количество программ,
    # выполняя каждую из двух возможных команд и суммируя результаты
    return f(n+1, m) + f(n*2 + 1, m)

# Запускаем функцию с начальными числами 1 и 25 и выводим результат
print(f(1, 25))

Ответ: 20

Ошибка.
Попробуйте повторить позже

Задача 23#72479Максимум баллов за задание: 1

Исполнитель Год23 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, для которых при исходном числе 3 результатом является число 40 и при этом траектория вычислений не содержит число 12?

Показать ответ и решение

Решение рекурсией

Мы используем рекурсивный подход для подсчёта количества программ. Сначала определяем функцию f(a, b), которая считает, сколько существует программ, преобразующих число $a$ в число $b$ с учётом всех условий. Внутри функции проверяем следующие условия:

1. Если текущее число $a$ больше целевого числа $b$ или равно запрещённому числу 12, то путь невозможен и возвращаем 0.

2. Если текущее число $a$ совпадает с $b$ , значит мы нашли корректную программу и возвращаем 1.

3. В противном случае считаем все возможные переходы: прибавляем 1, прибавляем 2 или умножаем на 3, вызывая функцию рекурсивно для каждого из вариантов и суммируя результаты.

Таким образом, каждая рекурсивная ветка проверяет корректность траектории и суммирует количество программ для всех допустимых вариантов. Вызов f(3,40) даст итоговое количество программ, которые из числа 3 приводят к числу 40, обходя число 12.

# Импортируем кэш для ускорения рекурсии
from functools import lru_cache

# Применяем кэширование для функции f
@lru_cache(None)
def f(a, b):
    # Если текущее число больше целевого или равно запрещённому 12
    # путь невозможен, возвращаем 0
    if a > b or a == 12:
        return 0
    # Если текущее число совпало с целевым числом
    # найден корректный путь, возвращаем 1
    if a == b:
        return 1
    # В остальных случаях считаем все возможные переходы:
    # прибавить 1, прибавить 2, умножить на 3
    return f(a + 1, b) + f(a + 2, b) + f(a * 3, b)

# Вызываем функцию от 3 до 40 и выводим результат
print(f(3,40))

—

Решение динамикой

Мы используем динамический способ, создавая массив a длиной 41, где индекс соответствует числу на экране, а значение по индексу показывает количество программ, ведущих к этому числу. Изначально заполняем массив нулями, а в ячейку с индексом 3 записываем 1, так как начинаем с числа 3.

Далее для каждого числа $i$ от 4 до 40 включительно выполняем следующие действия:

- Считаем количество программ, которые приходят к $i$ из $i− 1$ командой "прибавить 1".

- Считаем количество программ, которые приходят к $i$ из $i− 2$ командой "прибавить 2".

- Если $i$ делится на 3, считаем количество программ, которые приходят к $i$ из $i∕∕3$ командой "умножить на 3".

- Если $i$ равно 12, принудительно обнуляем количество программ, так как число 12 запрещено в траектории.

После прохода по всем индексам в массиве, итоговое количество программ хранится в a[40].

# Создаем массив из 41 элемента, все значения равны 0
a = [0] * 41
# В ячейку с индексом 3 записываем 1, так как стартуем с числа 3
a[3] = 1
# Перебираем все числа от 4 до 40
for i in range(4, 41):
    # Считаем количество программ из i-1, i-2 и i//3
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Если число равно 12, обнуляем количество программ
    a[12] = 0

# Выводим количество программ, которые ведут от 3 к 40 без числа 12
print(a[40])

Ответ: 11824582

Ошибка.
Попробуйте повторить позже

Задача 24#136554Максимум баллов за задание: 1

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Прибавить 1

B. Умножить на 2

С. Возвести в квадрат

Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.

Показать ответ и решение

Для подсчёта количества программ используем рекурсивную функцию. Аргументы функции $f(a,b)$ обозначают количество способов преобразовать число $a$ в число $b$ при заданных правилах. Если $a > b$ или в процессе получено число $11$ , то таких путей нет. Если $a = b$ , найден один способ. Иначе программа может продолжиться тремя командами: $a+ 1$ , $a∗ 2$ или $a ∗∗2$ . Таким образом, $f(a,b) = f (a + 1,b)+ f (a ∗2,b)$ + f(a**2, b). Общее количество программ результату вызова функции при $a = 2$ и $b = 20$ .

# Рекурсивная функция для подсчета количества программ
def f(a, b):
    # Если текущее число больше целевого или равно 11 — пути нет
    if a > b or a == 11:
        return 0
    # Если достигли целевого числа, найден один путь
    if a == b:
        return 1
    # Иначе продолжаем тремя возможными командами:
    # A: a + 1, B: a * 2
    return f(a + 1, b) + f(a * 2, b) + f(a ** 2, b)


# Количество программ от 1 до 35 через 10, без числа 17
print(f(2, 20))

Ответ: 37