Trochę teorii - ciąg Fibonnaciego - I_R_W14_M09_Java Ciąg Fibonnaciego

R7L2RZA2MV5A1

Ciąg Fibonacciego – definicja

Ciąg Fibonacciego to ciąg złożony z liczb naturalnych o następujących cechach:

pierwszy element ciągu jest równy 0,
drugi element ciągu jest równy 1,
każdy kolejny element ciągu jest sumą dwóch elementów go poprzedzających.

Definicja rekurencyjna ciągu Fibonacciego ma następującą postać:

$F_{n} = {\begin{cases} 0 & dla n = 0 \\ 1 & dla n = 1 \\ F_{n - 1} + F_{n - 2} & dla n > 1 \end{cases}$

Na podstawie definicji możemy obliczyć kolejne elementy ciągu.

Przykład 1

Obliczmy wyraz ciągu Fibonacciego o indeksie 5.

FIndeks dolny 5 = FIndeks dolny 4 + FIndeks dolny 3

FIndeks dolny 4 = FIndeks dolny 3 + FIndeks dolny 2

FIndeks dolny 3 = FIndeks dolny 2 + FIndeks dolny 1

FIndeks dolny 2 Indeks dolny koniec = FIndeks dolny 1 + FIndeks dolny 0 = 1 + 0 = 1

FIndeks dolny 3 Indeks dolny koniec= FIndeks dolny 2 + FIndeks dolny 1 = 1 + 1 = 2

FIndeks dolny 4 = FIndeks dolny 3 + FIndeks dolny 2 = 2 + 1 = 3

FIndeks dolny 5 = FIndeks dolny 4 + FIndeks dolny 3 = 3 + 2 = 5

Korzystając z definicji rekurencyjnej możemy zapisać funkcję w psełdokodzie.

Przykład 2

Oto zapisana w postaci pseudokodu funkcja iteracyjna, która oblicza wyraz ciągu >Fibonacciego o indeksie n:

funkcja rek_fib(n)
	jeżeli n == 0 wykonaj:
		zwróć 0
	w przeciwnym razie:
  	jeżeli n == 1 wykonaj: 
			zwróć 1
  	w przeciwnym razie:
  		zwróć rek_fib(n-2) + rek_fib(n-1)

Umiemy już zapisać wersję rekurencyną obliczania n‑tego wyrazu ciągu Fibonacciego. Korzystając z definicji rekurencyjnej obliczymy n‑ty element ciągu w wersji iteracyjnej.

Przykład 3

Oto zapisana w postaci pseudokodu funkcja iteracyjna, która oblicza wyraz ciągu Fibonacciego o indeksie n:

funkcja iter_fib(n)
	jeżeli n == 0 wykonaj:
		zwróć 0
	w przeciwnym razie jeżeli n == 1 wykonaj: 
		zwróć 1

	a = 0
	b = 1
	i = 2

	dopóki i <= n wykonuj:
		suma = a + b
		a = b
		b = suma
		i = i + 1
	zwróć b

Słownik

argument funkcji

element składni w określonym języku programowania, który w wyniku wywołania podprogramu zostaje utożsamiony (skojarzony) z określonym parametrem podprogramu

funkcja typu void

funkcja, która nie zwraca żadnej wartości

instrukcja warunkowa

element języka programowania sterujący działaniem programu; pozwala wykonać różne instrukcje w zależności od tego, czy zdefiniowane przez programistę wyrażenie logiczne jest prawdziwe czy nieprawdziwe

nieskończona pętla

pętla, która nigdy nie spełnia warunku zakończenia; pętla działająca w nieskończoność

parametr funkcji

element składni w określonym języku programowania; umożliwia komunikację pomiędzy podprogramem (funkcją) wywołanym a programem wywołującym; parametry określa się w nagłówku podprogramu (przy jego definicji)

rekurencja

sytuacja, w której funkcja wywołuje samą siebie, aż do napotkania przypadku podstawowego

Na dobry początek

Zaprogramuj go - wersja iteracyjna

Ciąg Fibonacciego – definicja

Słownik