Ciąg Fibonacciego




Pobierz 29.49 Kb.
NazwaCiąg Fibonacciego
Data konwersji15.12.2012
Rozmiar29.49 Kb.
TypDokumentacja
Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:

Pierwsze dwa wyrazy ciągu równe są 1, każdy następny jest sumą dwóch poprzednich.

Formalnie:



Kolejne wyrazy tego ciągu nazywamy liczbami Fibonacciego. Kwestia, czy zaliczać zero do ciągu Fibonacciego jest dyskusyjna. Część autorów rozpoczyna ciąg od .

Wyrazy ciągu Fibonacciego to:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Ciąg został podany w 1202 roku przez Leonarda z Pizy zwanego Fibonaccim w swoim dziele Liber abaci jako rozwiązanie zadania o rozmnażaniu się królików. Nazywanie tego ciągu jako ciąg Fibonacciego spopularyzował w XIX w. Edward Lucas.


Wzór Bineta


Jawny wzór na n-ty wyraz ciągu Fibonacciego możemy otrzymać np. korzystając z metody funkcji tworzących.

Zdefiniujmy ciąg i dla tego ciągu fn obliczmy wzór na jego n-ty wyraz.

Funkcja tworząca dla tego ciągu ma postać



Podstawiając otrzymujemy:







tak więc: Wyrażenie możemy przedstawić w prostszej postaci, a mianowicie:

gdzie

wówczas tak więc

Podstawiając otrzymujemy ostatecznie tzw. wzór Bineta :



Ponieważ drugi człon tego wyrażenia szybko zbiega do zera


Własności


Można też wyrazić wartości kolejnych elementów ciągu za pomocą symbolu Newtona :



Zachodzą równości:





(równanie ilustruje rysunek)











Kilka mniej znanych twierdzeń na temat ciągu Fibonacciego:

  • Z wyjątkiem jednocyfrowych liczb Fibonacciego (liczb występujących w ciągu Fibonacciego), zawsze cztery albo pięć następujących po sobie wyrazów ciągu ma tę samą liczbę cyfr w układzie dziesiętnym.

  • Jedynymi liczbami w całym ciągu Fibonacciego, będącymi kwadratami liczb całkowitych są 1 i 144.

  • Co trzecia liczba Fibonacciego jest podzielna przez 2, co czwarta – przez 3. Ogólniej: jeśli numer n dzieli się przez k, to liczba Fn dzieli się przez Fk. Zachodzi jeszcze silniejszy związek: największy wspólny dzielnik dwóch liczb Fibonacciego jest liczbą Fibonacciego, której numer jest równy największemu wspólnemu dzielnikowi numerów tych liczb:

  • Każda niezerowa liczba całkowita ma wielokrotność będącą liczbą Fibonacciego.

  • Istnieje nieskończenie wiele liczb n dla których zachodzi podzielność n | Fn. W szczególności można pokazać, że jeśli to .

Obliczanie liczb Fibonacciego


Teoretycznie wartości kolejnych wyrazów ciągu Fibonacciego mogą być obliczone wprost z definicji, jest to jednak metoda na tyle wolna, że stosowanie jej ma tylko sens dla niewielu początkowych wyrazów ciągu, nawet na bardzo szybkich komputerach. Wynika to z tego, że definicja Fn wielokrotnie odwołuje się do wartości poprzednich wyrazów ciągów. Drzewo wywołań takiego algorytmu dla parametru n musi mieć co najmniej Fn liści o wartości 1. Ponieważ ciąg Fibonacciego rośnie wykładniczo, oznacza to wyjątkowo słabą wydajność.

Istnieje równie prosta i znacznie szybsza metoda. Obliczamy wartości ciągu po kolei: F0, F1, F2 i tak aż do Fn, za każdym razem korzystając z tego, co już obliczyliśmy. Nie musimy nawet zapamiętywać wszystkich obliczonych dotychczas wartości – ponieważ wystarczą dwie ostatnie. Daje to złożoność liniową – o wiele lepszą od wykładniczej złożoności poprzedniej metody. Metoda ta może być postrzegana jako zastosowanie programowania dynamicznego.

Fibonacci( n )

if n=0 then return 0

if n=1 then return 1

f' ← 0

f ← 1

for i ← 2 to n

do

m ← f + f'

f' ← f

f ← m

end

return f


Można zrobić to jeszcze szybciej dzięki zależności:



Ponieważ równocześnie:



to indukcyjnie:



A ponieważ istnieją bardzo wydajne algorytmy potęgowania macierzy, możemy wyliczyć dowolny wyraz ciągu Fibonacciego za pomocą logarytmicznej ilości mnożeń.

Graficzna reprezentacja dwójkowa




Ciąg Fibonacciego w systemie dwójkowym

Jeśli kolejne wyrazy ciągu zapisać w systemie dwójkowym, jeden pod drugim, z wyrównaniem do prawej strony to otrzymamy wydłużający się w dół trójkąt, którego elementy powtarzają się ("czubek" pojawia się poniżej, przy prawej krawędzi, w coraz dłuższym rozwinięciu - pojawia się nad nim "biały trójkąt"), co czyni go podobnym do fraktala. Dla lepszej przejrzystości na rysunku obok wszystkie zera zastąpiono białymi punktami, a jedynki - czarnymi.

Złota liczba


granica ciągu



czyli ilorazów sąsiadujących ze sobą wyrazów ciągu Fibonacciego to tzw. złota liczba lub złota proporcja definiowana jako dodatnie rozwiązanie równania :

lub równoważnego

Dowód (zakładający istnienie takiej granicy):













Jest ona także pierwiastkiem wielomianu x² − x − 1 oraz równania x + x−2 = 2

Zauważmy, że w powyższym dowodzie informacja o początkowych wyrazach ciągu czy też jakichkolwiek innych nie była wykorzystywana. Przeto dla dowolnego ciągu



zachodzi wzór : Czasem taki ciąg G również nazywany jest ciągiem Fibonacciego lub uogólnionym ciągiem Fibonacciego. Jeżeli a i b nie są równocześnie zerami to granica ciągu jest taka sama jak dla 'oryginalnego' ciągu Fibonacciego.

Kolejne wyrazy ciągu : są także wartością n-tego odcinka ułamka łańcuchowego :

wartościami kolejnych 'odcinków' są liczby:


Liczby pierwsze w ciągu Fibonacciego


Kilka początkowych wyrazów w ciągu Fibonacciego to także liczby pierwsze a mianowicie: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229.. Wydaje się prawdopodobne, że liczb pierwszych w ciągu Fibonacciego istnieje nieskończenie wiele, lecz problem ten jak dotąd nie doczekał się rozstrzygnięcia.


Ciąg liczbowy Fibonacciego

Spośród wszystkich ciągów liczbowych, które występują, jeden jest szczególnie interesujący. Ciąg ten zawdzięcza swoją nazwę matematykowi z Pizy, Leonardowi, który pod nazwiskiem Fibonacci wydał w 1202 roku słynną księgę Liber Abaci. Ojciec Leonarda nosił przydomek Bonacci, stąd syn został Fibonaccim (filius Bonacci - syn dobrotliwego) Liczby naturalne tworzące ciąg o takiej własności, że kolejny wyraz (z wyjątkiem dwóch pierwszych) jest sumą dwóch poprzednich nazywa się liczbami Fibonacciego i pojawiają się w tak wielu sytuacjach, że wydaje się to niemożliwe.

Ciąg Fibonacciego to ciąg liczb określony rekurencyjnie w sposób następujący:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2,   dla n ≥ 2

Początkowe wartości tego ciągu to:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Podstawowy ciąg liczb Fibonacciego to: 1, 1, 2, 3, 5, 8, ... Każda liczba w ciągu jest sumą dwóch poprzednich (poza pierwszą i drugą). Mamy więc do czynienia z ciągiem rekurencyjnym. Ciąg liczbowy Fibonacciego jest pierwszym ze znanych ciągów tego rodzaju.

W wyniku podzielenia każdej z liczb ciągu przez jej poprzednik otrzymuje się iloraz oscylujący wokół 1,618 - liczby złotego podziału. W miarę zwiększania się liczb zmniejszają się odchylenia od tej wartości. Dokładna wartość granicy jest złotą liczbą: Φ = 5 + 1 2 = 1,6180339887498948482...

Liczby Fibonacciego można wyznaczyć ze wzoru:
Fn+1=n0+n-11+n-22+...
Liczby Fibonacciego są więc sumami liczb z przekątnych w trójkącie Pascala.


Matematycy i naukowcy odkryli, że ciąg Fibonacciego można odnaleźć w wielu aspektach przyrody. Taki ciąg liczbowy opisuje liczbę pędów rośliny jednostajnie przyrastającej w latach. W słoneczniku możemy zaobserwować dwa układy linii spiralnych, wychodzących ze środka. Liczba linii rozwijających się zgodnie z ruchem wskazówek zegara wynosi 55 i tylko 34 skręconych w przeciwną stronę. Takie same spirale można zaobserwować na wielu innych roślinach, takich jak kalafior, ananas czy szyszki. Liczby spiral występujących w tych roślinach są kolejnymi liczbami Fibonacciego.

Złotymi proporcjami wyznaczonymi na podstawie ciągu Fibonacciego posługiwał się w swoim malarstwie Leonardo da Vinci i Botticelli. W XX wieku ciąg Fibonacciego stosowany był także przez niektórych kompozytorów do proporcjonalnego porządkowania rytmu lub harmonii. Na ciągu Fibonacciego zbudowane jest między innymi Trio klarnetowe Krzysztofa Meyera.
Złote proporcje wykorzystano także podczas wznoszenia piramidy Cheopsa w Gizie i Partenonu w Grecji.

Dodaj dokument na swoim blogu lub stronie

Powiązany:

Ciąg Fibonacciego iconZłota liczba I ciąg Fibonacciego

Ciąg Fibonacciego iconCiąg Fibonacciego elementarne formuły I tożsamości

Ciąg Fibonacciego iconWykład 5 I 6 Szeregi liczbowe Niech dany będzie ciąg nieskończony Tworzymy dla niego ciąg sum częściowych

Ciąg Fibonacciego iconWspółczynniki Fibonacciego

Ciąg Fibonacciego iconTemat 1 Liczby Fibonacciego I „złoty podział”

Ciąg Fibonacciego iconPierwsze Reprezentacyjne Przykłady Występowania Ciągu Fibonacciego

Ciąg Fibonacciego iconCiąg liczbowy an

Ciąg Fibonacciego iconZabawy ciąg dalszy…

Ciąg Fibonacciego iconBushu ciag dalszy

Ciąg Fibonacciego iconPornografia ciąg dalszy

Umieść przycisk na swojej stronie:
Rozprawki


Baza danych jest chroniona prawami autorskimi ©pldocs.org 2014
stosuje się do zarządzania
Rozprawki
Dom