495. Замораживание Фибоначчи

Последовательность чисел Фибоначчи (0, 1, 1, 2, 3, 5, 8, 13, 21, ....) определяется рекуррентным соотношением:

f₀ = 0, f₁ = 1,

f_i = f_i-1 + f_i-2, i ³ 2

Следует написать программу, которая вычисляет числа Фибоначчи.

Вход. Каждая строка содержит целое неотрицательное число n (n £ 5000).

Выход. Для каждого входного n вывести n – ое число Фибоначчи в соответствии с ниже приведенным форматом.

Пример входа	Пример выхода
5 7 11	The Fibonacci number for 5 is 5 The Fibonacci number for 7 is 13 The Fibonacci number for 11 is 89

РЕШЕНИЕ

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

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

Поскольку n £ 5000, то для нахождения f_n следует воспользоваться классом BigInteger. Найдем и запомним в массиве m все значения f_n (0 £ n £ 5000) и для каждого входного n будем выводить m[n] = f_n.

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

Вычислим все значения f_n (0 £ i £ 5000) и занесем их в массив m[5001]. Поскольку f₅₀₀₀ содержит не более 1100 десятичных знаков, то установим MAXLENGTH = 1100.

#define MAXLENGTH 1100

BigInteger m[5001];

Положим m[1] = 1 и воспользуемся рекуррентной формулой m[i] = m[i -1] + m[i - 2].

m[1] = BigInteger(1);

for(i = 2; i < 5001; i++)

m[i] = m[i-1] + m[i-2];

Для каждого входного значения n выводим f_n = m[n] в соответствии с требуемым форматом.

while(scanf("%d",&n) == 1)

printf("The Fibonacci number for %d is ",n),m[n].print();

Java реализация

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

BigInteger fib[] = new BigInteger[5001];

fib[0] = BigInteger.ZERO;

fib[1] = BigInteger.ONE;

for(int i = 2; i <= 5000; i++)

fib[i] = fib[i-1].add(fib[i-2]);

while(con.hasNextInt())

{

int n = con.nextInt();

System.out.println("The Fibonacci number for " + n +

" is " + fib[n]);

}

con.close();

}

}