Fibonacci number#2292

Fibonacci number (Editorial)

Since $n \leq 1 0^{4}$ n ≤ 10^4, computing $F (n)$ requires the use of arbitrary-precision arithmetic or, for example, programming languages such as Java or Python.

Сompute the Fibonacci numbers from $1$ to $1 0^{4}$ 10^4 and store them in an array $f ib$ . Then, for each input value $n$ print $f ib [n]$ .

Java implementation

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 implementation – recursion with memoization

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 implementation

Initialize the first two Fibonacci numbers: $F (1) = 1. F (2) = 1$ F(1) = 1. F(2) = 1.

f1, f2 = 1, 1

Create a list $f ib$ to store the Fibonacci numbers. The value $F (0) = 0$ F(0) = 0 is added intentionally so that the indexing matches the problem statement.

fib = [0, f1, f2]

Compute the Fibonacci numbers up to $F (10002)$ .

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

Read the number of test cases $t$ .

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

Read the input value $n$ and print $F (n)$ .

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