2. problema de Fibonacci consiste em calcular o n-ésimo número da sequência de Fibonacci, onde a sequência é definida como: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) para ngeqslant 2 Implemente um algoritmo que leia um inteiro N(Nlt 46) e mostre os N primeiros números dessa série usando programação dinâmica . Na programação dinâmica é necessário usar uma tabela (vetor) para armazenar os resultados intermediários , evitando cálculos repetidos . Recomendo utilizar o beecrowd (https://judge beecrowd.com/pt/problems /view/1151) para testar a implementação , lembrando que a solução DEVE envolver o uso de Programação Dinâmica.

Question

2. problema de Fibonacci consiste em calcular o n-ésimo número da sequência de Fibonacci, onde a sequência é definida como: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) para ngeqslant 2 Implemente um algoritmo que leia um inteiro N(Nlt 46) e mostre os N primeiros números dessa série usando programação dinâmica . Na programação dinâmica é necessário usar uma tabela (vetor) para armazenar os resultados intermediários , evitando cálculos repetidos . Recomendo utilizar o beecrowd (https://judge beecrowd.com/pt/problems /view/1151) para testar a implementação , lembrando que a solução DEVE envolver o uso de Programação Dinâmica.

Answer 1

Para resolver esse problema usando programação dinâmica, podemos utilizar uma tabela (vetor) para armazenar os resultados intermediários. Vamos implementar um algoritmo em Python que leia um inteiro N (N < 46) e mostre os N primeiros números da sequência de Fibonacci usando programação dinâmica.```pythondef fibonacci(N): if N <= 0: return [] elif N == 1: return [0] elif N == 2: return [0, 1] # Inicialização da tabela (vetor) para armazenar os resultados intermediários tabela = [0] * (N + 1) tabela[1] = 1 # Preenchimento da tabela com os números da sequência de Fibonacci for i in range(2, N + 1): tabela[i] = tabela[i - 1] + tabela[i - 2] return tabela[2:N+1]# Leitura do valor de N pelo usuárioN = int(input("Digite um inteiro N (N < 46): "))# Cálculo e exibição dos N primeiros números da sequência de Fibonaccisequencia = fibonacci(N)print(sequencia)```Explicação do código:1. A função `fibonacci` recebe um inteiro N como entrada e retorna uma lista com os N primeiros números da sequência de Fibonacci.2. Se N for menor ou igual a 0, a função retorna uma lista vazia.3. Se N for igual a 1, a função retorna uma lista com o número 0.4. Se N for igual a 2, a função retorna uma lista com os números 0 e 1.5. Caso contrário, inicializamos uma tabela (vetor) com tamanho N+1 para armazenar os resultados intermediários.6. Preenchimos a tabela com os números da sequência de Fibonacci, utilizando a fórmula de recorrência dada no enunciado.7. Retornamos a parte da tabela que contém os N primeiros números da sequência de Fibonacci (excluindo o índice 0 e 1).Ao executar o programa, o usuário será solicitado a digitar um inteiro N (menor que 46). Em seguida, o programa calculará e exibirá os N primeiros números da sequência de Fibonacci utilizando programação dinâmica.

Question

Solution

Resposta