Neste artigo, vamos explorar a solução para o desafio da sequência de Fibonacci, um problema emblemático para estudantes de Ciência da Computação. A sequência de Fibonacci começa com os números 0 e 1, e cada número subsequente é a soma dos dois anteriores. Entretanto, este famoso problema ganha uma roupagem diferente no desafio “Fibonacci, Quantas Chamadas?”. Neste problema, além de calcular o valor da sequência, é preciso também determinar quantas chamadas recursivas são necessárias para chegar a esse resultado.
Vamos explorar a solução para o problema “Fibonacci, Quantas Chamadas?” em JavaScript. Abordaremos a definição do problema, a estratégia de resolução, o código e uma explicação detalhada de como a solução funciona. Este desafio é uma oportunidade para praticar programação e entender como calcular a sequência de Fibonacci de forma eficiente.
Referência do Problema: Fibonacci, Quantas Chamadas? (Beecrowd)
Antes de começar a explorar a solução para o problema “Fibonacci, Quantas Chamadas?” em JavaScript, é importante garantir que você tenha os seguintes pré-requisitos em seu ambiente de desenvolvimento:
Node.js: Certifique-se de que você tenha o Node.js instalado em seu sistema. O código fornecido neste artigo foi testado com a versão do Node.js 18.17.1, mas versões anteriores do Node.js também devem funcionar. Você pode verificar sua versão do Node.js com o comando: node -v
Editor de Código: Qualquer editor de código de sua preferência pode ser usado para escrever e executar o código JavaScript. Alguns exemplos populares incluem Visual Studio Code, Sublime Text e Atom.
Certificar-se de que você atende a esses pré-requisitos é essencial para seguir adiante e implementar a solução apresentada neste artigo.
Quase todos os estudantes de Ciência da Computação em algum momento de seu curso são desafiados com o problema da sequência de Fibonacci. Esta sequência tem como os dois primeiros valores 0 e 1, e cada valor subsequente é a soma dos dois valores imediatamente anteriores. O problema “Fibonacci, Quantas Chamadas?” apresenta uma variação desse desafio, pedindo para calcular o número de chamadas recursivas necessárias para calcular um número na sequência de Fibonacci.
O problema fornece a seguinte definição da sequência de Fibonacci:
O objetivo é calcular o valor de fib(n) e também determinar quantas chamadas recursivas são feitas para chegar a esse resultado. Para fazer isso, o programa deve ser capaz de lidar com vários casos de teste.
Exemplo de entrada
2
5
4
Exemplo de saída
fib(5) = 14 calls = 5
fib(4) = 8 calls = 3
Uma maneira de calcular o número de Fibonacci é através de chamadas recursivas. No entanto, é importante acompanhar o número de chamadas recursivas para atender ao requisito do problema. A solução proposta envolve a criação de uma função que calcula fib(n) e rastreia o número de chamadas recursivas.
O pensamento lógico por trás da solução é simples:
fib(n) seguindo a definição dada.fib(n) e o número de chamadas recursivas.A estrutura básica da função será a seguinte:
function fibonacci(num) {
let calls = 0;
function fib(n) {
calls++;
// Implementação da recursão
}
const result = fib(num);
return `fib(${num}) = ${calls - 1} calls = ${result}`;
}
Aqui está o código em JavaScript que implementa a solução:
import readline from 'readline';
function fibonacci(num) {
let calls = 0;
function fib(n) {
calls++;
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
const result = fib(num);
return `fib(${num}) = ${calls - 1} calls = ${result}`;
}
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.question('Insira o número de casos de teste: ', (numTestCases) => {
const numberOfCases = parseInt(numTestCases);
let currentIndex = 0;
const askForNumber = () => {
if (currentIndex < numberOfCases) {
rl.question('Informe o número: ', (num) => {
const result = fibonacci(parseInt(num));
console.log(result);
currentIndex++;
askForNumber();
});
} else {
rl.close();
}
};
askForNumber();
});
Este código em JavaScript realiza o cálculo da sequência de Fibonacci e interage com o usuário para fornecer os números da sequência com base na entrada. Explicação:
Importando o módulo readline:
readline, que é utilizado para interagir com a entrada e saída no console.Definindo a função fibonacci:
fibonacci(num) recebe um número num como argumento e calcula o valor da sequência de Fibonacci para esse número.fib(n) é uma função recursiva que realiza o cálculo da sequência de Fibonacci. Ela também registra o número de chamadas realizadas no contador calls.Configurando a interface readline:
rl usando o readline.createInterface(). Essa interface permite ler a entrada do usuário e exibir mensagens no console.Solicitando o número de casos de teste:
rl.question() para solicitar ao usuário que insira o número de casos de teste. O usuário insere um número, e a função de retorno de chamada é acionada quando o usuário pressiona “Enter”.numberOfCases.Iniciando a solicitação de números:
askForNumber() é definida para solicitar números de acordo com o número de casos de teste.currentIndex é usado para rastrear quantos números já foram inseridos.Solicitando números de teste:
askForNumber() usa rl.question() para solicitar ao usuário que insira um número. O usuário insere um número, e a função de retorno de chamada é acionada quando o usuário pressiona “Enter”.fibonacci() para calcular o valor da sequência de Fibonacci.Controle de fluxo:
currentIndex e numberOfCases).askForNumber() continua a solicitar números.rl.close() é chamada para fechar a interface readline.Em resumo, este código calcula a sequência de Fibonacci com base nos números fornecidos pelo usuário e exibe o resultado no console. Ele permite ao usuário inserir o número de casos de teste e, em seguida, os números individuais para calcular a sequência de Fibonacci.
Este artigo forneceu uma solução para o problema “Fibonacci, Quantas Chamadas?” em JavaScript. O código calcula o número de Fibonacci e rastreia o número de chamadas recursivas, atendendo aos requisitos do problema. Esperamos que este artigo tenha ajudado a compreender como abordar problemas de sequência de Fibonacci e rastreamento de chamadas recursivas em programação.
