Количество результатов выполнения программ —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#11538

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

Удвоить
Удвоить и прибавить $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

Ошибка.
Попробуйте повторить позже

Задача 2#28819

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

1. Прибавить $2$

2. Умножить на $2$ и прибавить $1$

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

Сколько различных результатов можно получить из исходного числа $6$ после выполнения программы, содержащей ровно $12$ команд?

Показать ответ и решение

Решение 1 (Рекурсия)

ans = set()
def f(start, com):
    global ans
    if com == 0:
        ans.add(start)
        return 0
    f(start + 2, com - 1)
    f(start * 2 + 1, com - 1)
f(6, 12)
print(len(ans))

Решение 2 (Динамика)

ans = set()
ans.add(6)
for cnt in range(12):
    can_get = set()
    for i in ans:
        can_get.add(i + 2)
        can_get.add(i * 2 + 1)
    ans = can_get
print(len(ans))

Ответ: 1286

Ошибка.
Попробуйте повторить позже

Задача 3#30482

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

1. Прибавить 1

2. Умножить на 2

3. Прибавить 4

Программа для исполнителя — это последовательность команд.

Сколько существует различных результатов выполнения программ, содержащих 8 команд и начинающих свою работу из 2.

Показать ответ и решение

Решение 1 (Рекурсия)

def f(st, count, end_count):
    global A # объявляем А глобальной переменной,
    # чтобы добавлять туда новые элементы внутри функции
    if count == end_count:
        A.add(st)
    else:
        f(st + 1, count + 1, end_count)
        f(st * 2, count + 1, end_count)
        f(st + 4, count + 1, end_count)
A = set() # Лучший вариант для данной задачи, так как в множестве
# не повторяются элементы
f(2, 0, 8)
print(len(A))

Решение 2 (Динамика)

ans = set()
ans.add(2)
for operations in range(8):
    can_get = set()
    for i in ans:
        can_get.add(i + 1)
        can_get.add(i * 2)
        can_get.add(i + 4)
    ans = can_get
print(len(ans))

Ответ: 189

Ошибка.
Попробуйте повторить позже

Задача 4#30483

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

1. Вычесть 10

2. Умножить на -2

3. Модуль числа

Программа для исполнителя — это последовательность команд.

Сколько существует различных результатов выполнения программ, содержащих 10 команд и начинающих свою работу из 1. При этом исполнитель не может совершать ходы, которые не изменяют знак числа. Например, из числа 1 нельзя попасть в число 1, но можно в -9 и в -2.

Показать ответ и решение

Решение 1 (Рекурсия)

def f(st, count, end_count):
    global A
    if count == end_count:
        A.add(st)
    else:
        if st > 0:
            f(st * (-2), count + 1, end_count)
            if st < 10:
                f(st - 10, count + 1, end_count)
        if st < 0:
            f(st * (-1), count + 1, end_count)
            f(st * (-2), count + 1, end_count)


A = set()  # Лучший вариант для данной задачи,
# в множестве не повторяются элементы
f(1, 0, 10)
print(len(A))

Решение 2 (Динамика)

ans = set()
ans.add(1)
for operations in range(10):
    can_get = set()
    for i in ans:
        if i > 0:
            can_get.add(i * (-2))
            if i - 10 < 0:
                can_get.add(i - 10)
        else:
            can_get.add(abs(i))
            can_get.add(i * (-2))
    ans = can_get
print(len(ans))

Ответ: 28

Ошибка.
Попробуйте повторить позже

Задача 5#30484

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

1. Прибавить квадрат числа

2. Прибавить целую часть квадратного корня числа, если корень возможно извлечь

3. Вычесть 12

Программа для исполнителя — это последовательность команд.

Сколько существует различных результатов выполнения программ, содержащих 5 команд и начинающих свою работу из 23. При этом исполнитель не может совершать ходы, которые приводят его в числа кратные 5. Например, из числа 7 можно попасть только в 9 и 56.

Показать ответ и решение

Решение 1 (Рекурсия)

def f(st, count, end_count):
    global A # объявляем А глобальной переменной, чтобы добавлять туда
#новые элементы из функции
    if count == end_count:
        A.add(st)
    else:
        if (st + st ** 2) % 5 != 0:
            f(st + st ** 2, count + 1, end_count)
        if (st - 12) % 5 != 0:
            f(st - 12, count + 1, end_count)
        if st >= 0:
            if (st + int(st ** 0.5)) % 5 != 0:
                f(st + int(st ** 0.5), count + 1, end_count)
A = set()
f(23, 0, 5)
print(len(A))

Решение 2 (Динамика)

ans = set()
ans.add(23)
for operations in range(5):
    can_get = set()
    for i in ans:
        if (i + i ** 2) % 5 != 0:
            can_get.add(i + i ** 2)
        if (i - 12) % 5 != 0:
            can_get.add(i - 12)
        if i >= 0:
            if (i + int(i ** 0.5)) % 5 != 0:
                can_get.add(i + int(i ** 0.5))
    ans = can_get
print(len(ans))

Ответ: 57

Ошибка.
Попробуйте повторить позже

Задача 6#30490

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

1. Прибавить $1$

2. Прибавить $3$

3. Умножить на $3$

Программа для исполнителя — это последовательность команд.

Сколько существует различных результатов выполнения программ, содержащих $10$ команд и начинающих свою работу из $2$ . При этом траектория вычислений исполнителя содержит не более трех нечетных чисел.

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $2$ траектория будет состоять из чисел $3,6,18$ .

Показать ответ и решение

Стоит сказать, что динамическое решение данной задачи получается достаточно трудоемким. Поэтому рекомендуется решать эту задачу с помощью рекурсии.

Решение 1 (Рекурсия)

def f(st, count_odd, count, end_count):
    global A
    if count == end_count and count_odd <= 3:
        A.add(st)
    if count_odd > 3 or count > end_count:
        return
    f(st + 1, count_odd + (st % 2 == 0), count + 1, end_count)
    f(st * 3, count_odd + (st % 2 == 1), count + 1, end_count)
    f(st + 3, count_odd + (st % 2 == 0), count + 1, end_count)
A = set()
f(2, 0, 0, 10)
print(len(A))

Решение 2 (Динамика)

ans, otv = set(), set()
ans.add((2, 0))
for operations in range(10):
    can_get = set()
    for i in ans:
        ch, chet = i
        if chet + (ch + 1) % 2 <= 3:
            can_get.add((ch + 1, chet + (ch + 1) % 2))
        if chet + (ch + 3) % 2 <= 3:
            can_get.add((ch + 3, chet + (ch + 3) % 2))
        if chet + (ch * 3) % 2 <= 3:
            can_get.add((ch * 3, chet + (ch * 3) % 2))
    ans = can_get
for i in ans:
    a, b = i
    otv.add(a)
print(len(otv))

Ответ: 602

Ошибка.
Попробуйте повторить позже

Задача 7#59601

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

1. Прибавить 3

2. Умножить на 4

Программа для исполнителя - это последовательность команд. Сколько существует значений, в которые можно прийти не менее чем за 1, но не более чем за 8 команд из числа 2?

Показать ответ и решение

def f(a, k = 0):
    if 1 <= k <= 8:
        s.add(a)
    elif k > 8:
        return 0

    f(a + 3, k + 1)
    f(a * 4, k + 1)

s = set()
f(2)
print(len(s))

Ответ: 339

Ошибка.
Попробуйте повторить позже

Задача 8#61639

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

1. Прибавить 1.

2. Отнять 2.

3. Умножить на 3.

Первая команда увеличивает число на 1, вторая уменьшает число на 2, третья – умножает на 3. Сколько различных результатов можно получить из исходного числа 2 после выполнения программы, содержащей 20 команд, если известно, что запрещено повторять команду, сделанную на предыдущем шаге.

Показать ответ и решение

Программное решение:

from functools import lru_cache
@lru_cache(None)

def f(a, k, last = 0): #Ввёдем в функцию 2 параметра: ’k’ и ’last’. Параметр ’k’ является счётчиком команд.
    # Параметр ’last’ записывает последнюю выполненную команду для того чтобы две одинаковые команды не совершались друг за другом
    if k == 20:
        s.add(a)
    if k < 20: # Пока количество команд меньше 20, мы изменяем число
        if last == 0:
            f(a+1, k+1, 1)
            f(a-2, k+1, 2)
            f(a*3, k+1, 3)
        if last == 1:
             f(a-2, k+1, 2)
             f(a*3, k+1, 3)
        if last == 2:
            f(a+1, k+1, 1)
            f(a*3, k+1, 3)
        if last == 3:
            f(a+1, k+1, 1)
            f(a-2, k+1, 2)
s = set()
f(2, 0) #Вызываем функцию
print(len(s)) #Выводим количество различных результатов программы

Ответ: 35093

Ошибка.
Попробуйте повторить позже

Задача 9#84012

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

1. Прибавь 3

2. Прибавь 7

3. Прибавь 1

4. Умножь на 2

5. Умножь на 4

6. Умножь на 1.5

Причём команду 6 можно использовать только если число на экране чётное. Программа для исполнителя – это последовательность команд.

Сколько различных результатов можно получить при исходном числе 10 в ходе исполнения программы, содержащей не менее 1, но не более 8 команд, если известно, что совершать можно только команду, чей номер отличен по чётности от номера команды, совершенной на предыдущем шаге (например после команды 2 нельзя использовать команду 4, но можно команду 5)?

Показать ответ и решение

Программное решение:

# Множество различных результатов работы программы

# c — номер команды на предыдущем шаге, причём c = 0.5 для того, чтобы изначально сработали оба условия: и c % 2 != 0, и c % 2 != 1.
# k — счётчик количества совершенных команд
def f(a, c = 0.5, k = 0):
    if 1 <= k <= 8:
        s.add(a)
    elif k > 8:
        return 0
    if c % 2 != 0:
        f(a + 7, 2, k + 1)
        f(a * 2, 4, k + 1)
        if a % 2 == 0: 
            f(int(a * 1.5), 6, k + 1)
    if c % 2 != 1:
        f(a + 3, 1, k + 1)
        f(a + 1, 3, k + 1)
        f(a * 4, 5, k + 1)

s = set()
f(10)
print(len(s))

Ответ: 2232

Ошибка.
Попробуйте повторить позже

Задача 10#84014

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

1. Увеличь на 3

2. Увеличь на 5

3. Умножь на 2

4. Умножь на 3

Программа для исполнителя – это последовательность команд.

Сколько различных результатов можно получить при исходном числе 35 в ходе исполнения программы, содержащей ровно 18 команд, если известно, что нельзя повторять команду с тем же арифметическим действием, что и у сделанной на предыдущем шаге (после умножения нельзя повторять умножение, после сложения нельзя повторять сложение)?

Показать ответ и решение

# Множество различных результатов работы программы
s = set()

# c - номер команды на предыдущем шаге
# k - счётчик количества совершенных команд
def f(a, c=0, k=0):
    if k == 18:
        s.add(a)
        return
    if c != 1 and c != 2:
        f(a + 3, 1, k + 1)
        f(a + 5, 2, k + 1)
    if c != 3 and c != 4:
        f(a * 2, 3, k + 1)
        f(a * 3, 4, k + 1)

f(35)

print(len(s))

Ответ: 90924

Ошибка.
Попробуйте повторить позже

Задача 11#84015

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

1. Увеличь на 6

2. Увеличь на 9

3. Умножь на 3

Программа для исполнителя – это последовательность команд.

Сколько различных результатов можно получить при исходном числе 3 в ходе исполнения программы, содержащей ровно 9 команд, если известно, что повторять можно только первую команду, а вторую и третью - нельзя (после первой команды может идти любая другая, но после второй не может идти вторая, а после третьей - третья)?

Показать ответ и решение

# Множество различных результатов работы программы
s = set()

# c - номер команды на предыдущем шаге
# k - счётчик количества совершенных команд
def f(a, c=0, k=0):
    if k == 9:
        s.add(a)
        return
    f(a + 6, 1, k + 1)
    if c != 2:
        f(a + 9, 2, k + 1)
    if c != 3:
        f(a * 3, 3, k + 1)

f(3)

print(len(s))

Ответ: 292

Ошибка.
Попробуйте повторить позже

Задача 12#84016

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

1. Увеличь на 1

2. Умножь на 2

3. Умножь на 3

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 8 результатом является число 123, если известно, что после второй команды обязательно должна идти третья?

Показать ответ и решение

Программное решение:

# c — номер команды на предыдущем шаге
def f(a, b, c = 0):
    if a > b:
        return 0
    if a == b:
        return 1
    if c == 2:
        return f(a * 3, b, 3)
        
    return f(a + 1, b, 1) + f(a * 2, b, 2) + f(a * 3, b, 3)

print(f(8, 123))

Ответ: 111

Ошибка.
Попробуйте повторить позже

Задача 13#84017

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

1. Увеличь на 8

2. Уменьши на 4

3. Раздели на 2

Причём команду 3 можно применять только для чётных чисел. Программа для исполнителя – это последовательность команд.

Сколько различных натуральных результатов можно получить при исходном числе 16 в ходе исполнения программы, содержащей ровно 10 команд, если известно, что нельзя повторять третью команду, если она была использована на предыдущем шаге.

Показать ответ и решение

Программное решение:

# Множество различных результатов работы программы

# c — номер команды на предыдущем шаге
# k — счётчик количества совершенных команд
def f(a, c = 0, k = 0):
    if k == 10:
        if a >= 1:
            s.add(a)
        return 0
    f(a + 8, 1, k + 1)
    f(a - 4, 2, k + 1)
    if c != 3 and a % 2 == 0:
        f(a // 2, 3, k + 1)

s = set()
f(16)
print(len(s))

Ответ: 67

23.07 Количество результатов выполнения программ