Ряд Фібоначчі в 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 ініціалізується значенням 0, а nextNumber ініціалізується значенням 1.
• Цикл Фібоначчі for виконує ітерації maxNumber:
  • Відобразити попередній номер.
  • Обчисліть суму попередніх чисел (previousNumber) та наступних чисел (nextNumber).
  • Оновіть нові значення previousNumber та nextNumber.

Програма рядів Фібоначчі в Java за допомогою циклу While

Ви також можете згенерувати Java Ряд Фібоначчі з використанням a 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

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

Рекурсивна функція — це така, яка має можливість викликати саму себе.

fibonacciRecursion():

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 для альтернативного синтаксису циклу.

Поширені запитання