algorytm.org

Ciąg Fibonacciego

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Ciąg Fibonacciego
Ocena użytkowników:***** / 126
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 26 lipca 2005 23:08

Ciąg Fibonacciego wyraża się rekurencyjnym wzorem: f(n)=f(n-2)+f(n-1), gdy f(1)=1 oraz f(2)=1.
Łatwo obliczyć, że:
f(3)=f(1)+f(2)=1+1=2
f(4)=f(2)+f(3)=1+2=3
f(5)=f(3)+f(4)=2+3=5

Rekurencyjne obliczanie n-tego wyrazu ciągu Fibonacciego może być opisane następującym schematem blokowym:
schemat blokowy - ciąg Fibonacciego (rekurencyjnie)


Rekurencyjne obliczanie wartości zajmuje O(2n) czasu i dla bardzo dużych wartości n jest niepraktyczne. O wiele szybciej - w czasie O(log(n)) można obliczyć n-ty wyraz ciągu Fibonacciego używając szybką rekurencję modularną.



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 7
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 12
Michał KnasieckiC/C++
.cpp
.cpp
***** / 20
MarianC/C++C++
.cpp
.cpp
***** / 20
_marass_C/C++wersja iteracyjna
.cpp
.cpp
***** / 30
Bartosz BednarczykC/C++C++ wersja iteracyjna dla dużych liczb
.cpp
.cpp
***** / 6
Krzysztof KozłowskiC/C++bez rekurencji, bez iteracji - wzór ogólny
.cpp
.cpp
***** / 6
Michał KnasieckiDelphi/PascalBorland Delphi
.pas
.pas
***** / 6
Adam ChrapkowskiHaskell
.hs
.hs
***** / 0
Tomasz LubińskiJava
.java
.java
***** / 18
Jakub KoniecznyJava_Block3 metody (w zakładkach)
.jbf
.jbf
***** / 2
_marass_Phpwersja iteracyjna
.php
.php
***** / 5
_marass_Phpwersja rekurencyjna
.php
.php
***** / 4
monikaPythonwersja z użyciem list
.py
.py
***** / 11
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 23 kwietnia 2012 09:06
Komentarze
photo
-9 # Okles 2009-08-22 17:50
A jak w takim razie obliczyć dla f(6)?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # Okles 2009-08-22 17:58
Już wiem
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Rafał info 2011-11-17 17:36
ten schemat jest zly... bo jaka wartosc jest dla 0? oczywiscie 0 natomiast program nie wykona tego polecenia... stwierdzi iz rownanie jest bledne...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # David 2011-11-29 16:48
Ale niektórzy matematycy do dzisiaj sprzeczają się o to czy ciąg Fibonacciego zaczynać od 0 czy od 1
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # dedos 2011-12-04 21:43
Cytuję Rafał info:
ten schemat jest zly... bo jaka wartosc jest dla 0? oczywiscie 0 natomiast program nie wykona tego polecenia... stwierdzi iz rownanie jest bledne...

Ten schemat jest poprawny bo dla 0 wartosc wynosi 1
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # 123navyblue 2012-04-14 09:39
Cytuję dedos:
Cytuję Rafał info:
ten schemat jest zly... bo jaka wartosc jest dla 0? oczywiscie 0 natomiast program nie wykona tego polecenia... stwierdzi iz rownanie jest bledne...

Ten schemat jest poprawny bo dla 0 wartosc wynosi 1


Po pierwsze, 0-owa liczba Fibonacciego wynosi 0.
pl.wikipedia.org/wiki/Ciąg_Fibonaccie go

Po drugie, czasami przyjmuje się że ciąg Fib. zaczyna się od 1, 1, 2, 3, 5... i indeksuje się go od jedynki.
Czyli:
fib(0) nie istnieje
fib(1) = 1
fib(2) = 1
...
Zatem jeżeli przyjmiemy powyższą definicję ciągu Fib. to schemat jest prawidłowy.

Po trzecie, myślę że schemat powinien być poprawiony tak aby dla 0 i wszystkich niepoprawnych indeksów (np. -17) zwracał 0.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Smoku 2012-11-15 22:06
A od kiedy to indeksy ujemne są niepoprawne? Ciąg fibonacciego w gimnazjum jest dla dodatnich, jednak sam w sobie jest zdefiniowany dla ujemnych.
fib(0)=0
fib(1)=1

fib(n)=
: fib(n-1)+fib(n-2) dla n>=2
: fib(n+1)-fib(n+2) dla n
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Tomasz Lubiński 2012-11-16 09:21
Smoku popełniłeś chyba błąd powinno być raczej:

fib(n) =
:0, dla n = 0
:1, dla n = 1
:fib(n-1) + fib(n-2), dla n >= 2
:fib(n+2) - fib(n+1), dla n < 0
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # 123navyblue 2013-01-17 18:23
Masz rację Smoku. Trochę przesadziłem z tym, że ujemne indeksy są niepoprawne. Jednak uważam, że na potrzeby tego artykułu wystarczy zdefiniowanie ciągu Fibonacciego dla liczb dodatnich i ewentualnie zera.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # qe3w3 2013-12-24 11:26
trzeba by sie Fibonacciego zapytać ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz