Ряд Фибоначчи в Java использование рекурсии и циклов

Что такое ряд Фибоначчи? Java?

A Серия Фибоначчи in Java Фибоначчи — это последовательность чисел, в которой следующее число является суммой двух предыдущих. Первые два числа последовательности Фибоначчи — это 0 и 1. Числа Фибоначчи широко используются в исследованиях вычислительной производительности алгоритма, определяющего наибольший общий делитель двух целых чисел.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

В виде формулы правило имеет вид F(n) = F(n-1) + F(n-2), где F(0) = 0 и F(1) = 1. В таблице ниже показано, как образуются первые восемь членов.

Программа рядов Фибоначчи в Java использование цикла For

Итеративная версия хранит в памяти одновременно только два значения, поэтому она работает за линейное время и с постоянным объемом памяти.

//Using  For Loop
public class FibonacciExample {
	public static void main(String[] args)
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10;
		 int previousNumber = 0;
		 int nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */


	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
	}
}

Выход:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Логика программы:

• Значение previousNumber инициализируется нулем, а значение nextNumber — единицей.
• Цикл for по Фибоначчи выполняет итерации по... maxNumber:
  • Отобразить предыдущее число.
  • Вычислите сумму previousNumber и nextNumber.
  • Обновите значения полей previousNumber и nextNumber.

Программа рядов Фибоначчи в Java использование цикла while

Вы также можете создать Java Последовательность Фибоначчи с использованием while зациклиться JavaАрифметические операции идентичны, меняется только синтаксис цикла.

//Using  While Loop
public class FibonacciWhileExample {
	public static void main(String[] args)
	{
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");

	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }

	}

}

Выход:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Единственное отличие в логике программы заключается в использовании цикла while для вывода чисел Фибоначчи. Счетчик должен быть объявлен до цикла и увеличиваться внутри него, иначе цикл никогда не завершится.

Ряд Фибоначчи на основе пользовательского ввода

Задание количества терминов вручную удобно для демонстрации, но в реальных упражнениях значение обычно считывается с клавиатуры. Класс Scanner обрабатывает это в три строки, а логика генерации остается неизменной.

//fibonacci series based on the user input
import java.util.Scanner;

public class FibonacciUserInput {

    public static void main(String[] args)
    {
        int maxNumber = 0;
        int previousNumber = 0;
        int nextNumber = 1;

        System.out.println("How many numbers you want in Fibonacci:");
        Scanner scanner = new Scanner(System.in);
        maxNumber = scanner.nextInt();
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        for (int i = 1; i <= maxNumber; ++i)
        {
            System.out.print(previousNumber + " ");
            /* On each iteration, we are assigning the second number
             * to the first number and assigning the sum of the last two
             * numbers to the second number
             */

            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }

        scanner.close();
    }
}

Пример запуска:

How many numbers you want in Fibonacci:
7
Fibonacci Series of 7 numbers:0 1 1 2 3 5 8

Логика программы:
Логика та же, что и раньше. Вместо того чтобы жестко задавать количество элементов для отображения, вместо этого используется кодирование количества элементов в коде. Java Для вычисления числа из последовательности Фибоначчи пользователю предлагается ввести это число.

Ряд Фибоначчи с использованием рекурсии в Java

Ниже представлена ​​программа рядов Фибоначчи в Java используя рекурсию:

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

Выход:

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

Логика программы:

Рекурсивная функция — это функция, которая имеет возможность вызывать саму себя.

фибоначчиРекурсия():

1. Java Функция рекурсии Фибоначчи принимает на вход число. Она проверяет значения 0, 1 и 2 и возвращает 0, 1, 1 соответственно, поскольку последовательность Фибоначчи в Java начинается с 0, 1, 1.
2. Когда входное значение n равно 3 или больше, функция вызывает саму себя рекурсивно. Вызов происходит дважды. tracНиже приведен запрос на ввод значения 4.

fibonacciRecursion(4)
    = fibonacciRecursion(2) + fibonacciRecursion(3)

    fibonacciRecursion(2) = 1                    // base case, no further calls
    fibonacciRecursion(3) = fibonacciRecursion(1) + fibonacciRecursion(2)
                          = 1 + 1
                          = 2

    Result: 1 + 2 = 3

Базовые случаи останавливают спуск. Поскольку 1 и 2 возвращаются немедленно, ветвь для fibonacciRecursion(2) никогда не расширяется дальше, что и поддерживает tracконечное.

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

Обычная рекурсия многократно пересчитывает одни и те же члены. Для вычисления члена 40 требуется более 200 миллионов вызовов. Сохранение каждого результата при первом вычислении полностью исключает это дублирование.

public class FibonacciMemo {

    static long[] cache;

    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        // return the stored value when it exists
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        int maxNumber = 90;
        cache = new long[maxNumber + 1];

        System.out.println("Term 50 is: " + fib(50));
        System.out.println("Term 90 is: " + fib(90));
    }
}

Выход:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Сравнение методов Фибоначчи в Java

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

Та же схема счётчика и накопителя встречается в нескольких связанных упражнениях. Продолжайте с... Java программа палиндромов, Java программа для проверки простого числа, и Программа для вывода простых чисел от 1 до 100.Для практических занятий с использованием массивов см. Bubble Сортировать в Java и Java массивы, и просмотрите для каждого цикла в Java для альтернативного синтаксиса цикла.

Часто задаваемые вопросы (FAQ)