2292. Fibonacci number

The Fibonacci numbers are defined as follows:

F(1) = 1,

F(2) = 1,

F(n) = F (n – 1) + F (n – 2), n ≥ 3

Compute the n-th Fibonacci number.

Input. The first line contains the number of test cases t (1 ≤ t ≤ 10³).  Each of the next t lines contains one integer n (1 ≤ n ≤ 10⁴).

Output. For each test case, print the corresponding Fibonacci number on a separate line.

Sample input	Sample output
5 1 2 3 4 5	1 1 2 3 5

SOLUTION

Fibonacci numbers

Algorithm analysis

Since n ≤ 10⁴, 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 10⁴ and store them in an array fib. Then, for each input value n print fib[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 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();

}

}

Python implementation

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

f1, f2 = 1, 1

Create a list fib to store the Fibonacci numbers. The value 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])