Faça um programa em C (vai ser rodado no programa De C++) que leia um valor e apresente o número de Fibonacci correspondente a este valor lido. Lembre-se que os 2 primeiros elementos da série de Fibonacci são 0 e 1 e cada termo é a soma dos 2 anteriores a ele. Todos os valores de Fibonacci calculados neste problema devem caber em um inteiro padrão (int)
Entrada
A primeira linha de cada entrada contém um inteiro
, indicando o número de casos de teste. Cada caso de teste contém um único inteiro
, correspondente ao N -ésimo termo da série de Fibonacci.
OBS.: O vetor deve conter inteiros longos sem sinal
Passo 1
O enunciado pede um programa em C que leia um inteiro
, número de casos de teste, e em cada caso leia um inteiro
com
. Para cada
devemos imprimir o
-ésimo termo da série de Fibonacci, definida por
Como
cabe em um inteiro de 32 bits, usaremos
unsigned long
para garantir capacidade suficiente.Passo 2
Vamos pré-calcular todos os termos de
até
usando programação dinâmica. Declaramos um vetor
fib[41]
e inicializamosfib[0] \(=0\);
fib[1] \(=1\);
Em seguida, para
i
de 2 até 40, fazemosfib[i] = fib[i-1] + fib[i-2];
assim temos todos os valores prontos em
.
Passo 3
No com e já imprimir
main
lemos
scanf("%d", &T);
, depois usamos um laço while (T--)
para ler cada
fib[N]
com printf("%lu ", fib[N]);
.Resposta
#include <stdio.h>
int main() {
int T, N;
scanf("%d", &T);
unsigned long fib[41];
fib[0] \(=0\);
fib[1] \(=1\);
for (int i \(=2\); i <\(=40\); i\(++\)) {
fib[i] = fib[i-1] + fib[i-2];
}
while (T--) {
scanf("%d", &N);
printf("%lu
", fib[N]);
}
return 0;
}