❤️Пока вы набираете лайки, делюсь кодами для решения сегодняшних задач

25 мая25 мая

1 мин

Задача 1️⃣ — прямая рекурсия def F(n): if n == 1: return 1 # база: F(1) = 1 if n % 2 == 0: return n + F(n-1) # если n чётное: F(n) = n + F(n-1) return 2 * F(n-2) # если n нечётное и n > 1: F(n) = 2×F(n-2) print(F(24)) # ответ: 2072 Метод: обычная рекурсия — функция вызывает саму себя напрямую, значения не кешируются. Задача 2️⃣ — рекурсия с увеличением лимита стека import sys sys.setrecursionlimit(250000) # увеличиваем лимит глубины рекурсии (по умолчанию 1000) def F(n): if n < 10: return 1 # база: F(n) = 1 при n < 10 return (n + 3) * F(n-3) # рекуррентность: F(n) = (n+3) × F(n-3) print((F(247563)//519 - 477 * F(247560)) / F(247557)) # ответ: 1431 Метод: рекурсия с принудительным увеличением лимита стека — нужно, так как глубина вызовов ~82000. Задача 3️⃣ — рекурсия с кешированием (lru_cache) from functools import * @lru_cache() # декоратор кеширует результаты — каждое значение считается один раз def G(n): if n >= 250000: re

Задача 1️⃣ — прямая рекурсия

def F(n):

if n == 1: return 1 # база: F(1) = 1

if n % 2 == 0: return n + F(n-1) # если n чётное: F(n) = n + F(n-1)

return 2 * F(n-2) # если n нечётное и n > 1: F(n) = 2×F(n-2)

print(F(24)) # ответ: 2072

Метод: обычная рекурсия — функция вызывает саму себя напрямую, значения не кешируются.

Задача 2️⃣ — рекурсия с увеличением лимита стека

import sys

sys.setrecursionlimit(250000) # увеличиваем лимит глубины рекурсии (по умолчанию 1000)

def F(n):

if n < 10: return 1 # база: F(n) = 1 при n < 10

return (n + 3) * F(n-3) # рекуррентность: F(n) = (n+3) × F(n-3)

print((F(247563)//519 - 477 * F(247560)) / F(247557)) # ответ: 1431

Метод: рекурсия с принудительным увеличением лимита стека — нужно, так как глубина вызовов ~82000.

Задача 3️⃣ — рекурсия с кешированием (lru_cache)

from functools import *

@lru_cache() # декоратор кеширует результаты — каждое значение считается один раз

def G(n):

if n >= 250000: return n // 20 + 45 # база для G

return G(n+9) - 2 # G идёт вверх (n+9), поэтому считаем сверху вниз

@lru_cache()

def F(n):

if n >= 25: return F(n-6) + 4137 # рекуррентность для F

return 7 * (G(n-9) - 40) # база для F через G

for n in range(260000, 1, -1): G(n) # заполняем кеш G сверху вниз (от большого к малому),

# иначе рекурсия уйдёт слишком глубоко

for n in range(1000): F(n) # заполняем кеш F снизу вверх

print(F(680)) # ответ: 153727

Метод: рекурсия с мемоизацией через lru_cache — результаты сохраняются, повторные вызовы берутся из кеша; порядок предварительного заполнения кеша важен, чтобы избежать переполнения стека.

Задача 4️⃣ — итеративное заполнение массива (динамическое программирование)

F = [0] * 7000 # массив для хранения значений F(0)..F(6999)

for n in range(7000):

if n < 10: F[n] = n # база: F(n) = n при n < 10

else: F[n] = 3*n + F[n-3] # рекуррентность: F(n) = 3n + F(n-3)

print((F[6250] + 2*F[6244]) // F[6238]) # вычисляем выражение по готовому массиву

# ответ: 3

Метод: итеративное динамическое программирование — значения заполняются в цикле снизу вверх, рекурсии нет, переполнение стека невозможно.

С меня решение, с тебя ЛАЙК!!❤️