Послідовність Фібоначчі (#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))