Wie man prüft, ob eine Zahl in Java eine Fibonacci-Zahl ist

Einführung

In diesem Lab werden Sie lernen, wie Sie in Java prüfen können, ob eine gegebene Zahl eine Fibonacci-Zahl ist. Wir werden drei verschiedene Ansätze untersuchen, um dies zu erreichen.

Zunächst werden Sie lernen, wie Sie die Fibonacci-Folge bis zu einer bestimmten Anzahl von Gliedern generieren. Dann werden Sie eine Methode implementieren, um zu prüfen, ob eine gegebene Zahl in der generierten Folge existiert. Schließlich werden wir den Prüfprozess optimieren, indem wir eine mathematische Formel nutzen, die effizient bestimmen kann, ob eine Zahl eine Fibonacci-Zahl ist, ohne die gesamte Folge zu generieren.

Skills Graph

Fibonacci-Folge generieren

In diesem Schritt werden wir ein Java-Programm schreiben, um die Fibonacci-Folge bis zu einer bestimmten Anzahl von Gliedern zu generieren. Die Fibonacci-Folge ist eine Reihe von Zahlen, bei der jede Zahl die Summe der beiden vorhergehenden Zahlen ist, normalerweise beginnend mit 0 und 1. Die Folge sieht wie folgt aus: 0, 1, 1, 2, 3, 5, 8, 13, 21 und so weiter.

Wir werden eine neue Java-Datei erstellen und den Code schreiben, um diese Folge zu generieren.

1. Öffnen Sie die WebIDE, wenn sie noch nicht geöffnet ist. Standardmäßig sollten Sie sich im Verzeichnis ~/project befinden. Wenn nicht, öffnen Sie das Terminal unten und geben Sie ein:

   cd ~/project

2. Erstellen Sie eine neue Datei namens Fibonacci.java im Verzeichnis ~/project. Sie können dies tun, indem Sie mit der rechten Maustaste im Dateiexplorer links klicken und "Neue Datei" auswählen, dann Fibonacci.java eingeben.

3. Öffnen Sie die Datei Fibonacci.java im Editor und kopieren und fügen Sie den folgenden Java-Code ein:

   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();
       }
   }

   Lassen Sie uns schnell die wichtigsten Teile dieses Codes verstehen:

   • import java.util.Scanner;: Importiert die Scanner-Klasse, um Benutzereingaben zu lesen.
   • public class Fibonacci: Deklariert die Hauptklasse namens Fibonacci.
   • public static void main(String[] args): Die Hauptmethode, in der die Programmausführung beginnt.
   • Scanner scanner = new Scanner(System.in);: Erstellt ein Scanner-Objekt, um Eingaben von der Konsole zu lesen.
   • System.out.print("Enter the number of terms... ");: Fordert den Benutzer auf, die Anzahl der Glieder einzugeben.
   • int n = scanner.nextInt();: Liest die Ganzzahl-Eingabe des Benutzers und speichert sie in der Variablen n.
   • Der if-else if-else-Block behandelt verschiedene Fälle für die Anzahl der Glieder (n).
   • int firstTerm = 0; int secondTerm = 1;: Initialisiert die ersten beiden Glieder der Folge.
   • System.out.print(firstTerm + ", " + secondTerm);: Gibt die ersten beiden Glieder aus.
   • Die for-Schleife berechnet und gibt die folgenden Glieder aus.
   • int nextTerm = firstTerm + secondTerm;: Berechnet das nächste Glied, indem es die beiden vorhergehenden Glieder summiert.
   • firstTerm = secondTerm; secondTerm = nextTerm;: Aktualisiert firstTerm und secondTerm für die nächste Iteration.
   • scanner.close();: Schließt das Scanner-Objekt.

4. Speichern Sie die Datei Fibonacci.java (Strg+S oder Cmd+S).

5. Kompilieren Sie jetzt das Java-Programm mit dem Befehl javac im Terminal:

   javac Fibonacci.java

   Wenn keine Fehler auftreten, erstellt dieser Befehl eine Datei Fibonacci.class im Verzeichnis ~/project.

6. Führen Sie schließlich das kompilierte Programm mit dem Befehl java aus:

   java Fibonacci

   Das Programm wird Sie auffordern, die Anzahl der Glieder einzugeben. Geben Sie eine Zahl ein (z.B. 10) und drücken Sie die Eingabetaste, um die Fibonacci-Folge anzuzeigen.

   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

Sie haben erfolgreich ein Java-Programm geschrieben, kompiliert und ausgeführt, um die Fibonacci-Folge zu generieren!

Prüfen, ob eine Zahl in der Folge existiert

In diesem Schritt werden wir unser Java-Programm ändern, um zu prüfen, ob eine gegebene Zahl in der generierten Fibonacci-Folge existiert. Dies erfordert die Hinzufügung von Logik, um die vom Benutzer eingegebene Zahl mit den Gliedern der Folge zu vergleichen, während diese generiert werden.

1. Öffnen Sie die Datei Fibonacci.java im WebIDE-Editor.

2. Modifizieren Sie die main-Methode, um die Logik zum Prüfen, ob eine Zahl in der Folge existiert, einzubeziehen. Ersetzen Sie die vorhandene main-Methode durch den folgenden Code:

   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();
       }
   }

   Hier ist eine Zusammenfassung der Änderungen:

   • Wir haben eine Eingabeaufforderung hinzugefügt, um den Benutzer nach der Zahl zu fragen, die er prüfen möchte (System.out.print("Enter the number to check...")).
   • Wir lesen diese Zahl in eine neue Variable checkNum (int checkNum = scanner.nextInt();).
   • Eine boolesche Variable found wird auf false initialisiert. Diese Variable verfolgt, ob die Zahl in der Folge gefunden wird.
   • Wir prüfen, ob checkNum gleich dem firstTerm oder secondTerm ist, bevor die Schleife beginnt.
   • Innerhalb der for-Schleife, nachdem nextTerm berechnet wurde, prüfen wir, ob checkNum gleich nextTerm ist. Wenn ja, setzen wir found auf true.
   • Nachdem die Schleife beendet ist, verwenden wir eine if-else-Anweisung, um auszugeben, ob die Zahl gefunden wurde, basierend auf dem Wert der found-Variable.

3. Speichern Sie die Datei Fibonacci.java.

4. Kompilieren Sie das geänderte Programm im Terminal:

   javac Fibonacci.java

5. Führen Sie das kompilierte Programm aus:

   java Fibonacci

   Das Programm wird nun nach der Anzahl der Glieder und dann nach der zu prüfenden Zahl fragen.

   Beispiel 1 (Zahl existiert):

   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.

   Beispiel 2 (Zahl existiert nicht):

   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.

Sie haben Ihr Programm erfolgreich so modifiziert, dass es prüft, ob eine Zahl Teil der generierten Fibonacci-Folge ist.

Optimierung mit einer mathematischen Formel

In den vorherigen Schritten haben wir die Fibonacci-Folge iterativ generiert und geprüft, ob eine Zahl in der Folge existiert, indem wir sie mit jedem Glied verglichen haben. Bei sehr großen Zahlen kann die Generierung der gesamten Folge ineffizient sein. In diesem Schritt werden wir eine mathematische Eigenschaft der Fibonacci-Zahlen untersuchen, die es uns ermöglicht, zu prüfen, ob eine Zahl eine Fibonacci-Zahl ist, ohne die Folge zu generieren.

Eine positive Ganzzahl x ist genau dann eine Fibonacci-Zahl, wenn entweder 5*x^2 + 4 oder 5*x^2 - 4 eine perfekte Quadratzahl ist. Eine perfekte Quadratzahl ist eine Ganzzahl, die das Quadrat einer anderen Ganzzahl ist (z.B. ist 4 eine perfekte Quadratzahl, weil es 2*2 ist).

Wir werden ein neues Java-Programm erstellen, das diese Formel verwendet, um zu prüfen, ob eine Zahl eine Fibonacci-Zahl ist.

1. Erstellen Sie eine neue Datei namens CheckFibonacci.java im Verzeichnis ~/project.

2. Öffnen Sie CheckFibonacci.java und kopieren und fügen Sie den folgenden Java-Code ein:

   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();
       }
   }

   Schauen wir uns die neuen Teile dieses Codes an:

   • public static boolean isPerfectSquare(int n): Dies ist eine Hilfsfunktion, die eine Ganzzahl n nimmt und true zurückgibt, wenn n eine perfekte Quadratzahl ist, und false sonst. Sie berechnet die Ganzzahl-Wurzel und prüft, ob das Quadrat dieser Wurzel die ursprüngliche Zahl ergibt.
   • public static boolean isFibonacci(int n): Diese Funktion implementiert die mathematische Formel. Sie berechnet 5*n*n + 4 und 5*n*n - 4 und verwendet die isPerfectSquare-Funktion, um zu prüfen, ob eines der Ergebnisse eine perfekte Quadratzahl ist. Der ||-Operator bedeutet "oder".
   • Die main-Methode fordert jetzt den Benutzer auf, eine Zahl einzugeben, ruft die isFibonacci-Funktion auf und gibt das Ergebnis aus.

3. Speichern Sie die Datei CheckFibonacci.java.

4. Kompilieren Sie das neue Programm im Terminal:

   javac CheckFibonacci.java

5. Führen Sie das kompilierte Programm aus:

   java CheckFibonacci

   Das Programm wird Sie auffordern, eine Zahl einzugeben. Geben Sie eine Zahl ein (z.B. 13) und drücken Sie die Eingabetaste.

   Beispiel 1 (Fibonacci-Zahl):

   Enter a number to check if it is a Fibonacci number: 13
   13 is a Fibonacci number.

   Beispiel 2 (Keine Fibonacci-Zahl):

   Enter a number to check if it is a Fibonacci number: 10
   10 is not a Fibonacci number.

Diese Methode ist bei der Prüfung, ob eine einzelne große Zahl eine Fibonacci-Zahl ist, viel effizienter als die Generierung der Folge bis zu dieser Zahl.

Zusammenfassung

In diesem Lab haben wir gelernt, wie man in Java prüft, ob eine Zahl eine Fibonacci-Zahl ist. Wir haben begonnen, indem wir die Fibonacci-Folge bis zu einer bestimmten Anzahl von Gliedern mit einem einfachen iterativen Ansatz generiert haben. Dies erforderte das Verständnis der Definition der Fibonacci-Folge und die Implementierung der Logik zur Berechnung und Ausgabe der Glieder.

Als Nächstes haben wir untersucht, wie man prüft, ob eine gegebene Zahl in der generierten Fibonacci-Folge existiert. Schließlich haben wir einen optimierten Ansatz kennengelernt, der eine mathematische Formel verwendet, um effizient zu bestimmen, ob eine Zahl eine Fibonacci-Zahl ist, ohne die gesamte Folge explizit zu generieren. Dies erforderte das Verständnis der Eigenschaften der Fibonacci-Zahlen und die Anwendung der Formel zur Prüfung.