Ciąg Fibonacciego to słynny ciąg liczbowy, w którym pierwsze dwa wyrazy to 0 i 1, a każdy kolejny jest sumą dwóch poprzednich. Początkowe liczby to 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
def fibonacci(r: int) -> None:
a, b = 0, 1
for _ in range(r):
print(a)
a, b = b, a + ba — aktualna liczba, b — następna liczba, nowe b — suma dwóch poprzednich.
Algorytm ma złożoność O(n) i przy wypisywaniu n liczb praktycznie nie da się zrobić go szybciej — samo wypisanie n elementów wymaga n operacji.
Może zainteresować Cię również
Wyszukiwanie binarne pozwala szybko znaleźć element w liście poprzez wielokrotne dzielenie przeszukiwanego zakresu na pół. Zamiast sprawdzać każdy element po kolei, algorytm porównuje szukaną wartość ze środkowym elementem listy i odrzuca połowę pozostałych danych.