Задача к ЕГЭ по информатике на тему «количество результатов выполнения программ» №1

Просмотров 7 Комментарии 0

Исполнитель ДЮ преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

Удвоить
Удвоить и прибавить $1$
Утроить и прибавить $1$

Первая команда умножает число на экране на $2$ , вторая — умножает его на $2$ , а затем прибавляет $1$ , а третья — умножает его на $3$ , а затем прибавляет $1$ .

Программа для исполнителя ДЮ — это последовательность команд. Сколько различных результатов можно получить из исходного числа $1$ после выполнения программы, содержащей ровно $7$ команд?

# set может хранить только по одному экземпляру каждого числа,
# то есть все числа внутри будут различными
a = set()
# каждая последовательность команд будет содержать 7 команд
# последовательность команд состоит из чисел 1 2 3
# в алфавите 3СС тоже три числа
# необходимо рассмотреть все семиразрядные числа в 3СС
# каждая из них будет представлять последовательность команд
for i in range(3**7):
    t = i # какая-то последовательность команды (в 10СС)
    n = 1 # тут хранится результат работы данной последовательности
    # перевод последовательности команд в 3СС
    # мы сами переназвали команды, теперь *2 это 0-вая команда и тд
    for j in range(7):
        if t % 3 == 0:
            n*=2
        if t%3==1:
            n = n*2 +1
        if t%3==2:
            n = n*3 + 1
        t //= 3
    # добавляем число в множество, если оно там уже есть,
    # то ничего не произойдет
    a.add(n)
print(len(a))

Ответ: 857