Послідовність Фібоначчі (Розбір)

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

Найбільшим числом Фібоначчі, яке вміщується в тип int є

При n \le 40 достатньо використовувати тип даних int.

Нехай функція fib(n) обчислює $n$-е число Фібоначчі. Тоді маємо таке рекурентне співвідношення:

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

Функція 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$.

n = int(input())

Ініціалізуємо список $dp$.

dp = (n + 1) * [-1]
dp[0] = 0
dp[1] = 1

Обчислюємо та виводимо відповідь.

print(fib(n))

Python реалізація — мемоізація 2

arr = {}

Функція fib обчислює $n$-е число Фібоначчі.

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$, обчислюємо та виводимо $fib(n)$.

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

Python реалізація — мемоізація 3

arr = {0:0, 1:1}

Функція fib обчислює $n$-е число Фібоначчі.

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

Основна частина програми. Читаємо значення $n$ та виводимо $fib(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$, обчислюємо та виводимо $fib(n)$.

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