РЕКУРСИЯ
ЕГЭ-16
Сайт К.Полякова \ЕГЭ\ Генератор\№23
https://kpolyakov.spb.ru/download/calcdyn.zip
ТРЕНАЖЕР “Динамическое программирование”
№5542
(М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:�1. Прибавь 2�2. Умножь на 3�3. Умножь на 4�Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 3, выполняя третью – умножает на 4.
Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений содержит ровно 5 чисел с суммой цифр 14.
Ответ:612020
№5542
(М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:�1. Прибавь 2�2. Умножь на 3�3. Умножь на 4�Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 3, выполняя третью – умножает на 4.
Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений содержит ровно 5 чисел с суммой цифр 14.
Ответ:612020
def way(s, f, count):
h=str(s)
d=0
for i in range(0,-1):
d=d+int(h[i])
if s > f:
return 0
if s==f or ((count == 5) and (d==14)):
return 1
return way(s + 2, f, count+1) + way(s * 3, f, count + 1) + way(s * 4, f, count + 1)
print(way(1,600,0))
не рабочая
№ 5465
(Е. Джобс) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:�1. Вычти 3�2. Раздели нацело на 2�Выполняя первую из них, исполнитель уменьшает число на экране на 3, выполняя вторую – делит число на экране на 2 нацело, отбрасывая остаток.
Программой для исполнителя называется последовательность команд.
Сколько существует программ, для которых при исходном числе 108 результатом является число 12, и при этом траектория вычислений содержит число 42?
Ответ:30
№ 5465
(Е. Джобс) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:�1. Вычти 3�2. Раздели нацело на 2�Выполняя первую из них, исполнитель уменьшает число на экране на 3, выполняя вторую – делит число на экране на 2 нацело, отбрасывая остаток.
Программой для исполнителя называется последовательность команд.
Сколько существует программ, для которых при исходном числе 108 результатом является число 12, и при этом траектория вычислений содержит число 42?
Ответ:30Т: 30
def f(a, b):
if a < b:
return 0
if a==b:
return 1
return f(a-3,b) + f(a//2,b)
print(f(108,42)*f(42,12))
№ 5404
(Е. Джобс) Исполнитель преобразует двузначное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
Выполняя первую из них, исполнитель складывает разряды числа и выводит соответствующее значение на экран. При выполнении второй команды находится произведение разрядов, которое выводится на экран.
Программой для исполнителя называется последовательность команд. Например, программа 221 примененная к числу 93 выполнится следующим образом: 9*3 = 27, 2*7 = 14, 1+4 = 5.
Найдите количество различных двузначных чисел, которые этот исполнитель может преобразовать в число 8?
ОТВЕТ: 34
№ 5404
(Е. Джобс) Исполнитель преобразует двузначное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
Выполняя первую из них, исполнитель складывает разряды числа и выводит соответствующее значение на экран. При выполнении второй команды находится произведение разрядов, которое выводится на экран.
Программой для исполнителя называется последовательность команд. Например, программа 221 примененная к числу 93 выполнится следующим образом: 9*3 = 27, 2*7 = 14, 1+4 = 5.
Найдите количество различных двузначных чисел, которые этот исполнитель может преобразовать в число 8?
ОТВЕТ: 34
№ 5403
(А. Богданов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 2�2. Умножь на 2�3. Возведи в квадрат�Первая команда увеличивает число на экране на 2, вторая – умножает на 2, третья команда возводит число в квадрат. Сколько существует различных программ с нечётным числом команд, которые преобразуют исходное число 1 в число 100?
Ответ:1025 34
№ 5403
(А. Богданов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 2�2. Умножь на 2�3. Возведи в квадрат�Первая команда увеличивает число на экране на 2, вторая – умножает на 2, третья команда возводит число в квадрат. Сколько существует различных программ с нечётным числом команд, которые преобразуют исходное число 1 в число 100?
Ответ:1025 34
def f(a, b,col):
if a > b:
return 0
if a==b and col%2==1:
return 1
if b%2==0 and b==a**2:
return f(a*2,b,col+1)+f(a+2,b.col+1)+f(a**2,b,col)
if a%2!=0 and b==a**2:
return f(a+2,b,col+1)+f(a,b,col+1)
return f(a+2,b,col+1)
print(f(1,100,0))
не рабочая
№ 5329
(ЕГЭ-2022) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:�1. Вычти 1�2. Найди целую часть от деления на 2�Первая команда уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?
Ответ:376
№ 5329
(ЕГЭ-2022) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:�1. Вычти 1�2. Найди целую часть от деления на 2�Первая команда уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?
Ответ:376
№ 5259
(Е. Джобс) На экране есть два окна, в каждом из которых написано по числу. У исполнителя Сумматор есть две команды, которым присвоены номера:
Выполняя первую из них, Сумматор складывает числа в окнах и заменяет этой суммой число в первом окне, а выполняя вторую, складывает числа и заменяет этой суммой число во втором окне. Сколько существует программ для Сумматора таких, что в результате его работы из пары чисел (1, 1) получится пара с суммой 88?
Ответ:40
Решение № 5259
(Е. Джобс) Удобней будет идти от конца к началу.
Обе команды сохраняют одно число неизменным, значит, в паре 13 и 4 тоже есть число из предыдущей пары. Т. к. 13 > 4, то 4 не изменилось, а значит, 13 = 9 + 4. Эта пара получена командой 1 из пары 9 и 4.
Аналогично для 9: 9 = 5 + 4, команда 1 из пары 5 и 4.
Аналогично для 5: 5 = 1 + 4, команда 1 из пары 1 и 4.
Поскольку 1 < 4, то число 4 получено как 4 = 1 + 3, т. е. командой 2 из пары 1 и 3
Аналогично рассуждаем для 3: 3 = 1 + 2, командой 2 из пары 1 и 2.
Окончательно, последовательность команд: 22111.
Ответ:40
(Е. Джобс) На экране есть два окна, в каждом из которых написано по числу. У исполнителя Сумматор есть две команды, которым присвоены номера:
Выполняя первую из них, Сумматор складывает числа в окнах и заменяет этой суммой число в первом окне, а выполняя вторую, складывает числа и заменяет этой суммой число во втором окне. Сколько существует программ для Сумматора таких, что в результате его работы из пары чисел (1, 1) получится пара с суммой 88?
Ответ:40
№5099
(А. Брейк) Лягушке нужно добраться до укрытия, избегая опасностей. У Лягушки есть три действия:�1. Короткий прыжок +1 �2. Длинный прыжок +2 �3. Избежать опасности 2n
Первые два действия увеличивают позицию Лягушки на 1 и 2 соответственно. Третье действие применяет тогда, когда Лягушка находится в нечетной позиции — позиция N преобразуется в позицию 2N, позволяя Лягушке избежать опасности.
Другие действия в нечетных позициях не могут быть выполнены.
Лягушка была замечена на расстоянии 2.
Сколько существует различных путей Лягушки к укрытию в позиции 76, каждый их которых содержит позиции 20 и 38?
Ответ:7
Решение №5099
(А. Брейк) Лягушке нужно добраться до укрытия, избегая опасностей. У Лягушки есть три действия:�1. Короткий прыжок +1 �2. Длинный прыжок +2 �3. Избежать опасности 2n
Первые два действия увеличивают позицию Лягушки на 1 и 2 соответственно. Третье действие применяет тогда, когда Лягушка находится в нечетной позиции — позиция N преобразуется в позицию 2N, позволяя Лягушке избежать опасности. Другие действия в нечетных позициях не могут быть выполнены. Лягушка была замечена на расстоянии 2. Сколько существует различных путей Лягушки к укрытию в позиции 76, каждый их которых содержит позиции 20 и 38?
Ответ:7
def F(x, y):
if x > y:
return 0
if x == y:
return 1
if x % 2 == 1:
return F(x * 2, y)
return F(x + 1, y) + F(x + 2, y)
print(F(2, 20)* F(20, 38)*F(38,76))�
№1
Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:
Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21.
Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.
Ответ:10
Решение №1
def F(x, y):
if x > y or x==24:
return 0
if x == y:
return 1
if x <y:
return F(x + 1, y) + F(x * 2 +1, y)
return F(x + 1, y)
print(F(1, 25))
Ответ:10
№2
У исполнителя Удвоитель две команды, которым присвоены номера:�1. Прибавить 1�2. Умножить на 2�Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Удвоитель – это последовательность команд.
Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?
Ответ:18
№2
У исполнителя Удвоитель две команды, которым присвоены номера:�1. Прибавить 1�2. Умножить на 2�Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Удвоитель – это последовательность команд.
Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?
Ответ:18
def nProg( x, t ): # x - текущее число, t - цель (target)
if x == t:
return 1
if x > t:
return 0
# x < t - строим дерево:
return nProg( x + 1, t ) + nProg( x * 2, t )
# Т.к. предпоследняя команда +1, то 22 +1 +1 = 24, (11 +1) *2 = 24
print( nProg( 4, 22 ) + nProg( 4, 11 ) )
№3448
(№ 3448) (С.С. Поляков)
У исполнителя Калькулятор есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
•
Сколько разных чисел на отрезке [34, 59] может быть получено из числа 1 с помощью программ, состоящих из 6 команд?
Ответ:11
№3448
(С.С. Поляков)
У исполнителя Калькулятор есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
•
Сколько разных чисел на отрезке [34, 59] может быть получено из числа 1 с помощью программ, состоящих из 6 команд?
Ответ:11
def func(s,x,l):
if x < s or l < 0:
return 0
if x == s:
return 1
K = func(s,x-1,l-1)
K += func(s,x-2,l-1)
if x % 2 == 0:
K += func(s,x//2,l-1)
return K
count = 0
for i in range(34,60):
if func(1,i,6) != 0:
count += 1
print(count)
#'s' - начало, 'x' - цель, 'l' - количество команд, 'count' - количество чисел
№3
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь две младшие цифры на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая-либо из двух младших цифр равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.
Сколько есть программ, которые число 23 преобразуют в число 48?
Ответ:26
№3
t = 48 # цель (target)
# Функция подсчета количества цепочек команд (программ).
# x - текущее число.
def nProg( x ):
if x == t: # если цель достигнута, то
return 1 # завершить функцию, посчитав цепочку (программу)
if x > t: # если перелет, то
return 0 # завершить функцию, не считая цепочку
# x < t - продолжаем строить дерево:
x1 = x
if x1 % 100 // 10 < 9: # число десятков < 9?
x1 += 10
if x1 % 10 < 9: # число единиц < 9?
x1 += 1
return nProg( x + 1 ) + nProg( x1 )
print( nProg( 23 ) )
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь две младшие цифры на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая-либо из двух младших цифр равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.
Сколько есть программ, которые число 23 преобразуют в число 48?
Ответ:26
№4
№4
№5
№5