Число Фібоначчі#2292

Число Фібоначчі (Розбір)

Оскільки $n \leq 1 0^{4}$ n ≤ 10^4, для обчислення $F (n)$ необхідно використовувати довгу арифметику або, наприклад, мови програмування Java або Python.

Обчислимо числа Фібоначчі від $1$ до $1 0^{4}$ 10^4 і збережемо їх у масиві $f ib$ . Потім для кожного вхідного значення $n$ виведемо елемент $f ib [n]$ .

Java реалізація

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger fib[] = new BigInteger[10001];
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    fib[2] = fib[1] = BigInteger.ONE;
    for(int i = 3; i < 10001; i++)
      fib[i] = fib[i-1].add(fib[i-2]);
    
    int tests = con.nextInt();
    for(int i = 0; i < tests; i++)
    {
      int n = con.nextInt();
      System.out.println(fib[n]);      
    }
    con.close();
  }
}

Java

Java реалізація – рекурсія з запам'ятовуванням

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger fib[] = new BigInteger[10001];    
  static BigInteger MUNIS1 = new BigInteger("-1");

  static BigInteger f(int n)
  {
    if (n <= 2) return BigInteger.ONE;
    if (fib[n].compareTo(MUNIS1) != 0) return fib[n];
    return fib[n] = f(n-1).add(f(n - 2));
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    for(int i = 0; i < 10001; i++) fib[i] = MUNIS1;
    int tests = con.nextInt();
    for(int i = 0; i < tests; i++)
    {
      int n = con.nextInt();
      System.out.println(f(n));      
    }
    con.close();
  }
}

Java

Python реалізація

Ініціалізуємо перші два числа Фібоначчі: $F (1) = 1. F (2) = 1$ F(1) = 1. F(2) = 1.

f1, f2 = 1, 1

Створюємо список $f ib$ , у якому будемо зберігати числа Фібоначчі. Значення $F (0) = 0$ F(0) = 0 додаємо спеціально, щоб індексація співпадала з умовою задачі.

fib = [0, f1, f2]

Обчислюємо числа Фібоначчі, аж до $F (10002)$ .

for i in range(10000):
  add = f1 + f2
  fib.append(add)
  f1, f2 = f2, add

Читаємо кількість тестів $t$ .

t = int(input())
for i in range(t):

Читаємо вхідне значення $n$ і виводимо $F (n)$ .

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