Ciąg Fibonacciego - ciąg, którego wyrazy są sumą 2 poprzednich wyrazów. 2 początkowe wyrazy wynoszą: F0 = 0, F1 = 1.
Najłatwiejszym sposobem na stworzenie programu podającego konkretny wyraz ciągu Fibonacciego jest rekurencja, poznana na poprzedniej lekcji.
def fib(n):
if n<2:
return n
else:
return fib(n-1)+fib(n-2)
n=int(input())
print(fib(n))
5
5
7
13
Patrząc teraz na program, zastanówmy się w jaki sposób komputer odczytuje kolejne komendy. Na początku wprowadzamy do funkcji zmienną. Będzie ona którymś z kolei wyrazem ciągu Fibonacciego. Następnie sprawdzamy jej wartość, jeżeli jest ona równa 0 lub 1 oznacza to, że wyraz ciągu o tym numerze przyjmuje wartość 0 lub 1. W przeciwnym wypadku chcemy, aby program zwrócił nam sumę wartości poprzednich wyrazów ciągu. W tym momencie następuje cała magia rekurencji. Wywołujemy funkcje z argumentem o 1 i o 2 mniejszym, gdyż wartość, którą chcemy uzyskać, jest ich sumą. Komputer musi wykonać całą funkcję dla argumentów o 1 i o 2 mniejszych. Będzie on powtarzał tę czynność tak długo, aż cofnie się do pierwszego lub drugiego wyrazu ciągu. Wtedy znając wszystkie wartości, będzie on mógł podać żądanie, które wysłaliśmy na początku. Choć ten sposób jest dużo prostszy do zapisania i zrozumienia dla osoby programującej, jest on bardzo obciążający dla procesora(przetestuj program np. dla 40). Komputer nie potrafi myśleć tak jak ludzie, przez co często liczy on kilkakrotnie te same wyrażenia. Zastanówmy się teraz czy można stworzyć funkcję dla ciągu Fibonacciego bez użycia rekurencji. Jest na to sposób nieco trudniejszy niż rekurencja, ale mniej obciąża on komputer, więc bardzo zyskujemy na szybkości szczególnie przy dużych danych.
def fib(n):
if n<2:
return n
a=0
b=1
for i in range(n):
b=a+b
a=b-a
return a
n=int(input())
print(fib(n))
5
5
7
13
Porównajmy programy z rekurencją i bez na poniższym przykładzie:
Ciąg Tribonacciego - ciąg, którego wyrazy są sumą 3 poprzednich wyrazów. 3 początkowe wyrazy wynoszą: F0 = 0, F1 = 0, F2 = 1.
def trib(n):
if n<2:
return 0
if n==2:
return 1
else:
return trib(n-1)+trib(n-2)+trib(n-3)
n=int(input())
print(trib(n))
def trib(n):
if n<2:
return 0
if n==2:
return 1
a=0
b=0
c=1
for i in range(n-2):
c=a+b+c
b=c-a-b
a=c-b-a
return c
n=int(input())
print(trib(n))