Карточки
Тесты
Главная
Курсы
Куратор
Подписка
23. Построение дерева вариантов. Оператор присваивания и ветвления: все задания
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить $1$
B. Прибавить $3$
C. Умножить на $3$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $3$ результатом является число $20$, при этом траектория вычислений содержит число $14$ и не содержит $15$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $7$ траектория будет состоять из чисел $21$, $24$, $25$.
Так как все команды только увеличивают число, любая траектория, содержащая $14$, разбивается на две части: $3\rightarrow14\rightarrow20$.
Посчитаем количество программ от $3$ до $14$ и от $14$ до $20$. Число $15$ запрещаем.
def f(x, y):
if x == y:
return 1
if x > y or x == 15:
return 0
return f(x + 1, y) + f(x + 3, y) + f(x * 3, y)
print(f(3, 14) * f(14, 20))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $15$, такая траектория не подходит.
Количество путей:
$3\rightarrow14$: $46$,
$14\rightarrow20$: $2$.
$46\cdot2=92$.
Программа выведет: $92$.
20
Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить $1$
2. Умножить на $2$
Первая команда увеличивает число на экране на $1$, вторая умножает его на $2$.
Программа для Вычислителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $2$ результатом является число $30$ и при этом траектория вычислений содержит число $14$ и не содержит числа $25$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $17$.
Так как все команды только увеличивают число, любая траектория, содержащая $14$, разбивается на две части:
$2\rightarrow14\rightarrow30$.
Посчитаем количество программ от $2$ до $14$ и от $14$ до $30$. Число $25$ запрещаем.
def f(x, y):
if x == y:
return 1
if x > y or x == 25:
return 0
return f(x + 1, y) + f(x * 2, y)
print(f(2, 14) * f(14, 30))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $25$, такая траектория не подходит.
Количество путей:
$2\rightarrow14$: $13$,
$14\rightarrow30$: $2$.
$13\cdot2=26$.
Программа выведет: $26$.
20
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть $1$
B. Вычесть $2$
C. Найти целую часть от деления на $3$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $19$ результатом является число $3$, при этом траектория вычислений не содержит чисел $9$ и $16$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $13$ траектория состоит из чисел $4$, $2$, $1$.
Так как все команды уменьшают число, будем считать количество программ, переводящих число $19$ в число $3$. Числа $9$ и $16$ запрещаем.
def f(x, y):
if x == y:
return 1
if x < y or x == 9 or x == 16:
return 0
return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)
print(f(19, 3))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $9$ или $16$, такая траектория не подходит. Если значение стало меньше $y$, прийти обратно к $y$ уже невозможно.
Программа выведет: $180$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь $1$
B. Поменяй местами
Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $100$ результатом является число $150$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.
Так как обе команды увеличивают число, будем последовательно считать количество программ, переводящих число $100$ в число $150$.
Для команды B выделим цифры десятков и единиц. Если цифра десятков меньше цифры единиц, меняем их местами.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
k = f(x + 1, y)
a = x // 10 % 10
b = x % 10
if a < b:
z = x - 10 * a - b + 10 * b + a
k += f(z, y)
return k
print(f(100, 150))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена, и получаем новое число $z$ с переставленными цифрами.
Программа выведет: $35$.
20
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $3$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает его на $3$.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $2$ в число $14$ и при этом траектория вычислений программы содержит число $9$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $24$, $26$.
Так как все команды только увеличивают число, любая траектория, содержащая $9$, разбивается на две части:
$2\rightarrow9\rightarrow14$.
Посчитаем количество программ от $2$ до $9$ и от $9$ до $14$.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(2, 9) * f(9, 14))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow9$: $25$,
$9\rightarrow14$: $8$.
$25\cdot8=200$.
Программа выведет: $200$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь $1$
B. Поменяй местами
Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $101$ результатом является число $152$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.
Для решения используем рекурсивную функцию. Команда A переводит число $x$ в $x+1$.
Для команды B найдём цифру десятков $a$ и цифру единиц $b$. Если $a<b$, меняем эти цифры местами.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
k = f(x + 1, y)
a = x // 10 % 10
b = x % 10
if a < b:
z = x - 10 * a - b + 10 * b + a
k += f(z, y)
return k
print(f(101, 152))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена. Число $z$ получается перестановкой двух последних цифр числа $x$.
Программа выведет: $42$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь $1$
B. Поменяй местами
Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $100$ результатом является число $143$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.
Для решения используем рекурсивную функцию. Команда A переводит число $x$ в $x+1$.
Для команды B найдём цифру десятков $a$ и цифру единиц $b$. Если $a<b$, меняем эти цифры местами.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
k = f(x + 1, y)
a = x // 10 % 10
b = x % 10
if a < b:
z = x - 10 * a - b + 10 * b + a
k += f(z, y)
return k
print(f(100, 143))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена. Число $z$ получается перестановкой двух последних цифр числа $x$.
Программа выведет: $34$.
20
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить $2$
B. Прибавить $3$
C. Умножить на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $3$ результатом является число $25$, при этом траектория вычислений содержит число $10$ и не содержит $17$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $7$ траектория будет состоять из чисел $14$, $17$, $19$.
Так как все команды только увеличивают число, любая траектория, содержащая $10$, разбивается на две части:
$3\rightarrow10\rightarrow25$.
Посчитаем количество программ от $3$ до $10$ и от $10$ до $25$. Число $17$ запрещаем.
def f(x, y):
if x == y:
return 1
if x > y or x == 17:
return 0
return f(x + 2, y) + f(x + 3, y) + f(x * 2, y)
print(f(3, 10) * f(10, 25))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $17$, такая траектория не подходит.
Количество путей:
$3\rightarrow10$: $5$,
$10\rightarrow25$: $18$.
$5\cdot18=90$.
Программа выведет: $90$.
20
Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $3$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает на $3$.
Программа для исполнителя М17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $2$ в число $12$ и при этом траектория вычислений программы содержит числа $8$ и $10$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $24$, $26$.
Так как все команды только увеличивают число, траектория, содержащая числа $8$ и $10$, разбивается на три части:
$2\rightarrow8\rightarrow10\rightarrow12$.
Посчитаем количество программ на каждом участке.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(2, 8) * f(8, 10) * f(10, 12))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow8$: $15$,
$8\rightarrow10$: $2$,
$10\rightarrow12$: $2$.
$15\cdot2\cdot2=60$.
Программа выведет: $60$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти $1$
2. Найди целую часть от деления на $2$
Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $32$ результатом является число $1$, и при этом траектория вычислений содержит число $12$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе $10$ траектория состоит из чисел $9$, $4$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $12$, разбивается на две части: $32\rightarrow12\rightarrow1$.
Посчитаем количество программ от $32$ до $12$ и от $12$ до $1$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 1, y) + f(x // 2, y)
print(f(32, 12) * f(12, 1))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$32\rightarrow12$: $10$,
$12\rightarrow1$: $47$.
$10\cdot47=470$.
Программа выведет: $470$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти $2$
B. Найди целую часть от деления на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $36$ результатом является число $2$, и при этом траектория вычислений содержит число $8$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе $13$ траектория состоит из чисел $11$, $5$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $8$, разбивается на две части: $36\rightarrow8\rightarrow2$.
Посчитаем количество программ от $36$ до $8$ и от $8$ до $2$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 2, y) + f(x // 2, y)
print(f(36, 8) * f(8, 2))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$36\rightarrow8$: $10$,
$8\rightarrow2$: $4$.
$10\cdot4=40$.
Программа выведет: $40$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти $1$
2. Найди целую часть от деления на $2$
Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $30$ результатом является число $1$, и при этом траектория вычислений содержит число $10$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе $10$ траектория состоит из чисел $9$, $4$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $10$, разбивается на две части: $30\rightarrow10\rightarrow1$.
Посчитаем количество программ от $30$ до $10$ и от $10$ до $1$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 1, y) + f(x // 2, y)
print(f(30, 10) * f(10, 1))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$30\rightarrow10$: $12$,
$10\rightarrow1$: $30$.
$12\cdot30=360$.
Программа выведет: $360$.
20
Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить $1$
2. Умножить на $2$
Первая команда увеличивает число на экране на $1$, вторая умножает его на $2$.
Программа для Вычислителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $1$ результатом является число $22$ и при этом траектория вычислений содержит число $10$ и не содержит числа $15$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $17$.
Так как все команды только увеличивают число, любая траектория, содержащая $10$, разбивается на две части: $1\rightarrow10\rightarrow22$.
Посчитаем количество программ от $1$ до $10$ и от $10$ до $22$. Число $15$ запрещаем.
def f(x, y):
if x == y:
return 1
if x > y or x == 15:
return 0
return f(x + 1, y) + f(x * 2, y)
print(f(1, 10) * f(10, 22))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $15$, такая траектория не подходит.
Количество путей:
$1\rightarrow10$: $14$,
$10\rightarrow22$: $2$.
$14\cdot2=28$.
Программа выведет: $28$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти $1$
2. Найди целую часть от деления на $2$
Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $32$ результатом является число $1$, и при этом траектория вычислений содержит число $9$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе $10$ траектория состоит из чисел $9$, $4$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $9$, разбивается на две части: $32\rightarrow9\rightarrow1$.
Посчитаем количество программ от $32$ до $9$ и от $9$ до $1$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 1, y) + f(x // 2, y)
print(f(32, 9) * f(9, 1))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$32\rightarrow9$: $16$,
$9\rightarrow1$: $23$.
$16\cdot23=368$.
Программа выведет: $368$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти $1$
2. Найди целую часть от деления на $2$
Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $32$ результатом является число $1$, и при этом траектория вычислений содержит число $11$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе $10$ траектория состоит из чисел $9$, $4$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $11$, разбивается на две части: $32\rightarrow11\rightarrow1$.
Посчитаем количество программ от $32$ до $11$ и от $11$ до $1$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 1, y) + f(x // 2, y)
print(f(32, 11) * f(11, 1))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$32\rightarrow11$: $12$,
$11\rightarrow1$: $37$.
$12\cdot37=444$.
Программа выведет: $444$.
20
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь $1$
B. Поменяй местами
Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $100$ результатом является число $141$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.
Для решения используем рекурсивную функцию. Команда A переводит число $x$ в $x+1$.
Для команды B найдём цифру десятков $a$ и цифру единиц $b$. Если $a<b$, меняем эти цифры местами.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
k = f(x + 1, y)
a = x // 10 % 10
b = x % 10
if a < b:
z = x - 10 * a - b + 10 * b + a
k += f(z, y)
return k
print(f(100, 141))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена. Число $z$ получается перестановкой двух последних цифр числа $x$.
Программа выведет: $16$.
20
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $3$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает на $3$.
Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $2$ в число $11$ и при этом траектория вычислений программы содержит числа $8$ и $10$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $24$, $26$.
Так как все команды только увеличивают число, траектория, содержащая числа $8$ и $10$, разбивается на три части: $2\rightarrow8\rightarrow10\rightarrow11$.
Посчитаем количество программ на каждом участке.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(2, 8) * f(8, 10) * f(10, 11))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow8$: $15$,
$8\rightarrow10$: $2$,
$10\rightarrow11$: $1$.
$15\cdot2\cdot1=30$.
Программа выведет: $30$.
20
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть $1$
B. Вычесть $4$
C. Найти целую часть от деления на $3$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $19$ результатом является число $2$, при этом траектория вычислений не содержит числа $7$ и содержит $13$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $22$ траектория состоит из чисел $7$, $3$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $13$, разбивается на две части: $19\rightarrow13\rightarrow2$.
Посчитаем количество программ от $19$ до $13$ и от $13$ до $2$. Число $7$ запрещаем.
def f(x, y):
if x == y:
return 1
if x < y or x == 7:
return 0
return f(x - 1, y) + f(x - 4, y) + f(x // 3, y)
print(f(19, 13) * f(13, 2))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $7$, такая траектория не подходит.
Количество путей:
$19\rightarrow13$: $4$,
$13\rightarrow2$: $17$.
$4\cdot17=68$.
Программа выведет: $68$.
20
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить $1$
B. Прибавить $2$
C. Умножить на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число $4$ в число $15$, и при этом траектория вычислений программы содержит числа $11$ и $13$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $18$.
Так как все команды только увеличивают число, траектория, содержащая числа $11$ и $13$, разбивается на три части: $4\rightarrow11\rightarrow13\rightarrow15$.
Посчитаем количество программ на каждом участке.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)
print(f(4, 11) * f(11, 13) * f(13, 15))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$4\rightarrow11$: $25$,
$11\rightarrow13$: $2$,
$13\rightarrow15$: $2$.
$25\cdot2\cdot2=100$.
Программа выведет: $100$.
20
Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $3$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает на $3$.
Программа для исполнителя М17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $3$ в число $13$ и при этом траектория вычислений программы содержит числа $9$ и $11$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $24$, $26$.
Так как все команды только увеличивают число, траектория, содержащая числа $9$ и $11$, разбивается на три части: $3\rightarrow9\rightarrow11\rightarrow13$.
Посчитаем количество программ на каждом участке.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(3, 9) * f(9, 11) * f(11, 13))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$3\rightarrow9$: $14$,
$9\rightarrow11$: $2$,
$11\rightarrow13$: $2$.
$14\cdot2\cdot2=56$.
Программа выведет: $56$.
20