Количество программ из A в B (Не проходящие через число) —Каталог задач по ЕГЭ - Информатика

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

Тема 23. Линейные программы и ветвление

23.05 Количество программ из A в B (Не проходящие через число)

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

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

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

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

Подтемы раздела линейные программы и ветвление

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

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

Задача 1#30473

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

Прибавить $2$
Умножить на $3$
Прибавить остаток от деления на $2$ и прибавить $2$

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

Сколько существует программ, для которых при исходном числe $1$ результатом является число $15$ , при этом траектория вычислений не содержит числа $13$ .

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $6$ траектория будет состоять из чисел $8$ , $24$ , $26$ .

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

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

def f(st, fn, exit_number):
    if st == fn:
        return 1
    if st > fn or st == exit_number:
        return 0
    x = f(st + 2, fn, exit_number)
    y = f(st * 3, fn, exit_number)
    z = f(st + st % 2 + 2, fn, exit_number)
    return x + y + z
print(f(1, 15, 13))

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

a = [0] * 16 * 3
a[1] = 1
for i in range(1, 15):
    if i != 13:
        a[i + 2] += a[i]
        a[i * 3] += a[i]
        a[i + i % 2 + 2] += a[i]
print(a[15])

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

a = [0] * 16
a[1] = 1
# 2 -> 2 + 0 + 2 = 4
# 1 -> 1 + 1 + 2 = 4
for i in range(2, 16):
    a[13] = 0
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0) + (a[i - 2] + a[i - 2 - 1]) * (i % 2 == 0)
print(a[15])

Ответ: 2

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

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

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

Задача 2#26985

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

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

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

Сколько существует программ, которые преобразуют исходное число 2 в число 20 и при этом траектория вычислений не содержит чисел 7 и 15?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

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

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

def f(a, b):
    if a == b:
        return 1
    if a > b or a == 7 or a == 15:
        return 0
    return f(a + 1, b) + f(a * 2, b) + f(a + 3, b)


print(f(2, 20))

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

a = [0] * 21
a[2] = 1
for i in range(3, 21):
    if i == 7 or i == 15:
        continue
    if i % 2 == 0:
        a[i] += a[i // 2]
    a[i] += a[i - 3]
    a[i] += a[i - 1]
print(a[20])

Ответ: 304

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

Задача 3#25915

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

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

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

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

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

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

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

def f(start, finish):
    if start == finish:
        return 1
    if start > finish or start == 8:
        return 0
    return f(start + 1, finish) + f(start + 2, finish) + f(start * 2, finish)
print(f(3, 13))

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

a = [0] * 14
a[3] = 1
for i in range(4, 14):
    if i == 8:
        continue
    a[i] += a[i - 1]
    a[i] += a[i - 2]
    if i % 2 == 0:
        a[i] += a[i // 2]
print(a[13])

Ответ: 40

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

Задача 4#25567

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

Прибавить $1$ ;
Прибавить $3$ ;
Умножить на $2$ ;
Умножить на $3$ .

Первая команда увеличивает число, записанное на экране, на $1$ , вторая — на $3$ , третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя ЭМИ — это последовательность команд. Сколько существует программ, для которых при исходном числе $3$ результатом является число $45$ и при этом траектория вычисления не содержит числа $5,17$ и $35$ ?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы $1314$ при исходном числе $7$ траектория будет состоять из чисел $8,16,17,51$ .

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

a = [0]*46
a[3] = 1
for i in range(4, 46):
    a[i] = a[i-1]+a[i-3]
    if i % 2 == 0:
        a[i] += a[i//2]
    if i % 3 == 0:
        a[i] += a[i//3]
    if i == 5 or i == 17 or i == 35:
        a[i] = 0
print(a[45])

Ответ: 1278967

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

Задача 5#25108

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

Прибавить $1$ ;
Сделай нечётное.

Выполняя первую команду, исполнитель увеличивает число на $1$ , а выполняя вторую — из числа $k$ получает число $2k + 1$ .

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

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

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

def f(s, fi):
    if s > fi:
        return 0
    if s == 21:
        return 0
    if s == fi:
        return 1
    return f(s + 1, fi) + f(s * 2 + 1, fi)
print(f(1, 25))

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

a = [0] * 26
a[1] = 1
for i in range(2, 26):
    a[i] += a[i - 1]
    if i % 2 != 0:
        a[i] += a[i // 2]
    if i == 21:
        a[i] = 0
print(a[25])

Ответ: 20

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

Задача 6#22659

Исполнитель КУРАТОР преобразует число, записанное на экране.

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 33 результатом является число 72 и при этом траектория не содержит число 56? Траектория вычислений программы $−$ это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 1 траектория будет состоять из чисел 2, 6, 12.

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

a = [0] * 10000
a[33] = 1
for i in range(33, 73):
    a[56] = 0
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]
print(a[72])

Ответ: 71265

Курсы

Всё необходимое для достижения цели

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

Задача 7#16526

Исполнитель ЗВЕЗДОЧКА преобразует число, записанное на экране.

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

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

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

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

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

Сколько существует программ, для которых при исходном числе $33$ результатом является число $72$ и при этом траектория не содержит число $30$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $2,6,12$ .

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

num = [0]*73
num[33] = 1
for i in range(34, 73):
num[i] = ((num[i-1] + num[i-4]) + num[i//2] * (i % 2 == 0)) * (i != 30)
print(num[72])

Ответ: 157430

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

Задача 8#11532

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

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

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

Первая из этих команд увеличивает число $x$ на экране на $1$ , вторая переводит число $x$ в число $2x + 1$ . Например, вторая команда переводит число $10$ в число $21$ . Программа для исполнителя ГО – это последовательность команд. Сколько существует таких программ, которые число $1$ преобразуют в число $27$ , причём траектория вычислений не содержит число $26$ ? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

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

a = [0]*28
a[1] = 1
for i in range(2,28):
    a[i] = a[i-1]
    if i%2==1:
        a[i] += a[i//2]
    if i==26:
        a[i]=0
print(a[27])

Ответ: 13

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

Задача 9#6834

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

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

Прибавить $1$
Умножить на $2$

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

Сколько существует программ, для которых при исходном числе $1$ результатом является число $19$ и при этом траектория вычислений не содержит число $14$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $7$ траектория будет состоять из чисел $8$ , $16$ , $17$ .

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

Решение 1

a = [0] * 20
a[1] = 1
for i in range(2, 20):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0)
    if i == 14:
        a[i] = 0
print(a[19])

Решение 2

a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14:
        a[i] = 0
    a[i + 1] += a[i]
    a[i * 2] += a[i]
print(a[19])

Решение 3 Пусть $R(n)$ — количество программ, которые число 1 преобразуют в число $n$ . Тогда верно следующее утверждение:

$R(n ) = R (n − 1) + R (n : 2)$

Заполним таблицу по данной формуле до 13:

|1--|2-|3-|4-|5-|6-|7-|-8-|-9--|10-|11-|12-|13-| |---|--|--|--|--|--|--|---|----|---|---|---|---| -1---2--2--4--4--6--6--10--10---14--14--20--20--

Так как по условию сказано, что траектория не должна проходить через число 14, значит мы никак не можем его получить, что означает $R(14) = 0$ .

Заполним таблицу до конца:

|--|--|--|--|--|--|---|---|---|---|---|----|---|---|---|---|----|---|---| |1-|2-|3-|4-|5-|6-|7--|8--|9--|10-|11-|12--|13-|14-|15-|16-|-17-|18-|19-| -1--2--2--4--4--6--6---10--10--14--14--20---20--0----0--10---10--20--20--

Отсюда получаем ответ — 20.

Ответ: 20

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

Задача 10#6054

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

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

Прибавить $3$
Прибавить $4$
Умножить на $2$

Первая команда увеличивает число на экране на $3$ , вторая — на $4$ , третья — удваивает число. Программа для исполнителя Пирожок — это последовательность команд.

Сколько существует программ, для которых при исходном числе $256$ результатом является число $273$ и при этом траектория вычислений не содержит числа $262$ и $270$ ? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $7$ траектория будет состоять из чисел $10$ , $14$ , $17$ .

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

Решение 1

a = [0] * 274
a[256] = 1
for i in range(257, 274):
    a[i] = a[i - 3] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    if i == 262 or i == 270:
        a[i] = 0
print(a[273])

Решение 2

Пусть $R(n)$ — количество программ, которое число 1 преобразует в число $n$ . Тогда верно следующее утверждение: