fib = [None] * 997

def fibonacci_ver1(n: int):
    """ версия 1 Рекурсивная функция расчета n-го числа Фибоначчи
    Реально вычисляет до 42 числа и скорость падает логарифмически
    f(20) считалось 0.006с , f(40)  считалось 48с , f(42)  считалось 130с
    """
    return fibonacci_ver1(n - 1) + fibonacci_ver1(n - 2)  if n > 2 else 1 # реккурентная формула


def fibonacci_ver2(n: int):
    """ версия 2 применение методов динамического программирования для расчета n-го числа Фибоначчи
    вычисляет очень большие числа с очень большой скоростью
    f(20) считалось 4.8e-05с , f(40)  считалось 2.5e-05с , f(42)  считалось 2.6e-05с
    """

    fib = [None] * (n + 1)
    fib[:2] = [0, 1]
    for k in range(2, n+1):
        fib[k] = fib[k - 1] + fib[k - 2]
    return fib[k]

def fibonacci_ver3(n: int):
    """ версия 3 Рекурсивная функция расчета n-го числа Фибоначчи с кэшированием в список
    начиная где-то с 50-го числа скорость логарифмически растет и обгоняет второй, но орграничено глубиной 996
    f(20) считалось 4.83e-05с , f(40)  считалось 4.1e-05с , f(42)  считалось 4.37e-05с
    """
    if fib[n] is not None:  #крайний случай
        return fib[n]
    elif n < 2:
        fib[n] = n
        return fib[n]
    else:
        fib[n] = fibonacci_ver3(n - 1) + fibonacci_ver3(n - 2)
        return fib[n]


def fibonacci_ver4(n: int):
    """ версия 4 цикл и кортеж двух переменных-самый быстроходный и считает любое число без органичений
    f(20) считалось 9.93e-06с , f(40)  считалось 6.2.e-06с , f(42)  считалось 7.62.e-06
    """
    a = b = 1
    for i in range(n - 2):
        a, b = b, a+b
    return b
