Последовательность Фибоначчи (#3258)

Анализ алгоритма

В задаче следует найти $n$ -ое число Фибоначчи. При $n \leq 40$ по времени пройдет рекурсивная реализация. Последовательность Фибоначчи имеет вид:

Наибольшим числом Фибоначчи, которое помещается в тип int является $f_{46} = 1836311903$ . При $n \leq 40$ достаточно использовать тип int.

Пусть функция fib(n) вычисляет $n$ -ое число Фибоначчи. Тогда имеем следующее рекуррентное соотношение:

$f ib (n) = ⎩ ⎨ ⎧ 01 f ib (n - 1) + f ib (n - 2) if n = 0 if n = 1 otherwise$

Реализация алгоритма

Функция fib вычисляет $n$ -ое число Фибоначчи.

int fib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Основная часть программы. Читаем значение $n$ и выводим fib(n).

scanf("%d", &n);
printf("%d\n", fib(n));

Java реализация

import java.util.*;

public class Main
{
    static int f(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return f(n-1) + f(n - 2);
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        System.out.println(f(n));
        con.close();
    }
}

Python реализация – мемоизация

Функция fib вычисляет $n$ -ое число Фибоначчи.

def fib(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]

n = int(input())
dp = (n + 1) * [-1]
dp[0] = 0
dp[1] = 1
print(fib(n))

Python реализация – мемоизация 2

arr = {}

def fib(n):
    if (n == 0): return 0
    if (n == 1): return 1
    if n not in arr:
        arr[n] = fib(n - 1) + fib(n - 2)
    return arr[n]

n = int(input())
print(fib(n))

Python реализация – мемоизация 3

arr = {0: 0, 1: 1}

def fib(n):
    if arr.get(n) is None:
        arr[n] = fib(n - 1) + fib(n - 2)
    return arr[n]

n = int(input())
print(fib(n))

Python реализация – TLE

Функция fib вычисляет $n$ -ое число Фибоначчи.

def fib(n):
    if (n == 0): return 0
    if (n == 1): return 1
    return fib(n - 1) + fib(n - 2)

n = int(input())
print(fib(n))