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

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

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

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

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

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

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

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

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

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

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

Задача 1#72492

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

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

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

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

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

def f(a,b):
    if a > b:return 0
    if a == b:return 1
    return f(a+2,b)+f(a+3,b)
print(f(4,7)*f(7,14))

Ответ: 3

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

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

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

Задача 2#63348

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

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

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

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

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

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

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

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

def f(x, y, is_8=0, is_13=0):
    if x == 8:
        is_8 = 1
    if x == 13:
        is_13 = 1

    if x > y:
        return 0
    if x == y and is_8 != is_13:
        return 1
    if x < y:
        return f(x + 1, y, is_8, is_13) + f(x * 2, y, is_8, is_13) + f(x + 2, y, is_8, is_13)
    return 0

print(f(3, 23))

Ответ: 7003

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

Задача 3#60737

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает число на 2, третья увеличивает число в 3 раза. Программа для исполнителя РазДваТри - это последовательность команд.

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

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

def f(a,b):
    if a > b:return 0
    if a == b:return 1
    if a < b:return f(a+1,b)+f(a+2,b)+f(a*3,b)
print(f(3,9)*f(9,14))

Ответ: 112

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

Задача 4#60488

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

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

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

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

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

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

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

# Сначала доходим до 31, потом из 31 до 77, перемножаем траектории
print(f(7, 31)*f(31, 77))

Ответ: 315645

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

Задача 5#58500

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

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

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

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

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

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

a = [0] * 101
a[2] = 1
for i in range(3, 101):
    a[i] = a[i - 3] + a[i - 4] + a[i // 5] * (i % 5 == 0)
    if i == 50:
        for j in range(i):
            a[j] = 0
print(a[100])

Ответ: 31503912

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

Задача 6#58499

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

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

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

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

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

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

a = [0] * 100
a[4] = 1
for i in range(5, 32):
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    if i == 18:
        for j in range(i):
            a[j] = 0
print(a[31])

Ответ: 236756

Курсы

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

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

Задача 7#54936

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

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

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

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

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

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

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

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

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

a = [0] * 100
a[2] = 1
for i in range(3, 36):
    a[i] = a[i - 1] + a[i - 4]
    if i % 3 == 0:
        a[i] += a[i // 3]
    if i == 18:
        for j in range(18):
            a[j] = 0
print(a[35])

Ответ: 18209

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

Задача 8#53444

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

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

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

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

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

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

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

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

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

def f(a,b):
    if a > b:return 0
    if a == b:return 1
    if a < b:return f(a+1,b) + f(a*2,b) + f(a+3,b)
print(f(2,14)*f(14,24))

Ответ: 3752

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

Задача 9#52532

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

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

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

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

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

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

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

Ответ: 68

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

Задача 10#6866

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

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

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

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

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

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

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

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

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

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

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

|---|--|--|--|--|--|--|--|---| |2--|3-|4-|5-|6-|7-|8-|9-|10-| |1 |1 |2 |2 |3 |3 |5 |5 | 7 | ------------------------------

Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — $R(12) = R (11)$ . Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.

В итоге получаем ответ — 7

Ответ: 7

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

Задача 11#6841

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 27 и при этом троектория содержит числа 13 и 19 ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

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

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

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

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

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

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

Используя данные формулы, заполним таблицу до 13:

|2-|3-|4-|5-|6-|-7-|-8--|9--|10-|-11-|-12--|13--| |--|--|--|--|--|---|----|---|---|----|-----|----| -1--1--3--4--9--13---25--39--68--107---187--294--

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

|13--|-14-|-15--|16--|-17--|--18--|-19--| |----|----|-----|----|-----|------|-----| -294--294--588---882--1470--2352---3822--

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

|-----|------|-----|-------|-------|------|-------|------|--------| |-19--|--20--|-21--|--22---|--23---|-24---|--25---|-26---|---27---| -3822--3822---7644--11466---19110---30576--49686---80262--129948---

Отсюда получаем ответ – 129948.

Ответ: 129948

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#6840

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 38 и при этом троектория содержит числа 14 и 29? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.

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

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

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

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

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

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

Заполним таблицу по данным формулам до 14:

|2-|3-|4-|5-|6--|7-|8-|9-|10-|11-|12-|-13-|14-| |--|--|--|--|---|--|--|--|---|---|---|----|---| -1--0--2--1--3---3--6--6--10--12--21---22--36-|

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

|14-|15-|16-|17-|-18-|19-|20-|-21-|-22--|23--|-24--|25--|26--|-27--|28--|-29--| |---|---|---|---|----|---|---|----|-----|----|-----|----|----|-----|----|-----| -36--0---36--36---36--72--72--108---144--180--252---324--432--576---756--1008--

Аналогично $R(30) = 0$ , так как число 30 никак нельзя получить, чтобы траектория проходила через число 29. Заполним таблицу до конца:

|-----|---|------|-----|------|-----|------|-----|------|-----| |-29--|30-|--31--|-32--|--33--|-34--|-35---|-36--|-37---|-38--| |1008 | 0 | 1008 |1008 |1008 |2016 |2016 |3024 |4032 |5040 | ---------------------------------------------------------------

Отсюда получаем ответ: 5040.

Ответ: 5040

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

Задача 13#6839

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|--|--|--|--|--|--|---|---|---|---|---|----|---|---|---|----|---|---|---|---|----|---|---|---|----|---| |3-|4-|5-|6-|7-|8-|-9-|10-|11-|12-|13-|14--|15-|16-|17-|18--|19-|20-|21-|22-|23--|24-|25-|26-|27--|28-| -1--0--1--1--1--2---3--3---5----6---0---6---6---6---12--12---0---12--12--12--24---24--36--48--60---84-|

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

Ответ: 84

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

Задача 14#6071

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

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

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

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

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

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

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

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

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

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

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

Заполним таблицу по данным формулам до 10:

|--|---|--|--|--|--|---|---|----| |2-|3--|4-|5-|6-|7-|-8-|-9-|10--| |1 |1 |2 |3 |5 |7 |12 |17 |27 | --------------------------------

По условию сказано, что траектория должна проходить через число 10, значит $R (11) = 30$ , так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:

|--|--|--|--|--|--|----|---|---|---|----|---|---|----|-----|----| |2-|3-|4-|5-|6-|7-|-8--|9--|10-|11-|12--|13-|14-|-15-|-16--|17--| |1 |1 |2 |3 |5 |7 | 12 |17 |27 |27 |27 |54 |81 |108 |162 |243 | -----------------------------------------------------------------

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

Ответ: 243

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

Задача 15#6055

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

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

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

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

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

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

Решение 1

a = [0] * 25
a[4] = 1
for i in range(5, 25):
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    if i == 11 or i == 17:
        for j in range(i):
            a[j] = 0
print(a[24])

Решение 2

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

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

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

Заполним таблицу по данным формулам до 11:

---------------------------- |4 |5 |6 |7 |8 |9 |10 |11 | |---|--|--|--|--|--|---|---| -1---1--1--1--2--3---5---6--

По условию траектория должна проходить через число 11, значит $R (12) = 6$ , так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:

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

Аналагично $R(19) = 24$ , так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:

|--|--|--|--|---|--|---|---|---|---|----|---|---|---|----|---|---|---|---|----|---| |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 | 14 |15 |16 |17 |18 |19 |20 |21 |22 |23 |24 | |1-|1-|1-|1-|2--|3-|5--|6--|-6-|-6-|-6--|6--|12-|18-|24--|24-|24-|24-|24-|48--|72-| ----------------------------------------------------------------------------------|

Отсюда получаем ответ: 72.

Ответ: 72

Предыдущий раздел

Следующий раздел