Задание из ЕГЭ по информатике

В егэ будет только исполнитель редактор

Для решения этой задачи мы можем использовать метод динамического программирования, чтобы найти количество различных путей, которые можно использовать для достижения числа 17 из числа 43, не проходя через числа 23 и 20. Мы будем двигаться от числа 17 к числу 43, добавляя числа 1, 3 и 4, и будем отслеживать количество способов достичь каждого числа.

Давайте определим ( P(n) ) как количество программ, которые преобразуют число ( n ) в 17. Тогда:

[ P(17) = 1 ] [ P(18) = P(17) ] [ P(19) = P(18) ] [ P(20) = 0 ] (так как мы не можем проходить через 20) [ P(21) = P(18) + P(19) ] [ P(22) = P(19) + P(21) ] [ P(23) = 0 ] (так как мы не можем проходить через 23) [ P(24) = P(21) ] [ P(25) = P(22) + P(24) ] [ … ] [ P(43) = P(40) + P(42) + P(39) ]

Таким образом, мы продолжаем вычислять ( P(n) ) для каждого значения ( n ) от 17 до 43, не учитывая значения 20 и 23. В конце концов, ( P(43) ) даст нам искомое количество программ. Не забудьте, что если ( n ) равно 20 или 23, то ( P(n) ) должно быть равно 0, так как эти числа не должны встречаться в траектории вычислений.

Это решение предполагает, что вы знакомы с основами динамического программирования. Если вам нужна дополнительная помощь в понимании этого метода или решении задачи, пожалуйста, дайте мне знать!

 def calculate_ways(): 
    ways = [0] * 44  # Создаем список для хранения количества способов 
    ways[17] = 1  # Начальное условие 
 
    for i in range(18, 44): 
        if i == 23 or i == 20:  # Пропускаем числа 23 и 20 
            continue 
        ways[i] = ways[i - 1] + ways[i - 3] + ways[i - 4] 
 
    return ways[43]  # Возвращаем количество способов достичь 43 
 
# Выводим результат 
print(calculate_ways())