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

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

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

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

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

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

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

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

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

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

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

Задача 1#49387

У исполнителя КРАБИК три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 5

3. умножь на 2

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 5, третья - увеличивает это число в 2 раза.

Программа для КРАБИКА — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16, но не проходят через число 10?

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

def f(x, y):
    if x == y:
        return 1
    if x > y or x==10:
        return 0
    return f(x + 1, y) + f(x + 5, y) + f(2 * x , y)
print(f(2, 16))

Ответ: 40

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

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

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

Задача 2#72479

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a,b):
    if a > b or a == 12:return 0
    if a == b:return 1
    return f(a+1,b)+f(a+2,b)+f(a*3,b)
print(f(3,40))

Ответ: 11824582

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

Задача 3#60492

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

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

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

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

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

def f(n, m):
    if n == m:
        return 1
    if n > m or n == 24:
        return 0
    return f(n+1, m)+f(n*3, m)

print(f(3, 36))

Ответ: 9

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

Задача 4#60489

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

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

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

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

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

def f(n, m):
    if n == m:
        return 1
    if n > m or n == 14:
        return 0
    return f(n+1, m) + f(n*2, m)

print(f(5, 31))

Ответ: 12

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

Задача 5#58501

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

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

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

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

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

a = [0] * 100
a[4] = 1
for i in range(5, 48):
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0)
    a[28] = 0
print(a[47])

Ответ: 11

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

Задача 6#58103

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 30, и при этом траектория вычислений не содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 1 траектория будет состоять из чисел 2, 4, 5.

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

def f(a,b):
    if a > b or a == 8:return 0
    if a == b:return 1
    if a < b:return f(a+1,b)+f(a*2,b)
print(f(1,30))

Ответ: 76

Курсы

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

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

Задача 7#6837

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

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

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

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

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

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

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

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

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

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

$R(n ) = R (n − 1) + R (n − 3)$ — если число не делится ни на 2, ни на 3.

$R(n ) = R (n − 1) + R (n − 3) + R (n : 2)$ — если число делится на 2, но не делится на 3.

$R(n ) = R (n − 1) + R (n − 3) + R (n : 3)$ — если число делится на 3, но не делится на 2.

$R(n ) = R (n − 1) + R (n − 3) + R (n : 2) + R (n : 3)$ — если число делится и на 2, и на 3.

Сразу заметим, что по условию задачи траектория не должна содержать числа 5, 17 и 35. Значит $R (5) = 0$ , $R (17 ) = 0$ и $R (35 ) = 0$ .

Составим таблицу по данным формулам:

|--|--|--|--|--|---|--|---|---|---|----|---|---|----|----|---|----|----|-----|----|----|------| |3-|4-|5-|6-|7-|-8-|9-|10-|11-|12-|13--|14-|15-|-16-|17--|18-|19--|-20-|-21--|22--|-23-|--24--| -1--1--0--2--3---4--7--10--14--24--34---51--75--113---0---84--197--207--294---505--712---1034--

|-----|------|-----|------|-----|------|------|-------|------|-------|------|----|------|-------|------|--------| | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | |-----|------|-----|------|-----|------|------|-------|------|-------|------|----|------|-------|------|--------| -1034--1539---2285--3326---4916--7201---10612--15528---22842--33468---48996---0---33576--82572---82769--116379---

|--------|--------|-------|--------|--------|---------| |---40---|--41----|--42---|---43---|--44----|---45----| -199158---281927---398651--597809---880241---1278967--|

Получаем ответ – 1278967.

Ответ: 1278967

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

Задача 8#6836

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

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

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

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

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

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

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

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

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

$R(n ) = R (n − 2) + R (n − 3) + R (n − 5)$

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

|--|--|--|--|--|--|--|--|---|---|---|---| |1-|2-|3-|4-|5-|6-|7-|8-|-9-|10-|11-|12-| -1--0--1--1--1--3--2--5---6--8---14--16--

Так как по условию сказано, что траектория не должна содержать число 13, значит $R (13) = 0$ . Продолжим заполнять таблицу:

|--|--|--|--|---|--|--|--|--|---|---|----|---|---|---|---|----|---| |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 |14 |15 |16 |17 |18 | |1-|0-|1-|1-|1--|3-|2-|5-|6-|-8-|14-|16--|0--|36-|24-|50-|76--|74-| ------------------------------------------------------------------|

Аналогично $R (19) = 0$ . Заполним таблицу до конца:

|1-|2-|3-|4-|5-|6-|7--|8-|9-|10-|11-|12-|13--|14-|15-|16-|17--|18-|19-|-20-|-21--|22--|-23-|-24--|25--| |--|--|--|--|--|--|---|--|--|---|---|---|----|---|---|---|----|---|---|----|-----|----|----|-----|----| -1--0--1--1--1--3--2---5--6--8---14--16---0---36--24--50--76---74--0---174--124---250--372--374---796--

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

Ответ: 796

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

Задача 9#6835

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

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая — на 3, третья — удваивает число на экране. Программа для исполнителя ЭВМ — это последовательность команд.

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

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

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

$R(n ) = R (n − 1) + R (n − 3)$ — если число не делится на 2.

$R(n ) = R (n − 1) + R (n − 3) + R (n : 2)$ — если число делится на 2.

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

|--|--|--|--|--|----|---|---|---|---|----|----|----|-----|----| |1-|2-|3-|4-|5-|-6--|7--|8--|-9-|10-|-11-|12--|-13-|-14--|15--| |1 |2 |2 |5 |7 |11 |16 |28 |39 |62 | 90 |140 |202 |308 |448 | ---------------------------------------------------------------

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

Продолжим заполнять таблицу:

|--|--|--|--|--|----|---|---|---|---|----|----|----|-----|----|---|-----|----|----|------|-----|------| |1-|2-|3-|4-|5-|-6--|7--|8--|-9-|10-|11--|12--|-13-|-14--|15--|16-|-17--|18--|-19-|-20---|-21--|-22---| -1--2--2--5--7--11---16--28--39--62--90---140--202--308---448---0--308---795--795--1165---1960--2845--|

Аналогично $R (23) = 0$ .

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

|-22--|23-|--24--|-25--|-26---|-27--| |-----|---|------|-----|------|-----| -2845---0--2100---4945--5147---7247--

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

Ответ: 7247

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

Задача 10#6833

Исполнитель САЛФЕТОЧКА преобразует число на экране.

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

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя САЛФЕТОЧКА — это последовательность команд.

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

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

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

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

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

|--|--|--|--|--|--|---| |1-|2-|3-|4-|5-|6-|-7-| -1--1--2--3--5--8--13--

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

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

|--|--|--|--|--|--|----|--|---|---|---|----|---|----| |1 |2 |3 |4 |5 |6 | 7 |8 |9 |10 |11 |12 |13 |14 | |--|--|--|--|--|--|----|--|---|---|---|----|---|----| -1--1--2--3--5--8--13---0--13--13--26--39---65--104--

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

Ответ: 104

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

Задача 11#6068

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

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

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

2. умножить на 2,

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

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

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

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

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