Ciąg Fibonnaciego - wersja iteracyjna

Wersja iteracyjna ciągu Fibonacciego polega na obliczaniu kolejnych wyrazów bez użycia rekurencji, co czyni ją bardziej wydajną pod względem czasu i pamięci. Zamiast wielokrotnie wywoływać tę samą funkcję, wykorzystujemy pętlę (np. for lub while) oraz zmienne pomocnicze do przechowywania dwóch ostatnich wartości ciągu. Dzięki temu każde kolejne obliczenie opiera się bezpośrednio na poprzednich wynikach, co znacząco redukuje złożoność obliczeniową do liniowej O(n).

Napiszemy program, który zwróci element ciągu Fibonacciego o indeksie n. Zastosujemy iterację.Sprubuj rozwiązać zadanie samodzielnie, jeżeli popełnisz błąd zapoznaj się z dalszą częścią materiału.

Rozpocznijmy od utworzenia metody o nazwie iterFibonacci.

public static long iterFibonacci(int n) {

}

Wybieramy typ long, ponieważ wartości kolejnych wyrazów ciągu Fibonacciego rosną wykładniczo.

Parametr n funkcji będzie indeksem elementu ciągu, który ma być obliczony.

Zapisujemy warunki, po których spełnieniu zostanie zatrzymane działanie funkcji i zwróci ona wartość. Wiemy, że pierwszy wyraz ciągu Fibonacciego – zatem wyraz o indeksie 0 – ma wartość 0. Natomiast drugi wyraz – czyli wyraz o indeksie 1 – wynosi 1. Zapiszemy odpowiednie instrukcje warunkowe.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
}

Musimy brać również pod uwagę przypadek, gdy wartość parametru n jest większa niż 1. W takiej sytuacji każdy kolejny element jest sumą dwóch poprzednich. Dla dalszego działania funkcji potrzebujemy zmiennych pomocniczych. Inicjalizujemy trzy zmienne pomocnicze: a, b (oznaczające wartości dwóch początkowych wyrazów ciągu) oraz i (indeks kolejnego elementu ciągu Fibonacciego). Przypisujemy im odpowiednio wartości 0, 1 i 2.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

long a = 0;
long b = 1;
int i = 2;

}

Zapisujemy pętlę while, która będzie wykonywać się tak długo, dopóki wartość zmiennej i jest mniejsza od wartości zmiennej n lub jej równa.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

long a = 0;
long b = 1;
int i = 2;

while (i <= n) {
    }

}

W każdym obiegu pętli while najpierw obliczamy i-ty wyraz ciągu, czyli sumę dwóch poprzednich wyrazów ciągu. Wynik przypisujemy do zmiennej suma. Następnie zmiennej a przypisujemy wartość zmiennej b, a zmiennej b wartość zmiennej suma. Na końcu zwiększamy wartość zmiennej i o 1.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

long a = 0;
long b = 1;
int i = 2;

while (i <= n) {
long suma = a + b;
a = b;
b = suma;
i = i + 1;
    }

}

Po zakończeniu pętli wartość zmiennej b jest zwracana jako wynik działania funkcji.

public static long iterFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}

long a = 0;
long b = 1;
int i = 2;

while (i <= n) {
long suma = a + b;
a = b;
b = suma;
i = i + 1;
    }

return b;

}