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

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

Задача 1#25996

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

Вычесть $1$
Вычесть $3$
Взять остаток от деления на $4$

Команда $3$ выполняется только для чисел, больших, чем $4$ . Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число $22$ преобразуют в число $2$ ?

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

a = [0]*23
a[22] = 1
for i in reversed(range(2, 23)):
    a[i-1] += a[i]
    a[i-3] += a[i]
    if i > 4:
        a[i % 4] += a[i]
print(a[2])

Ответ: 1873

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

Задача 2#26075

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

Вычесть $1$ ;
Вычесть $3$ ;
Разделить нацело на $3$ .

При выполнении команды $3$ выполняется деление нацело (остаток отбрасывается). Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число $22$ преобразуют в число $2$ ?

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

Решение 1 (Динамика)

a = [0] * 70
a[22] = 1
for i in range(21, 1, -1):
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
print(a[2])

Решение 2 (Рекурсия)

def f(a, b):
    if a == b:
        return 1
    if a < b:
        return 0
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

print(f(22, 2))

Решение 3 (Динамика)

a = [0] * 23
a[22] = 1
for i in range(22, 2, -1):
    a[i // 3] += a[i]
    a[i - 3] += a[i]
    a[i - 1] += a[i]
print(a[2])

Ответ: 2196

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

Задача 3#26129

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

1. Разделить на $2$ с округлением вниз (выполнить целочисленное деление на $2$ )

2. Вычесть $1$

Первая команда уменьшает число на экране в $2$ раза, вторая — уменьшает его на $1$ . Программа для исполнителя — это последовательность команд.

Определите количество программ, которые число $64$ преобразуют в число $14$ .

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

Решение 1 (Рекурсия)

def f(a, b):
    if a == b:
        return 1
    if a < b:
        return 0
    if a > 1:
        return f(a // 2, b) + f(a - 1, b)
    return f(a - 1, b)

print(f(64, 14))

Решение 2 (Динамика)

a = [0] * 65
a[64] = 1
for i in range(64, 14, -1):
    a[i // 2] += a[i]
    a[i - 1] += a[i]
print(a[14])

Ответ: 63

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

Задача 4#26210

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

1. Вычесть 1

2. Вычесть 3

3. Взять остаток от деления на 4

Команда 3 выполняется только для чисел, больших, чем 4. Программа для исполнителя — это последовательность команд.

Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

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

a = [0]*25
a[22] = 1
for i in reversed(range(2, 22)):
    a[i] = a[i+1] + a[i+3]
    if i < 4:
        for j in range(i+4, 23, 4):
            a[i] += a[j]
print(a[2])

Ответ: 1873

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

Задача 5#30471

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

Вычесть $3$
Поделить на $3$ , если число кратно $3$
Поделить на $2$ , если число кратно $2$

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числe $30$ результатом является число $3$ ?

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

Решение 1 (Рекурсия)

def f(st, fn):
    if st == fn:
        return 1
    if st < fn:
        return 0
    x = f(st // 3, fn) * (st % 3 == 0)
    y = f(st // 2, fn) * (st % 2 == 0)
    z = f(st - 3, fn)
    return x + y + z
print(f(30, 3))

Решение 2 (Динамика)

a = [0] * 31
a[30] = 1
for i in range(30, 1, - 1):
    a[i - 3] += a[i]
    a[i // 2] += a[i] * (i % 2 == 0)
    a[i // 3] += a[i] * (i % 3 == 0)
print(a[3])

Решение 3 (Динамика)

a = [0] * 100
a[30] = 1
for i in range(29, 2, -1):
    a[i] = a[i + 3] + a[i * 3] + a[i * 2]
print(a[3])

Ответ: 23

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

Задача 6#52529

Исполнитель Бот решил сыграть в игру. Он преобразовывает числа на доске с помощью трёх команд:

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 25 в число 3?

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

a = [0] * 1000
a[25] = 1
for i in range(24, 2, -1):
    a[i] = a[i + 2] + a[i + 3] + a[i ** 2]
print(a[3])

Ответ: 238

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

Задача 7#57112

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

А. Вычти 3

Б. Вычти 5

В. Найди целую часть от деления на 3

Первая из них уменьшает число на экране на 3, вторая уменьшает число на экране на 5, третья заменяет число на экране на целую часть от деления числа на 3. Программа для исполнителя — это последовательность команд.

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

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

a = [0] * 1000
a[68] = 1
for i in range(68, 3, -1):
    if i == 14 or i == 35:
        for j in range(i):
            a[j] = 0
    a[i - 3] += a[i]
    a[i - 5] += a[i]
    a[i // 3] += a[i]
print(a[4])

Ответ: 2024

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

Задача 8#63351

Исполнитель решил сыграть в игру. Он преобразовывает числа на доске с помощью трёх команд:

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя - это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 25 в число 3?

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

def F(x, y):
    if x == y:
        return 1
    if x < y:
        return 0
    if x > y:
        return F(x - 2, y) + F(x - 3, y) + (F(pow(x, 0.5), y) if x >= 0 else 0)

print(F(25, 3))

Ответ: 238

23.02 Количество программ из A в B (на убывание)