Задание 23. Информатика. ЕГЭ. Поляков-7401

Просмотры: 264
Изменено: 24 ноября 2024

(П. Тюрин) У исполнителя имеются две команды, которые обозначены номерами:

  1. Умножить на \(2\)
  2. Прибавить \(3\)

Первая команда умножает число на \(2\), вторая увеличивает его на \(3\). Программа для исполнителя — это последовательность команд. Рассматриваются все программы, в которых при исходном числе \(2\) результатом является число \(70\), причём

а) команда сложения не применяется более двух раз подряд;
б) траектория вычислений проходит либо через числа \(8\) и \(16\), либо через число \(32\) (но не через все три числа одновременно).

Сколько различных чисел содержится во всех таких траекториях вычислений?

Решение:

Python


p = []

def f(n, t, a):
    global p
    tmp_a = []
    for x in a:
        tmp_a.append(x)
    tmp_a.append(n)
    if n > t:
        return 0
    if n == t:
        p.append(tmp_a)
        return 1
    return f(2 * n, t, tmp_a) + f(n + 3, t, tmp_a)

f(2, 70, [])

# print(p) # Посмотреть на все траектории

p1 = []

for x in p:
    if not(8 in x and 16 in x and 32 in x):
        p1.append(x)

# print(p1) # Посмотреть на все траектории, которые не проходят одновременно через 8, 16 и 32

p2 = []

for x in p1:
    t = [b - a == c - b == d - c == 3 for a, b, c, d in zip(x, x[1:], x[2:], x[3:])]
    if not any(t):
        p2.append(x)

# print(p2) # Печать всех траекторий, удовлетворяющих условию задачи
            
s = set(x for y in p2 for x in y)

print(len(s))

Ответ: \(12\)