Как решать эти странные задания с ЕГЭ? (№16)

Question

В заданиях #16, которые составляют малоизвестные личности мне часто встречаются задачи, в которых идёт переполнение стека (я вот сомневаюсь, что на экзамене для школьников может быть задание на рекурсию, которую рвёт на части даже если передать в неё '1'). Мне интересно, это ошибка составителя задания или это я что-то делаю не так.

from functools import lru_cache
from sys import setrecursionlimit

setrecursionlimit(3000)


@lru_cache()
def F(n: int):
    if n >= 10000:
        return n
    elif n % 2:
        return F(n + 2) + 1
    else:
        return F(n + 2) - 3


print(F(4))

Answer 1

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

F(94) = F(96) - 3 = F(98) - 6 …
F(80) = F(82) - 3 = F(84) - 6 …

Очевидно, что с нечётным n мы никогда не столкнёмся, тогда имеем:

F(94) - F(80) = (F(10000) - ((10000-94)/2) * 3) - (F(10000) - ((10000 - 80))/2 * 3)) =
(10000 - 14859) - (10000 - 14880) = 21

Answer 2

Есть альтернативный вариант, чтобы не прибегать к аналитическому решению. В своём коде вы используете lru_cache, который можно предварительно заполнить при помощи цикла:

from functools import lru_cache


@lru_cache(None)
def F(n):
    if n >= 10000:
        return n
    elif n % 2:
        return F(n + 2) + 1
    else:
        return F(n + 2) - 3


for n in range(10000, 1, -1):
    print(F(n))

print(F(94)-F(80))

После этого лимит рекурсии не будет превышаться

Answer 3

Моё решение будет длинным, но работает быстро:

import os
import time

def F(n, memo={}):
    if n in memo:
        return memo[n]
    stack = [n]
    while stack:
        current = stack.pop()
        if current in memo:
            continue
        if current >= 10000:
            memo[current] = current
        elif current % 2 == 0:
            if current + 2 in memo:
                memo[current] = memo[current + 2] - 3
            else:
                stack.append(current)
                stack.append(current + 2)
        else:
            if current + 2 in memo:
                memo[current] = memo[current + 2] + 1
            else:
                stack.append(current)
                stack.append(current + 2)
    return memo[n]

start_time = time.time()
result = F(94) - F(80)
end_time = time.time()

execution_time = end_time - start_time

print("Result:", result)
print("Execution time:", execution_time, "seconds")
os.system("pause")

Результат:

Result: 21
Execution time: 0.0023860931396484375 seconds
Press any key to continue . . .

БЛОГ НА HUSL

Как решать эти странные задания с ЕГЭ? (№16)

Ответы (3 шт):