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

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

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

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

1. прибавь 1

2. прибавь 5

3. умножь на 2

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +5), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x == y: # Если дошли до нужного числа
        return 1
    if x > y or x == 10: # Если число стало больше нужного или встретили 10
        return 0
    return f(x + 1, y) + f(x + 5, y) + f(2 * x , y) # Количество путей до текущего числа

print(f(2, 16)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 5 и i // 2.

# Создаем массив для хранения количества путей до чисел от 3 до 16
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 17
a[2] = 1 # Начальное число
for i in range(3, 17):
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    a[10] = 0 # Пропускаем число 10
print(a[16]) # Выводим ответ

Ответ: 40

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

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

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

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

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

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

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

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

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 3, i - 4 и i // 2.

# Создаем массив для хранения количества путей до чисел от 257 до 273
# a[i] - количество программ, которые преобразуют число 256 в число i
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) # Будем делить на 2 только если число кратно 2
    if i == 262 or i == 270: # Если встретили запрещённые числа - ставим 0, чтобы их не учитывать
        a[i] = 0
print(a[273]) # Выводим ответ

Решение руками

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

Заметим, что $256 ⋅ 2 = 512$ — это больше числа, которое нам нужно найти, значит 3-я команда нам не понадобится. Составим уравнение:

$R(n ) = R (n − 3) + R (n − 4)$

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

|----|-----|----|----|-----|----| |256-|257--|258-|259-|260--|261-| | 1 | 0 | 0 | 1 | 1 | 0 | ---------------------------------

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

|----|-----|----|----|-----|----|----|-----|----| |261-|262--|263-|264-|265--|266-|267-|268--|269-| --0----0-----2----1----0-----2----3----1-----2---

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

--------------------------- |269 |270 |271 |272 |273 | |----|----|-----|----|----| --2----0----4-----3----2---

Отсюда ответ — 2.

Ответ: 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|--|--|--|--|--|----|---|---|--|---|---|----|---|---|---|----|---|---|---|---|----|---|---| |1 |2 |3 |4 |5 | 6 |7 |8 |9 |10 |11 | 12 |13 |14 |15 |16 |17 |18 |19 |20 |21 |22 |23 | |--|--|--|--|--|----|---|---|--|---|---|----|---|---|---|----|---|---|---|---|----|---|---| -1--2--3--5--5--10---10--15--0---5---5---20--20--30--35--50---50--60--60--70--80---85--85--

Аналогично $R(24) = 0$ . Продолжим заполнять таблицу:

|---|---|----|---|---|---|----|---|---| |23-|24-|25--|26-|27-|28-|29--|30-|31-| -85---0---0---20--20--50--50---90--90--

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

-------------------------------------- |31 |32 |33 |34 |35 |36 |37 | 38 | |----|---|---|---|----|----|----|-----| -90---0---5---55--55---135--135--195--|

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, умножить на 3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

#Функция для подсчета количества программ преобразования a -> b
def f(c,m):
    if c > m or c == 9 or c == 24 or c == 32: # Если число стало больше нужного или встретились запрещённые
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c * 2, m) + f(c + 1, m) + f(c * 3, m) # Количество путей до текущего числа

print(f(1,38)) # Найдем ответ по условию задачи

Ответ: 195

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

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

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

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

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.

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, +2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 8: # Если число стало больше нужного или встретили запрещённое
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m)+f(c + 1, m) # Количество путей до текущего числа

print(f(1, 14)) # Найдем ответ по условию задачи

Ответ: 104

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

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

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

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

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

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

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

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

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1 и i // 2.

a = [0] * 20
a[1] = 1 # Начальное число
for i in range(2, 20):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    if i == 14: # Если встретили нужное число - обнулим всё до него, таким образом будут учтены пути лишь с учётом 14
        a[i] = 0
print(a[19]) # Выводим ответ

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

# Повторим шаги с первого решения динамикой, но теперь будем заполнять значения наперёд
# Создаем массив для хранения количества путей до чисел до 40
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14: # Если встретили нужное число - обнулим всё до него, таким образом будут учтены пути лишь с учётом 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

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

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

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

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

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.

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 16 or c == 23:  # Если число стало больше нужного или встретили запрещённое
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 1, m) + f(c + 3, m) + f(c * 2, m) # Количество путей до текущего числа

print(f(1, 27)) # Найдем ответ по условию задачи

Ответ: 7247

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

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

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

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

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.

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+2, +5, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 13 or c == 19: # Если число стало больше нужного или встретили запрещённое
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m) + f(c + 3, m) + f(c + 5, m) # Количество путей до текущего числа

print(f(1, 25)) # Найдем ответ по условию задачи

Ответ: 796

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

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

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

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

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.

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +3, умножить на 3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 5 or c == 17 or c == 35: # Если число стало больше нужного или встретилось запрещённое
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 1, m) + f(c + 3, m) + f(c * 2, m) + f(c * 3, m) # Количество путей до текущего числа

print(f(3, 45)) # Найдем ответ по условию задачи

Ответ: 1278967

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

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

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

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

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

Первая из этих команд увеличивает число $x$ на экране на $1$ , вторая переводит число $x$ в число $2x + 1$ . Например, вторая команда переводит число $10$ в число $21$ . Программа для исполнителя ГО – это последовательность команд.

Сколько существует таких программ, которые число $1$ преобразуют в число $27$ , причём траектория вычислений не содержит число $26$ ?

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2 + 1), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 26: # Если число стало больше нужного или встретилось запрещённое
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x + 1, y) + f(x * 2 + 1, y) # Количество путей до текущего числа

print(f(1, 27)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1 и i // 2 - 1.

# Создаем массив для хранения количества путей до чисел от 2 до 27
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 28
a[1] = 1 # Начальное число
for i in range(2, 28):
    a[i] = a[i - 1]
    if i % 2 == 1:
        # Будем делить на 2 только если число даёт остаток 1, то есть результат по сути делить на 2 - 1 (деление целочисленное)
        a[i] += a[i // 2]
    if i == 26: # Выводим ответ
        a[i] = 0

print(a[27]) # Выводим ответ

Ответ: 13

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

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

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

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

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +4), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 30: # Если число стало больше нужного или встретили запрещённое
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x + 1, y) + f(x + 4, y) + f(x * 2, y) # Количество путей до текущего числа

print(f(33, 72)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 4 и i // 2.

# Создаем массив для хранения количества путей до чисел от 34 до 72
# a[i] - количество программ, которые преобразуют число 33 в число i
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)  # Будем делить на 2 только если число кратно 2 и не равно 30
print(num[72]) # Выводим ответ

Ответ: 157430

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

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

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

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

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +4), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 56: # Если число стало больше нужного или встретилось запрещённое
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x + 1, y) + f(x + 4, y) + f(x * 2, y) # Количество путей до текущего числа

print(f(33, 72)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 4 и i // 2.

# Создаем массив для хранения количества путей до чисел от 33 до 72
# a[i] - количество программ, которые преобразуют число 33 в число i
a = [0] * 10000
a[33] = 1 # Начальное число
for i in range(33, 73):
    a[56] = 0 # Пропустим число 56
    # Увеличиваем количество путей в следующих ячейках, если в них можно попасть из текущей
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]
print(a[72]) # Выводим ответ

Ответ: 71265

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2 + 1), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(s, fi):
    if s > fi: # Если число стало больше нужного
        return 0
    if s == 21: # Если встретили 21
        return 0 # Пропустим его, вписав 0
    if s == fi: # Если дошли до нужного числа
        return 1
    return f(s + 1, fi) + f(s * 2 + 1, fi) # Количество путей до текущего числа
print(f(1, 25)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1 и i // 2.

# Создаем массив для хранения количества путей до чисел от 2 до 25
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 26
a[1] = 1 # Начальное число
for i in range(2, 26):
    a[i] += a[i - 1]
    if i % 2 != 0: # Будем делить на 2 только если число кратно 2
        a[i] += a[i // 2]
    if i == 21: # Если встретили 21
        a[i] = 0 # Пропустим его, вписав 0
print(a[25]) # Выводим ответ

Ответ: 20

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +3, умножить на 3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 5 or x == 17 or x == 35: # Если число стало больше нужного или встретили запрещённое
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x + 1, y) + f(x + 3, y) + f(x * 2, y) + f(x * 3, y) # Количество путей до текущего числа

print(f(3, 45)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 3, i // 2, i // 3.

# Создаем массив для хранения количества путей до чисел от 4 до 45
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0]*46
a[3] = 1 # Начальное число
for i in range(4, 46):
    a[i] = a[i - 1] + a[i - 3]
    if i % 2 == 0: # Будем делить на 2 только если число кратно 2
        a[i] += a[i // 2]
    if i % 3 == 0: # Будем делить на 3 только если число кратно 3
        a[i] += a[i // 3]
    if i == 5 or i == 17 or i == 35: # Если встретили запрещённое число - пропускаем (ставим 0)
        a[i] = 0
print(a[45]) # Выводим ответ

Ответ: 1278967

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

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(start, finish):
    if start == finish:  # Если дошли до нужного числа
        return 1
    if start > finish or start == 8: # Если число стало больше нужного или 8
        return 0
    return f(start + 1, finish) + f(start + 2, finish) + f(start * 2, finish) # Количество путей до текущего числа
print(f(3, 13)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 2 и i // 2.

# Создаем массив для хранения количества путей до чисел от 4 до 13
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * 14
a[3] = 1 # Начальное число
for i in range(4, 14):
    if i == 8: # Пропустим число 8
        continue
    a[i] += a[i - 1]
    a[i] += a[i - 2]
    if i % 2 == 0: # Будем делить на 2 только если число кратно 2
        a[i] += a[i // 2]
print(a[13]) # Выводим ответ

Ответ: 40

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    if a == b: # Если дошли до нужного числа
        return 1
    if a > b or a == 7 or a == 15: # Если число стало больше нужного или попалось 7 или 15
        return 0
    return f(a + 1, b) + f(a * 2, b) + f(a + 3, b) # Количество путей до текущего числа


print(f(2, 20)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 3 и i // 2.

# Создаем массив для хранения количества путей до чисел от 3 до 20
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 21
a[2] = 1 # Начальное число
for i in range(3, 21):
    if i == 7 or i == 15: # Пропустим 7 и 15
        continue
    # Добавим в текущую ячейку пути из предыдущих
    if i % 2 == 0: # Будем делить на 2 только если число кратно 2
        a[i] += a[i // 2]
    a[i] += a[i - 3]
    a[i] += a[i - 1]
print(a[20]) # Выводим ответ

Ответ: 304

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

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

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

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

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

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

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

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

Ответ: 2

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

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

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

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

2. Поделить на $3$ нацело.

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $12$ при исходном числе $11$ траектория будет состоять из чисел $10,3$ .

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

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

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

0, если a < b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (-1, // 3), если a > b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x < y or x == 8: # Если число стало меньше нужного или попалась 8
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x - 1, y) + f(x // 3, y) # Количество путей до текущего числа

print(f(43, 1)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i + 1, i * 3, i * 3 + 1, i * 3 + 2.

# Создаем массив для хранения количества путей до чисел от 42 до 0
# a[i] - количество программ, которые преобразуют число 43 в число i
a = [0] * (43 * 3 + 3)
a[43] = 1 # Начальное число
for i in range(42, 0, -1):
    # Количество путей до текущего числа. Учтем, что целочисленное деление сработает и для чисел * 3 + 1 и * 3 + 2.
    a[i] = a[i + 1] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
    if i == 8: # Если встретили 8 - исключаем её (ставим 0 путей)
        a[i] = 0
print(a[1]) # Выводим ответ

Ответ: 189

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

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

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

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    if a > b or a == 8: # Если число стало больше нужного или 8
     return 0
    if a == b: # Если дошли до нужного числа
     return 1
    if a < b:
     return f(a + 1, b) + f(a * 2, b) # Количество путей до текущего числа

print(f(1, 30)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i // 2.

# Создаем массив для хранения количества путей до чисел от 2 до 30
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 31
a[1] = 1 # Начальное число
for i in range(2, 31):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    a[8] = 0 # Пропускаем 8
print(a[30]) # Выводим ответ

Ответ: 76

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

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

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

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

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

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

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

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

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

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (умножить на 2, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 28: # Если число стало больше нужного или 28
        return 0
    elif x == y: # Если дошли до нужного числа
        return 1
    else:
        return f(x + 3, y) + f(x * 2, y) # Количество путей до текущего числа

print(f(4, 47)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 3 и i // 2.

# Создаем массив для хранения количества путей до чисел от 5 до 47
# a[i] - количество программ, которые преобразуют число 4 в число i
a = [0] * 100
a[4] = 1 # Начальное число
for i in range(5, 48):
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    a[28] = 0 # Пропустим 28
print(a[47]) # Выводим ответ

Ответ: 11

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

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

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

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

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

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

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

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

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

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

- значит мы достигли результата корректным путем,

- возвращаем 1.

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

- дальнейшее движение невозможно,

- возвращаем 0.

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

- прибавляем 1 к текущему числу, вызывая f(n+1, m),

- умножаем текущее число на 2, вызывая f(n*2, m).

- Суммируем результаты этих двух вызовов, чтобы получить общее количество программ, ведущих к $m$ из текущего $n$ .

Таким образом, рекурсия последовательно перебирает все допустимые последовательности команд, исключая запрещённое число 14, и считает количество корректных программ.

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

# Вызываем функцию для исходного числа 5 и целевого числа 31
# и выводим общее количество корректных программ
print(f(5, 31))

—

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

Мы можем использовать динамическое программирование для подсчета количества программ, создавая массив, где каждый индекс соответствует числу, а значение в ячейке — количеству программ, приводящих к этому числу из исходного числа 5, без прохождения через запрещённое число 14.

1. Создаём массив a длиной 32 (для чисел от 0 до 31), изначально заполняем его нулями.

2. Устанавливаем a[5] = 1, так как исходное число 5 даёт ровно один путь к самому себе.

3. Проходим циклом по числам от 6 до 31:

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

- Если число $i$ чётное, добавляем количество способов добраться из $i∕∕2$ (команда «умножить на 2»).

4. После заполнения массива исключаем запрещённое число: a[14] = 0.

5. В конце a[31] содержит количество программ, которые переводят 5 в 31 без прохождения через 14.

# Создаем массив для чисел от 0 до 31, изначально все значения 0
a = [0] * 32
# Начальное число 5, один способ быть в нем
a[5] = 1
# Перебираем числа от 6 до 31 включительно
for i in range(6, 32):
    # Количество способов добраться до i через прибавление 1
    # и через умножение на 2, если i четное
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0)
    # Запрещаем проход через число 14
    a[14] = 0
# Выводим количество программ, которые ведут от 5 к 31
print(a[31])

Ответ: 12