Como Verificar se um Número é um Número de Fibonacci em Java - Tutorial e Código

Introdução

Neste laboratório, você aprenderá como verificar se um determinado número é um número de Fibonacci em Java. Exploraremos três abordagens diferentes para alcançar este objetivo.

Primeiramente, você aprenderá como gerar a sequência de Fibonacci até um número especificado de termos. Em seguida, você implementará um método para verificar se um determinado número existe dentro da sequência gerada. Finalmente, otimizaremos o processo de verificação utilizando uma fórmula matemática que pode determinar eficientemente se um número é um número de Fibonacci sem gerar toda a sequência.

Gerar Sequência de Fibonacci

Nesta etapa, escreveremos um programa Java para gerar a sequência de Fibonacci até um certo número de termos. A sequência de Fibonacci é uma série de números onde cada número é a soma dos dois anteriores, geralmente começando com 0 e 1. A sequência se parece com isto: 0, 1, 1, 2, 3, 5, 8, 13, 21, e assim por diante.

Criaremos um novo arquivo Java e escreveremos o código para gerar esta sequência.

Abra o WebIDE se ele ainda não estiver aberto. Você deve estar no diretório ~/project por padrão. Caso contrário, abra o Terminal na parte inferior e digite:
```
cd ~/project
```
Crie um novo arquivo chamado Fibonacci.java no diretório ~/project. Você pode fazer isso clicando com o botão direito no File Explorer à esquerda e selecionando "New File", em seguida, digitando Fibonacci.java.
Abra o arquivo Fibonacci.java no editor e copie e cole o seguinte código Java:
```
import java.util.Scanner;

public class Fibonacci {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of terms for Fibonacci sequence: ");
        int n = scanner.nextInt();

        if (n <= 0) {
            System.out.println("Please enter a positive integer.");
        } else if (n == 1) {
            System.out.println("Fibonacci sequence up to 1 term:");
            System.out.println("0");
        } else {
            System.out.println("Fibonacci sequence up to " + n + " terms:");

            int firstTerm = 0;
            int secondTerm = 1;

            System.out.print(firstTerm + ", " + secondTerm);

            for (int i = 3; i <= n; ++i) {
                int nextTerm = firstTerm + secondTerm;
                System.out.print(", " + nextTerm);
                firstTerm = secondTerm;
                secondTerm = nextTerm;
            }
            System.out.println(); // Print a newline at the end
        }

        scanner.close();
    }
}
```
Vamos entender rapidamente as partes-chave deste código:
- import java.util.Scanner;: Importa a classe Scanner para ler a entrada do usuário.
- public class Fibonacci: Declara a classe principal chamada Fibonacci.
- public static void main(String[] args): O método principal onde a execução do programa começa.
- Scanner scanner = new Scanner(System.in);: Cria um objeto Scanner para ler a entrada do console.
- System.out.print("Enter the number of terms... ");: Solicita ao usuário que insira o número de termos.
- int n = scanner.nextInt();: Lê a entrada inteira do usuário e a armazena na variável n.
- O bloco if-else if-else lida com diferentes casos para o número de termos (n).
- int firstTerm = 0; int secondTerm = 1;: Inicializa os dois primeiros termos da sequência.
- System.out.print(firstTerm + ", " + secondTerm);: Imprime os dois primeiros termos.
- O loop for calcula e imprime os termos subsequentes.
- int nextTerm = firstTerm + secondTerm;: Calcula o próximo termo somando os dois anteriores.
- firstTerm = secondTerm; secondTerm = nextTerm;: Atualiza firstTerm e secondTerm para a próxima iteração.
- scanner.close();: Fecha o objeto Scanner.
Salve o arquivo Fibonacci.java (Ctrl+S ou Cmd+S).
Agora, compile o programa Java usando o comando javac no Terminal:
```
javac Fibonacci.java
```
Se não houver erros, este comando criará um arquivo Fibonacci.class no diretório ~/project.
Finalmente, execute o programa compilado usando o comando java:
```
java Fibonacci
```
O programa solicitará que você insira o número de termos. Insira um número (por exemplo, 10) e pressione Enter para ver a sequência de Fibonacci.
```
Enter the number of terms for Fibonacci sequence: 10
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
```

Você escreveu, compilou e executou com sucesso um programa Java para gerar a sequência de Fibonacci!

Verificar se o Número Existe na Sequência

Nesta etapa, modificaremos nosso programa Java para verificar se um determinado número existe dentro da sequência de Fibonacci gerada. Isso envolve adicionar lógica para comparar o número inserido pelo usuário com os termos da sequência à medida que são gerados.

Abra o arquivo Fibonacci.java no editor WebIDE.

Modifique o método main para incluir a lógica para verificar se um número existe na sequência. Substitua o método main existente pelo seguinte código:

import java.util.Scanner;

public class Fibonacci {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of terms for Fibonacci sequence: ");
        int n = scanner.nextInt();

        if (n <= 0) {
            System.out.println("Please enter a positive integer for the number of terms.");
            scanner.close();
            return; // Exit the program
        }

        System.out.print("Enter the number to check if it exists in the sequence: ");
        int checkNum = scanner.nextInt();

        System.out.println("Fibonacci sequence up to " + n + " terms:");

        int firstTerm = 0;
        int secondTerm = 1;
        boolean found = false;

        // Check the first two terms
        if (checkNum == firstTerm) {
            found = true;
        }
        System.out.print(firstTerm);

        if (n > 1) {
            if (checkNum == secondTerm) {
                found = true;
            }
            System.out.print(", " + secondTerm);
        }


        // Generate and check subsequent terms
        for (int i = 3; i <= n; ++i) {
            int nextTerm = firstTerm + secondTerm;
            if (checkNum == nextTerm) {
                found = true;
            }
            System.out.print(", " + nextTerm);
            firstTerm = secondTerm;
            secondTerm = nextTerm;
        }
        System.out.println(); // Print a newline at the end

        if (found) {
            System.out.println(checkNum + " exists in the Fibonacci sequence.");
        } else {
            System.out.println(checkNum + " does not exist in the Fibonacci sequence.");
        }

        scanner.close();
    }
}

Aqui está uma análise das mudanças:

Adicionamos um prompt para pedir ao usuário o número que ele deseja verificar (System.out.print("Enter the number to check...")).
Lemos este número em uma nova variável checkNum (int checkNum = scanner.nextInt();).
Uma variável booleana found é inicializada como false. Esta variável rastreará se o número foi encontrado na sequência.
Verificamos se checkNum é igual a firstTerm ou secondTerm antes do loop.
Dentro do loop for, após calcular nextTerm, verificamos se checkNum é igual a nextTerm. Se for, definimos found como true.
Após o término do loop, usamos uma instrução if-else para imprimir se o número foi encontrado com base no valor da variável found.

Salve o arquivo Fibonacci.java.
Compile o programa modificado no Terminal:
```
javac Fibonacci.java
```

Execute o programa compilado:

java Fibonacci

O programa agora pedirá o número de termos e, em seguida, o número a ser verificado.

Exemplo 1 (Número existe):

Enter the number of terms for Fibonacci sequence: 10
Enter the number to check if it exists in the sequence: 8
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
8 exists in the Fibonacci sequence.

Exemplo 2 (Número não existe):

Enter the number of terms for Fibonacci sequence: 10
Enter the number to check if it exists in the sequence: 10
Fibonacci sequence up to 10 terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
10 does not exist in the Fibonacci sequence.

Você modificou com sucesso seu programa para verificar se um número faz parte da sequência de Fibonacci gerada.

Otimizar com Fórmula Matemática

Nas etapas anteriores, geramos a sequência de Fibonacci iterativamente e verificamos se um número existe comparando-o com cada termo. Para números muito grandes, gerar toda a sequência pode ser ineficiente. Nesta etapa, exploraremos uma propriedade matemática dos números de Fibonacci que nos permite verificar se um número é um número de Fibonacci sem gerar a sequência.

Um inteiro positivo x é um número de Fibonacci se e somente se 5*x^2 + 4 ou 5*x^2 - 4 for um quadrado perfeito. Um quadrado perfeito é um inteiro que é o quadrado de um inteiro (por exemplo, 4 é um quadrado perfeito porque é 2*2).

Criaremos um novo programa Java que usa esta fórmula para verificar se um número é um número de Fibonacci.

Crie um novo arquivo chamado CheckFibonacci.java no diretório ~/project.

Abra CheckFibonacci.java e copie e cole o seguinte código Java:

import java.util.Scanner;

public class CheckFibonacci {

    // Function to check if a number is a perfect square
    public static boolean isPerfectSquare(int n) {
        if (n < 0) {
            return false;
        }
        int sqrt = (int) Math.sqrt(n);
        return (sqrt * sqrt == n);
    }

    // Function to check if a number is a Fibonacci number
    public static boolean isFibonacci(int n) {
        // n is Fibonacci if 5*n^2 + 4 or 5*n^2 - 4 is a perfect square
        return isPerfectSquare(5 * n * n + 4) ||
               isPerfectSquare(5 * n * n - 4);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number to check if it is a Fibonacci number: ");
        int num = scanner.nextInt();

        if (isFibonacci(num)) {
            System.out.println(num + " is a Fibonacci number.");
        } else {
            System.out.println(num + " is not a Fibonacci number.");
        }

        scanner.close();
    }
}

Vamos analisar as novas partes deste código:

public static boolean isPerfectSquare(int n): Esta é uma função auxiliar que recebe um inteiro n e retorna true se n for um quadrado perfeito e false caso contrário. Ele calcula a raiz quadrada inteira e verifica se, ao elevá-la ao quadrado, o número original é retornado.
public static boolean isFibonacci(int n): Esta função implementa a fórmula matemática. Ela calcula 5*n*n + 4 e 5*n*n - 4 e usa a função isPerfectSquare para verificar se algum dos resultados é um quadrado perfeito. O operador || significa "ou".
O método main agora solicita ao usuário um número, chama a função isFibonacci e imprime o resultado.

Salve o arquivo CheckFibonacci.java.
Compile o novo programa no Terminal:
```
javac CheckFibonacci.java
```
Execute o programa compilado:
```
java CheckFibonacci
```
O programa pedirá que você insira um número. Insira um número (por exemplo, 13) e pressione Enter.

Exemplo 1 (Número de Fibonacci):
```
Enter a number to check if it is a Fibonacci number: 13
13 is a Fibonacci number.
```
Exemplo 2 (Não é um número de Fibonacci):
```
Enter a number to check if it is a Fibonacci number: 10
10 is not a Fibonacci number.
```

Este método é muito mais eficiente para verificar se um único número grande é um número de Fibonacci em comparação com a geração da sequência até esse número.

Resumo

Neste laboratório, aprendemos como verificar se um número é um número de Fibonacci em Java. Começamos gerando a sequência de Fibonacci até um certo número de termos usando uma abordagem iterativa simples. Isso envolveu a compreensão da definição da sequência de Fibonacci e a implementação da lógica para calcular e imprimir os termos.

Em seguida, exploramos como verificar se um determinado número existe dentro da sequência de Fibonacci gerada. Finalmente, aprendemos sobre uma abordagem otimizada usando uma fórmula matemática para determinar eficientemente se um número é um número de Fibonacci sem gerar explicitamente toda a sequência. Isso envolveu a compreensão das propriedades dos números de Fibonacci e a aplicação da fórmula para realizar a verificação.