Przeczytaj

Ciąg Fibonacciego – podsumowanie

Ciąg Fibonacciego to ciąg złożony z liczb naturalnychliczby naturalneliczb 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 ciągu Fibonacciego ma następującą postać:

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

Rekurencja

Przykład 1

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

rek_fib(n)
    jeśli n wynosi 0 zwróć 0
    jeśli n wynosi 1 zwróć 1
    w innym przypadku zwróć (rek_fib(n - 1) + rek_fib(n - 2))

Na podstawie pseudokodu możemy zdefiniować w języku Python funkcję, która zwróci element ciągu o indeksie n. Przetestujmy jej działanie dla indeksu równego 5:

def rek_fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return rek_fibonacci(n - 1) + rek_fibonacci(n - 2)
        
print(rek_fibonacci(5))

Wywołując przedstawioną funkcję w pętli, wygenerujemy określoną liczbę elementów ciągu Fibonacciego:

def rek_fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return rek_fibonacci(n - 1) + rek_fibonacci(n - 2)
        
ciag = ''
for element in range(10):
    ciag += str(rek_fibonacci(element)) + ' '

print(ciag)

Polecenie 1

Możesz również przygotować funkcję zwracającą ciąg Fibonacciego jako listę dla dalszych obliczeń. Przygotuj taki kod.

Iteracja

Przykład 2

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

Na podstawie pseudokodu możemy zdefiniować w języku Python funkcję, która zwróci element ciągu o indeksie n. Przetestujmy jej działanie dla indeksu równego 5:

def iter_fibonacci(n):
	if n == 0:
		return 0
	elif n == 1: 
		return 1

	a = 0
	b = 1
	i = 2

	while i <= n:
		suma = a + b
		a = b
		b = suma
		i = i + 1
	return b
	
print(iter_fibonacci(5))

Wywołując przedstawioną funkcję w pętli, wygenerujemy określoną liczbę elementów ciągu Fibonacciego:

def iter_fibonacci(n):
	if n == 0:
		return 0
	elif n == 1: 
		return 1

	a = 0
	b = 1
	i = 2

	while i <= n:
		suma = a + b
		a = b
		b = suma
		i = i + 1
	return b
	
ciag = ''
for element in range(10):
    ciag += str(iter_fibonacci(element)) + ' '
print(ciag)

Polecenie 2

Możesz również przygotować funkcję zwracającą ciąg Fibonacciego jako listę dla dalszych obliczeń. Przygotuj taki kod.

Złota liczba

Ciąg Fibonacciego jest powiązany z tzw. złotą liczbązłota liczbazłotą liczbą. W przybliżeniu wynosi ona 1,618033988… Dzieląc wyraz ciągu o indeksie n przez wyraz o indeksie n - 1, otrzymamy iloraz oscylujący wokół 1,618. W miarę tego, jak zwiększają się wartości dzielnej i dzielnika, zmniejsza się odchylenie od wartości złotej liczby.

Przykład 3

Napiszmy program, który dla zadanej liczby elementów ciągu Fibonacciego wypisze kolejne przybliżenia złotej liczby oraz przygotuje wykres obrazujący, jak zmienia się odchylenie od wartości złotej liczby dla kolejnych wyrazów ciągu Fibonacciego, wykorzystując moduł matplotlibmatplotlibmatplotlib.

Linia 1. def fibonacci podkreślnik zlota otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 2. kratka wczytanie modułu rysującego. Linia 3. import matplotlib kropka pyplot as plt. Linia 5. kratka definicja funkcji pomocniczej. Linia 6. def rek podkreślnik fib otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 7. if n znak równości znak równości 0 dwukropek. Linia 8. return 0. Linia 9. elif n znak równości znak równości 1 dwukropek. Linia 10. return 1. Linia 11. else dwukropek. Linia 12. return rek podkreślnik fib otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus rek podkreślnik fib otwórz nawias okrągły n minus 2 zamknij nawias okrągły. Linia 14. lista podkreślnik x znak równości otwórz nawias kwadratowy x for x in range otwórz nawias okrągły 2 przecinek n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 15. fibonacci znak równości otwórz nawias kwadratowy rek podkreślnik fib otwórz nawias okrągły x zamknij nawias okrągły for x in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 16. zlota znak równości otwórz nawias kwadratowy otwórz nawias okrągły fibonacci otwórz nawias kwadratowy x zamknij nawias kwadratowy prawy ukośnik fibonacci otwórz nawias kwadratowy x minus 1 zamknij nawias kwadratowy zamknij nawias okrągły for x in range otwórz nawias okrągły 2 przecinek n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 18. kratka wypisujemy na ekranie listę wartości. Linia 19. print otwórz nawias okrągły zlota zamknij nawias okrągły. Linia 21. kratka wyświetlamy okno z wykresem. Linia 22. kratka cudzysłów o dwukropek cudzysłów minus punkty połączone przerywaną linią. Linia 23. plt kropka plot otwórz nawias okrągły lista podkreślnik x przecinek zlota przecinek cudzysłów o dwukropek cudzysłów zamknij nawias okrągły. Linia 24. plt kropka grid otwórz nawias okrągły True zamknij nawias okrągły. Linia 25. plt kropka xlabel otwórz nawias okrągły apostrof n apostrof zamknij nawias okrągły. Linia 26. plt kropka ylabel otwórz nawias okrągły apostrof stosunek wyrazu ciągu Fibonacciego o indeksie n do wyrazu o indeksie n minus 1 apostrof zamknij nawias okrągły. Linia 27. plt kropka show otwórz nawias okrągły zamknij nawias okrągły. Linia 29. kratka przykład wykonania. Linia 30. fibonacci podkreślnik zlota otwórz nawias okrągły 24 zamknij nawias okrągły. Linia 31. otwórz nawias kwadratowy 1 kropka 0 przecinek 2 kropka 0 przecinek 1 kropka 5 przecinek 1 kropka 6666666666666667 przecinek 1 kropka 6 przecinek 1 kropka 625 przecinek. Linia 32. 1 kropka 6153846153846154 przecinek 1 kropka 619047619047619 przecinek. Linia 33. 1 kropka 6176470588235294 przecinek 1 kropka 6181818181818182 przecinek. Linia 34. 1 kropka 6179775280898876 przecinek 1 kropka 6180555555555556 przecinek. Linia 35. 1 kropka 6180257510729614 przecinek 1 kropka 6180371352785146 przecinek. Linia 36. 1 kropka 618032786885246 przecinek 1 kropka 618034447821682 przecinek. Linia 37. 1 kropka 6180338134001253 przecinek 1 kropka 618034055727554 przecinek. Linia 38. 1 kropka 6180339631667064 przecinek 1 kropka 6180339985218033 przecinek. Linia 39. 1 kropka 618033985017358 przecinek 1 kropka 6180339901755971 zamknij nawias kwadratowy.

def fibonacci_zlota(n):
    # wczytanie modułu rysującego
    import matplotlib.pyplot as plt
    
    # definicja funkcji pomocniczej
    def rek_fib(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return rek_fib(n - 1) + rek_fib(n - 2)
    
    lista_x = [ x for x in range(2,n) ]
    fibonacci = [ rek_fib(x) for x in range(n) ]
    zlota = [ (fibonacci[x] / fibonacci[x-1]) for x in range(2,n) ]
    
	# wypisujemy na ekranie listę wartości
    print(zlota)        
    
    # wyświetlamy okno z wykresem
    # "o:" - punkty połączone przerywaną linią
    plt.plot(lista_x,zlota,"o:")
    plt.grid(True)
    plt.xlabel('n')
	plt.ylabel('stosunek wyrazu ciągu Fibonacciego o indeksie n do wyrazu o indeksie n - 1')
    plt.show()
    
# przykład wykonania
fibonacci_zlota(24)
[1.0, 2.0, 1.5, 1.6666666666666667, 1.6, 1.625,
 1.6153846153846154, 1.619047619047619, 
 1.6176470588235294, 1.6181818181818182,
 1.6179775280898876, 1.6180555555555556, 
 1.6180257510729614, 1.6180371352785146,
 1.618032786885246, 1.618034447821682, 
 1.6180338134001253, 1.618034055727554,
 1.6180339631667064, 1.6180339985218033, 
 1.618033985017358, 1.6180339901755971]

Wynikiem będzie wykres prezentujący zależność odchylenia od wartości złotej liczby, dla kolejnych wyrazów ciągu Fibonacciego:

RwJy1iFhJDIfZ

Wykres pokazujący wynik przykładu 2. Wykres zaczyna się przy wartości: 1, osi Y, następnie przechodzi do wartości: 2, następnie wartości stabilizują się w okolicach wartości 1,618. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 1

Napisz w języku Python program, który będzie wyznaczał wyraz ciągu Fibonacciego o indeksie n.

Specyfikacja problemu:

Dane:

n – liczba naturalna, indeks wyznaczanego elementu

Wynik:

Na wyjściu standardowym program wypisze wyraz ciągu Fibonacciego o indeksie n.

RiqFJmHK0STVO

Ćwiczenie 2

R1Cw2gPscP9eq

Słownik

Fibonacci

włoski matematyk, ur. ok. $1175$ r., znany jako Leonardo Fibonacci, Filius Bonacci (syn Bonacciego), Leonardo Pisano (Leonardo z Pizy)

liczby naturalne

liczby całkowite nieujemne

matplotlib

biblioteka służąca do przedstawienia obrazów złożonych z punktów o współrzędnych x oraz y (wykresów, histogramów, rozkładów itp.); moduł matplotlib nie jest dostępny w standardowej instalacji Pythona; należy go zainstalować, korzystając z mechanizmu pip

przestrzeń nazw

(ang. namespace) miejsce w pamięci operacyjnej, w której jest przechowywana dana zmienna; najczęściej przestrzeń nazw jest związana z funkcją, a zmienne w niej używane są widoczne tylko w obrębie tej przestrzeni – jest to „zakres obowiązywania” tych zmiennych

złota liczba

inaczej boska proporcja (łac. divina proportio) – liczba, której wartość wynosi w przybliżeniu 1.618033988...; w geometrii podział odcinka na dwie części, tak by stosunek długości dłuższej z nich do krótszej był taki sam, jak całego odcinka do części dłuższej

Schemat interaktywny

Sprawdź się

Ciąg Fibonacciego – podsumowanie

Rekurencja

Iteracja

Złota liczba

Słownik