Редица на Фибоначи в 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 Loop

Итеративната версия съхранява само две стойности в паметта във всеки един момент, поради което работи в линейно време и постоянно пространство.

//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 Loop

Можете също така да генерирате 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 за алтернативен синтаксис на цикъл.

Въпроси и Отговори