2292. Число Фибоначчи

Числа Фибоначчи определяется следующим образом:

F(1) = F (2) = 1

F(n) = F (n – 1) + F (n – 2) для n ≥ 3.

Вычислить n-тое число Фибоначчи.

Вход. В первой строке задано количество тестов t (1 ≤ t ≤ 10³). Каждая из следующих t строк содержит одно число n (1 ≤ n ≤ 10⁴).

Выход. Для каждого теста выведите в отдельной строке соответствующее число Фибоначчи.

Пример входа	Пример выхода
5 1 2 3 4 5	1 1 2 3 5

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

Поскольку n ≤ 10⁴, то для вычисления F(n) следует воспользоваться длинной арифметикой или например, языком программирования Java. Вычислим числа Фибоначчи от 1 до 10⁴, занесем их в массив fib. Далее для каждого входного значения n выведем fib[n].

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

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 реализация – рекурсия с запоминанием

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();

}

}