Динамика №23. 23 задание в ЕГЭ

1.

23 задание в Е ГЭ

2.

динамик
разбор
а
повышенный
уровень Е ГЭ:
уровень:
1
2
3
4
5
рекурсия
уровень Е ГЭ:
разбор
повышенный
уровень:
6
9
7
8
excel
уровень Е ГЭ:
11
1
0
разбор

3.

время ф инальных вопросов

4.

разбор динамического решения
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 4
результатом является число 15, и при этом траектория вычислений содержит
числа 8 и 10?
Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы. Например, для программы ABA при
исходном числе 8 траектория состоит из чисел 9, 18, 19.

5.

1) Сначала создаём словарь со значением, из которого начинаем идти:
f = {4: 1}

6.

2) Создаём цикл, который будет проходить по всем оставшимся числам, так как нам
нужен результат в числе 15, то цикл будет проходить от 5ти до 15 включительно и
перед тем, как рассмотреть это число, присваиваем ему нолик в словаре, чтобы
создать такой ключ:
f = {4: 1}
for i in range(5, 16):
f[i] = 0

7.

3) Начинаем записывать команды, записываем количество путей из предыдущего
числа, так как у наc есть команда с прибавлением единицы, складываем значение
из предыдущего ключа к текущему:
f = {4: 1}
for i in range(5, 16):
f[i] = 0
f[i] += f[i - 1]

8.

4) Умножением на два мы можем прийти только в четное число, поэтому проверяем,
что число i чётное и ключ i // 2 уже есть в словаре, складываем найденное
значение:
f = {4: 1}
for i in range(5, 16):
f[i] = 0
f[i] += f[i - 1]
if i % 2 == 0 and i // 2 in f:
f[i] += f[i // 2]

9.

5) Теперь записываем условие, что программа точно проходит через число 8 - это
значит, что число 8 можно будет считать начальным, значит всем предыдущим
ключам можно присвоить значение 0, чтобы не учитывать их. Поэтому, когда дошли
до числа 8, создаём цикл, который будет проходить от 4 до 8 (не включительно) , и
обнуляем все значения в этих ключах:
f = {4: 1}
for i in range(5, 16):
f[i] = 0
f[i] += f[i - 1]
if i % 2 == 0 and i // 2 in f:
f[i] += f[i // 2]
if i == 8:
for j in range(4, i):
f[j] = 0

10.

6) Для числа 10 пишем аналогично:
f = {4: 1}
for i in range(5, 16):
f[i] = 0
f[i] += f[i - 1]
if i % 2 == 0 and i // 2 in f:
f[i] += f[i // 2]
if i == 8:
for j in range(4, i):
f[j] = 0
if i == 10:
for j in range(4, i):
f[j] = 0

11.

7) Так как искали количество путей в число 15, то в конце выводим значение, которое
принадлежит ключу 15:
f = {4: 1}
for i in range(5, 16):
f[i] = 0
f[i] += f[i - 1]
if i % 2 == 0 and i // 2 in f:
f[i] += f[i // 2]
if i == 8:
for j in range(4, i):
f[j] = 0
if i == 10:
for j in range(4, i):
f[j] = 0
print(f[15])
ответ
2

12.

разбор рекурсивного решения
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Прибавить 4
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 9
результатом является число 37, и при этом траектория вычислений содержит
числа 27 и 29, но не содержит число 32?

13.

1) Создаём функцию с двумя параметрами: curr и end - curr - будет число, с
которым будем производить команды, end - конечное число, к которому мы
стремимся, он не изменяется:
def f(curr, end):

14.

2) Начинаем расписывать все возможные равенства, с этим параметрами. Если curr
превысит end, значит мы уже никогда не попадём в конечное число, возвращаем
функцией значение 0. Также у нас в условии прописано, что нельзя попадать в
число 32, значит можно дополнить условие, если мы попадём в 32, то также будем
возвращать 0.
def f(curr, end):
if curr > end or curr == 32:
return 0

15.

3) Если curr равно end - значит число пришло в конечное, считаем такую программу,
возвращаем функцией единицу.
def f(curr, end):
if curr > end or curr == 32:
return 0
if curr == end:
return 1

16.

4) Если curr меньше end, то нужно произвести все возможные команды с числом curr,
вызываем все функции уже от измененного числа и складываем все вызовы.
Складываем для того, чтобы посчитать количество команд, если число меньше end, то
функции будут продолжать вызываться, если превысит, то функция будет равна 0,
если придёт в конечное, то будет 1. В конце концов, если всё это расписать, то у нас
получится длинная сумма нулей и единиц, которая будет равна количеству программ.
def f(curr, end):
if curr > end or curr == 32:
return 0
if curr == end:
return 1
if curr < end:
return f(curr + 2, end) + f(curr + 4, end)

17.

5) Начинаем выводить ответ, так как нужно обязательно пройти через 27 и 29, то
сначала посчитает, кол-во путей из 9 в 27, потом из 27 в 29 и из 29 в 37. Все
полученные значения перемножим и получим ответ:
def f(curr, end):
if curr > end or curr == 32:
return 0
if curr == end:
return 1
if curr < end:
return f(curr + 2, end) + f(curr + 4, end)
print(f(9, 27) * f(27, 29) * f(29, 37))
275
ответ

18.

разбор решения в excel
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом
является число 35, при этом траектория вычислений содержит число 10 и не
содержит 17?
Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять
из чисел 8, 16, 17.

19.

1) Создаём табличку, в первом столбце пишем все числа, через которые можем
проходить, в следующих двух столбцах будем хранить количество путей
через каждую команду, в последнем будем хранить количество путей в
каждое число. Изначально ставим единице результат 1, так как из неё
начинаем путь:

20.

2) Заполняем команды, для +1 достаточно поставить в клетку результат
предыдущего числа, протягиваем формулу до конца:

21.

3) Заполняем умножение, через формулу проверяем чётное ли число, если да,
то с помощью функции ВПР находим результат нужного числа, протягиваем
формулу по всему столбцу:

22.

4) В результат берём сумму двух столбцов:

23.

5) Так как нужно обязательно проходить через 10, то копируем всё на новый лист,
начиная с 10 и повторяем все эти действия (Умножение начинаем заполнять
только с 20, так как 10 - минимальное значение на листе:
ответ
98

24.

1
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
A. Прибавить 1
B. Прибавить 2
C. Прибавить 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют число 5 в число 11, и при этом
траектория вычислений содержит число 7?
Траектория вычислений программы – это последовательность результатов выполнения
всех команд программы. Например, для программы ACB при исходном числе 7
траектория состоит из чисел 8, 11, 13.
пояснение
ответ
14

25.

1
f = {5: 1}
for i in range(6, 12):
f[i] = 0
f[i] += f[i - 1]
if i - 2 in f:
f[i] += f[i - 2]
if i - 3 in f:
f[i] += f[i - 3]
if i == 7:
for j in range(5, i):
f[j] = 0
print(f[11])

26.

2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Умножить на 3
C. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 13 результатом является
число 45, и при этом траектория вычислений не содержит число 16?
пояснение
ответ
3

27.

2
f = {13: 1}
for i in range(14, 46):
f[i] = 0
if i - 2 in f:
f[i] += f[i - 2]
if i % 3 == 0 and i // 3 in f:
f[i] += f[i // 3]
if i % 2 == 0 and i // 2 in f:
f[i] += f[i // 2]
if i == 16:
f[i] = 0
print(f[45])

28.

3
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 5
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 42 результатом
является число 9, и при этом траектория вычислений содержит числа 23 и 22, но не
содержит число 32?
пояснение
1160
ответ

29.

3
f = {42: 1}
for i in range(41, 8, -1):
f[i] = 0
f[i] += f[i + 1]
if i + 5 in f:
f[i] += f[i + 5]
if i == 23:
for j in range(i + 1, 43):
f[j] = 0
if i == 22:
for j in range(i + 1, 43):
f[j] = 0
if i == 32:
f[i] = 0
print(f[9])

30.

4
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Прибавить 1
В. Прибавить 3
С. Возвести в квадрат
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом
является число 26, при этом траектория вычислений содержит число 20 и не
содержит числа 16?
Траектория вычислений программы — это последовательность результатов
выполнения всех команд программы.
Например, для программы СВА при исходном числе 4 траектория будет состоять из
чисел 16, 19, 20.
пояснение
ответ
936

31.

4
f = {3: 1}
for i in range(4, 27):
f[i] = 0
f[i] += f[i - 1]
if i - 3 in f:
f[i] += f[i - 3]
if i ** 0.5 == int(i ** 0.5) and i ** 0.5 in f:
f[i] += f[i ** 0.5]
if i == 20:
for j in range(3, i):
f[j] = 0
if i == 16:
f[i] = 0
print(f[26])

32.

5
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Найти целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом
является число 1 и при этом траектория вычислений содержит число 8?
Траектория вычислений программы - это последовательность результатов
выполнения всех команд программы.
Например, для программы ABB при исходном числе 10 траектория состоит из чисел
9, 4, 2.
пояснение
288
ответ

33.

5
f = {30: 1}
for i in range(29, 0, -1):
f[i] = 0
f[i] += f[i + 1]
if i * 2 in f:
f[i] += f[i * 2]
if i * 2 + 1 in f:
f[i] += f[i * 2 + 1]
if i == 8:
for j in range(i + 1, 31):
f[j] = 0
print(f[1])

34.

6
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Умножить на 3
C. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 13 результатом
является число 45, и при этом траектория вычислений не содержит число 16?
пояснение
ответ
3

35.

6
def f(curr, end):
if curr > end or curr == 16:
return 0
if curr == end:
return 1
if curr < end:
return f(curr + 2, end) + f(curr * 3, end) + f(curr * 2, end)
print(f(13, 45))

36.

7
Исполнитель преобразует число на экране. У исполнителя есть три команды,
которые обозначены латинскими буквами:
A. Прибавить 2
B. Возвести в квадрат
C. Возвести в куб
Программа для исполнителя – это последовательность команд.
Команда А прибавляет к числу 2. Например, из числа 68 получится число 68 + 2 =
70.
Команда B возводит число в квадрат. Например, из числа 9 получится число 9^2 =
81.
Команда C возводит число в куб. Например, из числа 4 получится число 4^3 = 64.
Сколько существует программ, для которых при исходном числе 10 результатом
является число 1000?
пояснение
ответ
13

37.

7
def f(curr, end):
if curr > end:
return 0
if curr == end:
return 1
if curr < end:
return f(curr + 2, end) + f(curr ** 2, end) + f(curr ** 3, end)
print(f(10, 1000))

38.

8
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые
обозначены латинскими буквами:
А. Вычесть 1
В. Вычесть 2
С. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом
является число 3, при этом траектория вычислений не содержит чисел 9 и 16?
Траектория вычислений программы — это последовательность результатов выполнения
всех команд программы.
Например, для программы СВА при исходном числе 13 траектория будет состоять из
чисел 4, 2, 1.
пояснение
ответ
180

39.

8
def f(curr, end):
if curr < end or curr in (9, 16):
return 0
if curr == end:
return 1
if curr > end:
return f(curr - 1, end) + f(curr - 2, end) + f(curr // 3, end)
print(f(19, 3))

40.

9
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым
присвоены номера:
1. Вычти сумму всех цифр числа
2. Найди целую часть от деления на 2
3. Вычти 1
Первая из них уменьшает число на экране на сумму всех его цифр, вторая заменяет
число на экране на целую часть от деления числа на 2, а третья уменьшает число на
единицу.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 40 результатом
является число 10, и при этом траектория вычислений содержит число 25?
Траектория вычислений программы – это последовательность результатов выполнения
всех команд программы. Например, для программы 1223 при исходном числе 10
траектория состоит из чисел 9, 4, 2, 1.
пояснение
ответ
247

41.

9
def f(curr, end):
if curr < end:
return 0
if curr == end:
return 1
if curr > end:
return f(curr - sum(map(int, str(curr))), end) + f(curr // 2,
end) + f(curr - 1, end)
print(f(40, 25) * f(25, 10))

42.

10
Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе
счисления. У исполнителя есть две команды, которым присвоены номера:
1. Умножь на 2
2. Умножь на 2 и прибавь 1
Сколько различных результатов можно получить из исходного числа 1 после
выполнения программы, содержащей ровно 15 команд?
пояснение
32768
ответ

43.

10
res = set()
# множество для значений
def f(curr, step):
if step == 15:
# если сделано 15 команд, добавляем число во
множество
res.add(curr)
else: # иначе производим все другие команды
f(curr * 2, step + 1)
f(curr * 2 + 1, step + 1)
f(1, 0) # вызываем функцию от единицы, заполняем множество
print(len(res)) # выводим длину множества

44.

1
1
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 3
2. Умножить на 2
Первая из них увеличивает число на экране на 3, вторая увеличивает число вдвое.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является
число 63, и при этом траектория вычислений содержит число 27?
Траектория вычислений программы – это последовательность результатов выполнения
всех команд программы.
Например, для программы 122 при исходном числе 13 траектория состоит из чисел 16,
32, 64.
пояснение
30
ответ

45.

1
1
1) Для +3:
2) Для *2:

46.

1
1
3) Сумма
4) Из 27 в
63: