Статья Автор: Лебедев Дмитрий

(The Last Inch) КЕГЭ- 16+23. Модель решения

Задание 16 (Тренировочный вариант №1)

Задание 23 (Тренировочный вариант №1)

Эти задания удобно решать в "связке", используя очень похожие коды. 
Для решения заданий будем применять "простой код" использующий "динамическо-рекурсивный" метод


 
решение задания 16 решение задания 23
def f(n) : # подпрограмма рекурсии
    if n < 6 : return n
    if n in dp : return dp[n]
    dp[n] = (3 * n - 2) * f(n - 5)
    return dp[n]
def f(n) : # подпрограмма рекурсии
    # проверка принадлежности отрезку
    if (n - sf[0])*(n- sf[1]) > 0 :   return 0
    if n in dp : return dp[n]
    dp[n] = f(n - 2) + f(n -3) + f(n // 3)
    return dp[n]

 
dp = {} # инициализируем словарь значений
N = 20568 # целевая точка (для удобства)
for i in range(N+1): # заполнение всего списка значений
    f(i) # вычисление очередного значения (одного !!!)
ans = (dp[N] - 51702 * dp[N - 5])/ dp[N - 15] #  вычисление результата
print(ans) # вывод результата
# Запуск 1: 48 -> 25
sf = [48 , 25]
# границы отрезка
dp = {sf[1] : 1, 15 : 0}
a = f(sf[0])
# запуск от старта
# Запуск 2: 25 -> 17
sf = [25 , 17] 
# границы отрезка
dp = {sf[1] : 1, 15 : 0}
b = f(sf[0]) 
# запуск от старта
# Запуск 3: 17 -> 3
sf = [17 , 4] 
# границы отрезка
dp = {sf[1] : 1, 15 : 0}
c = f(sf[0]) 
# запуск от старта
print(a * b * c, a, b, c)

Основной блок для заданий 23 состоит из "copy-paste" фрагментов (так проще, чем организовывать три запуска). 
В список sf записаны границы исследуемого отрезка в заданном направлении, пропуски обозначены в словаре значение 0.



Печать