Как проверить, является ли число числом Фибоначчи на Java

Введение

В этом лабораторном занятии (LabEx) вы научитесь проверять, является ли заданное число числом Фибоначчи на Java. Мы рассмотрим три различных подхода для решения этой задачи.

Сначала вы узнаете, как сгенерировать последовательность Фибоначчи до заданного количества членов. Затем вы реализуете метод для проверки, существует ли заданное число в сгенерированной последовательности. Наконец, мы оптимизируем процесс проверки, используя математическую формулу, которая может эффективно определить, является ли число числом Фибоначчи, не генерируя всю последовательность.

Skills Graph

Генерация последовательности Фибоначчи

На этом этапе мы напишем программу на Java для генерации последовательности Фибоначчи до определенного количества членов. Последовательность Фибоначчи представляет собой ряд чисел, в котором каждое число равно сумме двух предыдущих, обычно начиная с 0 и 1. Последовательность выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21 и так далее.

Мы создадим новый файл Java и напишем код для генерации этой последовательности.

1. Откройте WebIDE, если он еще не открыт. По умолчанию вы должны находиться в директории ~/project. Если это не так, откройте Терминал внизу и введите:

   cd ~/project

2. Создайте новый файл с именем Fibonacci.java в директории ~/project. Вы можете сделать это, щелкнув правой кнопкой мыши в проводнике файлов слева и выбрав "New File", а затем введя Fibonacci.java.

3. Откройте файл Fibonacci.java в редакторе и скопируйте и вставьте следующий код 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();
       }
   }

   Давайте быстро разберем основные части этого кода:

   • import java.util.Scanner;: Импортирует класс Scanner для чтения пользовательского ввода.
   • public class Fibonacci: Объявляет основный класс с именем Fibonacci.
   • public static void main(String[] args): Главный метод, с которого начинается выполнение программы.
   • Scanner scanner = new Scanner(System.in);: Создает объект Scanner для чтения ввода с консоли.
   • System.out.print("Enter the number of terms... ");: Запрашивает у пользователя количество членов последовательности.
   • int n = scanner.nextInt();: Считывает целочисленный ввод от пользователя и сохраняет его в переменной n.
   • Блок if-else if-else обрабатывает различные случаи для количества членов (n).
   • int firstTerm = 0; int secondTerm = 1;: Инициализирует первые два члена последовательности.
   • System.out.print(firstTerm + ", " + secondTerm);: Выводит первые два члена.
   • Цикл for вычисляет и выводит последующие члены.
   • int nextTerm = firstTerm + secondTerm;: Вычисляет следующий член, суммируя два предыдущих.
   • firstTerm = secondTerm; secondTerm = nextTerm;: Обновляет firstTerm и secondTerm для следующей итерации.
   • scanner.close();: Закрывает объект Scanner.

4. Сохраните файл Fibonacci.java (Ctrl+S или Cmd+S).

5. Теперь скомпилируйте программу Java с помощью команды javac в Терминале:

   javac Fibonacci.java

   Если нет ошибок, эта команда создаст файл Fibonacci.class в директории ~/project.

6. Наконец, запустите скомпилированную программу с помощью команды java:

   java Fibonacci

   Программа попросит вас ввести количество членов. Введите число (например, 10) и нажмите Enter, чтобы увидеть последовательность Фибоначчи.

   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

Вы успешно написали, скомпилировали и запустили программу на Java для генерации последовательности Фибоначчи!

Проверка наличия числа в последовательности

На этом этапе мы модифицируем нашу программу на Java, чтобы проверить, существует ли заданное число в сгенерированной последовательности Фибоначчи. Это включает добавление логики для сравнения введенного пользователем числа с членами последовательности по мере их генерации.

1. Откройте файл Fibonacci.java в редакторе WebIDE.

2. Измените метод main, чтобы включить логику проверки наличия числа в последовательности. Замените существующий метод main следующим кодом:

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

   Вот разбор изменений:

   • Мы добавили запрос, чтобы попросить пользователя ввести число, которое нужно проверить (System.out.print("Enter the number to check...")).
   • Мы считали это число в новую переменную checkNum (int checkNum = scanner.nextInt();).
   • Логическая переменная found инициализируется значением false. Эта переменная будет отслеживать, было ли число найдено в последовательности.
   • Мы проверяем, равно ли checkNum firstTerm или secondTerm до цикла.
   • Внутри цикла for, после вычисления nextTerm, мы проверяем, равно ли checkNum nextTerm. Если это так, мы устанавливаем found в true.
   • После завершения цикла мы используем оператор if-else, чтобы вывести, было ли число найдено, основываясь на значении переменной found.

3. Сохраните файл Fibonacci.java.

4. Скомпилируйте модифицированную программу в Терминале:

   javac Fibonacci.java

5. Запустите скомпилированную программу:

   java Fibonacci

   Теперь программа попросит ввести количество членов последовательности, а затем число для проверки.

   Пример 1 (число существует):

   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.

   Пример 2 (число не существует):

   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.

Вы успешно модифицировали свою программу для проверки, является ли число частью сгенерированной последовательности Фибоначчи.

Оптимизация с использованием математической формулы

В предыдущих шагах мы итеративно генерировали последовательность Фибоначчи и проверяли, существует ли число, сравнивая его с каждым членом последовательности. Для очень больших чисел генерация всей последовательности может быть неэффективной. На этом этапе мы рассмотрим математическое свойство чисел Фибоначчи, которое позволяет проверить, является ли число числом Фибоначчи, не генерируя последовательность.

Положительное целое число x является числом Фибоначчи тогда и только тогда, когда либо 5*x^2 + 4, либо 5*x^2 - 4 является полным квадратом. Полный квадрат - это целое число, которое является квадратом другого целого числа (например, 4 является полным квадратом, так как это 2*2).

Мы создадим новую программу на Java, которая использует эту формулу для проверки, является ли число числом Фибоначчи.

1. Создайте новый файл с именем CheckFibonacci.java в директории ~/project.

2. Откройте файл CheckFibonacci.java и скопируйте и вставьте следующий код 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();
       }
   }

   Давайте рассмотрим новые части этого кода:

   • public static boolean isPerfectSquare(int n): Это вспомогательная функция, которая принимает целое число n и возвращает true, если n является полным квадратом, и false в противном случае. Она вычисляет целочисленный квадратный корень и проверяет, совпадает ли его квадрат с исходным числом.
   • public static boolean isFibonacci(int n): Эта функция реализует математическую формулу. Она вычисляет 5*n*n + 4 и 5*n*n - 4 и использует функцию isPerfectSquare для проверки, является ли какой-либо из результатов полным квадратом. Оператор || означает "или".
   • Метод main теперь запрашивает у пользователя число, вызывает функцию isFibonacci и выводит результат.

3. Сохраните файл CheckFibonacci.java.

4. Скомпилируйте новую программу в Терминале:

   javac CheckFibonacci.java

5. Запустите скомпилированную программу:

   java CheckFibonacci

   Программа попросит вас ввести число. Введите число (например, 13) и нажмите Enter.

   Пример 1 (число Фибоначчи):

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

   Пример 2 (не число Фибоначчи):

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

Этот метод намного более эффективен для проверки, является ли одно большое число числом Фибоначчи, по сравнению с генерацией последовательности до этого числа.

Резюме

В этом практическом занятии (лабораторной работе) мы научились проверять, является ли число числом Фибоначчи на Java. Мы начали с генерации последовательности Фибоначчи до определенного количества членов с использованием простого итерационного подхода. Это включало в себя понимание определения последовательности Фибоначчи и реализацию логики для вычисления и вывода членов последовательности.

Затем мы рассмотрели, как проверить, существует ли данное число в сгенерированной последовательности Фибоначчи. Наконец, мы узнали об оптимизированном подходе с использованием математической формулы для эффективного определения, является ли число числом Фибоначчи, не явно генерируя всю последовательность. Это включало в себя понимание свойств чисел Фибоначчи и применение формулы для выполнения проверки.