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 T, indicando o número de casos de teste. Cada caso de teste contém um único inteiro N(0 \geq N \geq 40), 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 T, número de casos de teste, e em cada caso leia um inteiro N com 0 \le N \le 40. Para cada N devemos imprimir o N-ésimo termo da série de Fibonacci, definida por
F_0 = 0,\quad F_1 = 1,\quad F_i = F_{i-1} + F_{i-2}\\ (i \ge 2).
Como F_{40} cabe em um inteiro de 32 bits, usaremos unsigned long para garantir capacidade suficiente.

Passo 2

Vamos pré-calcular todos os termos de F_0 até F_{40} usando programação dinâmica. Declaramos um vetor fib[41] e inicializamos
fib[0] \(=0\);
fib[1] \(=1\);
Em seguida, para i de 2 até 40, fazemos
fib[i] = fib[i-1] + fib[i-2];
assim temos todos os valores prontos em O(40).

Passo 3

No main lemos T com scanf("%d", &T);, depois usamos um laço while (T--) para ler cada N e já imprimir 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;
}

Exercícios relacionados