Задание №13. Рекурсивные алгоритмы, переборы вариантов решений
№ UH0TO9
(Уровень сложности: Базовый)
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Ответ: 68
№ 4OJUHJ
(Уровень сложности: Базовый)
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 3
C. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 25, и при этом траектория вычислений содержит число 15 и не содержит 7?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория состоит из чисел 14, 17, 18.
Ответ: 2716
№ SVZJQG
(Уровень сложности: Базовый)
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABC при исходном числе 7 траектория состоит из чисел 8, 16, 48.
Ответ: 188
№ 0OOOFI
(Уровень сложности: Повышенный)
Исполнитель преобразует число на экране. У исполнителя есть две команды, обозначенные буквами:
А. Прибавь 1;
Б. Поменяй местами.
А. Прибавь 1;
Б. Поменяй местами.
Первая команда увеличивает число на экране на 1. Вторая команда может применяться только к числу, у которого цифра разряда десятков по значению меньше цифры, стоящей в разряде единиц, и заменяет число числом, в котором цифры двух младших разрядов поменяны местами. Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 110 результатом является число 154?
Текстовое решение:
def f(start, end):
p = str(start) # преобразуем для удобства работы к строке
if start > end: return 0
if start==end: return 1
# Проверяем, меньше ли цифра в разряде десятков, чем в разряде единиц
if p[1]<p[2]: # Если меньше, то проводим замену
return f(start+1, end) + f(int(p[0]+p[2]+p[1]), end) # меняем цифры местами и преобразуем к числу
else: # Если нет, то выполняем только команду +1
return f(start+1, end)
print(f(110, 154))
Ответ: 34
№ 5JDM6D
(Уровень сложности: Повышенный)
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены номерами:
1. Прибавь 1
2. Поменять местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда может применяться только к числу, у которого цифра разряда десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 100 результатом является число 142?
1. Прибавь 1
2. Поменять местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда может применяться только к числу, у которого цифра разряда десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 100 результатом является число 142?
Видео разбор:
Текстовое решение:
def f(start, end):
p = str(start) # преобразуем для удобства работы к строке
if start > end: return 0
if start==end: return 1
# Проверяем, меньше ли цифра в разряде десятков, чем в разряде единиц
if p[1]<p[2]: # Если меньше, то проводим замену
return f(start+1, end) + f(int(p[0]+p[2]+p[1]), end) # меняем цифры местами и преобразуем к числу
else: # Если нет, то выполняем только команду +1
return f(start+1, end)
print(f(110, 154))
Ответ: 21
№ 4RNS4V
(Уровень сложности: Гроб)
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены номерами:
1. Прибавь 3
2. Поменять местами
Первая из этих команд увеличивает число на экране на 3. Вторая команда может применяться только к числу, у которого цифра разряда десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 10 результатом является число 169?
1. Прибавь 3
2. Поменять местами
Первая из этих команд увеличивает число на экране на 3. Вторая команда может применяться только к числу, у которого цифра разряда десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 10 результатом является число 169?
Видео разбор:
Текстовое решение:
def f(start, end):
p = str(start) # преобразуем для удобства работы к строке
if start > end: return 0
if start==end: return 1
# Проверяем, двузначное ли число, если да, то выполняем алгоритм для двузначного числа, если нет, то для трехзначного
if len(p) == 2:
# Проверяем, меньше ли цифра в разряде десятков, чем в разряде единиц
if p[0]<p[1]: # Если меньше, то проводим замену
return f(start+3, end) + f(int(p[1]+p[0]), end) # меняем цифры местами и преобразуем к числу
else: # Если нет, то выполняем только команду +3
return f(start+3, end)
if len(p) == 3:
# Проверяем, меньше ли цифра в разряде десятков, чем в разряде единиц
if p[1]<p[2]: # Если меньше, то проводим замену
return f(start+3, end) + f(int(p[0]+p[2]+p[1]), end) # меняем цифры местами и преобразуем к числу
else: # Если нет, то выполняем только команду +3
return f(start+3, end)
print(f(10, 169))
Ответ: 825
№ QTOGXF
(Уровень сложности: Повышенный)
Исполнитель Робот преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
А. Прибавь 1;
В. Поменять цифры в разряде единиц и десятков местами, если разряд десятков меньше разряда единиц.
Сколько есть программ, которые преобразуют число 100 в число 150?
Текстовое решение:
def f(start, end):
p = str(start) # преобразуем для удобства работы к строке
if start > end: return 0
if start == end: return 1
# Проверяем, меньше ли цифра в разряде десятков, чем в разряде единиц
if p[1]<p[2]: # Если меньше, то проводим замену
return f(start+1, end) + f(int(p[0]+p[2]+p[1]), end) # меняем цифры местами и преобразуем к числу
else: # Если нет, то выполняем только команду +1
return f(start+1, end)
print(f(100, 150))
Ответ: 35
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. вычти 3
В. вычти 6
C. найди целую часть от деления на 2
Программа для исполнителя - это последовательность команд.
Сколько существует программ, для которых при исходном числе 86 результатом является 12, при этом траектория вычислений содержит число 53 и не содержит 36?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 27 траектория состоит из чисел 13, 7, 4.
A. вычти 3
В. вычти 6
C. найди целую часть от деления на 2
Программа для исполнителя - это последовательность команд.
Сколько существует программ, для которых при исходном числе 86 результатом является 12, при этом траектория вычислений содержит число 53 и не содержит 36?
Траектория вычислений программы - это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 27 траектория состоит из чисел 13, 7, 4.
Ответ: 144
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Поменяй местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 100 результатом является число 141?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.
Ответ: 16