Fibonaccijevo število

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Fibonaccijeva števila, ki določajo Fibonaccijevo zaporedje, so v matematiki rekurzivno določena z naslednjimi enačbami:


  F_n  \equiv F(n)=
  \left\{
   \begin{matrix}
    1;\,\qquad\qquad\qquad\quad\,\ \ \, && n=0\,;\ \ \\
    1;\qquad\qquad\qquad\qquad\, && n=1;\ \ \,\\
    F(n-2)+F(n-1); && n>1.
   \end{matrix}
  \right.

Zaporedje začnemo z dvema številoma, običajno 1 in 1. Naslednje Fibonaccijevo število dobimo, če seštejemo predhodni. Prva Fibonaccijeva števila so (OEIS A000045):[1]

F_{ 0}\, F_{ 1}\, F_{ 2}\, F_{ 3}\, F_{ 4}\, F_{ 5}\, F_{ 6}\, F_{ 7}\, F_{ 8}\, F_{ 9}\, F_{10}\, F_{11}\, F_{12}\, F_{13}\, F_{14}\, F_{15}\, F_{16}\, F_{17}\, F_{18}\, F_{19}\, F_{20}\, F_{21}\,
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
Pokritje ravnine s kvadrati v velikosti Fibonaccijevih števil
Jupana (kečuansko za orodje za štetje) je računalo, ki so ga uporabljali Inki. Raziskovalci menijo da so računi temeljili na Fibonaccijevih številih da se je zmanjšalo število potrebnih zrn na polje.[2]
Fibonaccijeva spirala tvorjena z risanjem lokov, ki povezujejo nasprotni oglišči kvadratov v Fibonaccijevem pokritju. Tu so kvadrati velikosti 1, 1, 2, 3, 5, 8, 13, 21 in 34; glej zlata spirala
Stran iz Fibonaccijevega dela Knjiga o abaku (Liber Abaci; Nacionalna centralna knjižnica v Firencah) prikazuje Fibonaccijevo zaporedje (uokvirjeno desno) s členi od 0 do 12 označenimi s črno z rimskimi in rdečo z indoarabskimi številkami
Fibonaccijevo zaporedje zvokovno, harmonični intervali naraščajo, melodični pa padajo.

To zaporedje je prvi opisal Leonardo Fibonacci pri opisu rasti določenega števila zajcev. Števila opisujejo število parov idealiziranega števila zajcev po n mesecih, če upoštevamo:

  • prvi mesec se rodi samo en nov par,
  • novorojeni pari so plodni od svojega drugega meseca naprej,
  • vsak mesec vsak ploden par zaplodi nov par in
  • zajci nikoli ne umrejo.

Enačba[uredi | uredi kodo]

Izraz Fibonaccijevega zaporedja lahko uporabimo splošneje na vsaki funkciji g, kjer je g(n + 2) = g(n) + g(n + 1). Te funkcije so natanko tiste oblike g(n) = aF(n) + bF(n + 1) za poljubna števila a in b, tako da Fibonaccijeva zaporedja tvorijo vektorski prostor s funkcijami F(n) in F(n + 1) kot baza.

Kot je pokazal Kepler, stopnja rasti Fibonaccijevih števil, F(n + 1) / F(n), konvergira k številu zlatega reza, označenem z φ. To je pozitivni koren kvadratne enačbe x2 - x - 1 = 0, tako da je φ2 = φ + 1. Če pomnožimo obe strani z φn, dobimo φn+2 = φn+1 + φn, in je funkcija φn Fibonaccijevo zaporedje. Lahko se pokaže, da ima negativni koren kvadratne enačbe, 1 - φ, enake lastnosti. Zato funkciji φn in (1-φ)n tvorita novo bazo istega prostora.

Z nastavitvijo koeficientov za primerne začetne vrednosti F(0) = 1 in F(1) = 1, dobimo:

F\left(n\right) = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}} .

Isti rezultat dobimo, če uporabimo postopke rodovnih funkcij ali reševanja linearnih rekurenčnih enačb.

Ko gre n v neskončnost, drugi člen konvergira proti nič, tako, da Fibonaccijeva števila težijo k eksponentu φn / √5, in zaradi tega njihova razmerja konvergirajo. V bistvu je drugi člen dovolj majhen in lahko dobimo Fibonaccijeva števila samo iz prvega člena, če jih zaokrožamo na najbližje celo število.

Računanje Fibonaccijevih števil[uredi | uredi kodo]

Računanje Fibonaccijevih števil z računanjem potenc števila zlatega reza ni preveč praktično, razen za majhne vrednosti n, ker se bodo zaokrožitvene napake povečale in števila s tekočo vejico po navadi niso dovolj natančna.

Tudi neposredna rekurzivna uporaba določitve Fibonaccijevega zaporedja ni preveč prikladna, ker moramo računati preveč vrednosti zaporedoma (razen če programski jezik dovoljuje shrambo predhodnih vrednosti fukcije). Zato po navadi računamo Fibonaccijeva števila od spodaj navzgor. Začnemo z vrednostima 1 in 1, potem pa izmenoma zamenjujemo prvo število z drugim, drugo število pa z vsoto prejšnjih dveh.

Za velike vrednosti in, če uporabimo programski jezik z možnostjo računanja velikih števil, je hitrejša pot računanja Fibonaccijevih števil z naslednjo matrično enačbo:

\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =
       \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\
                       F\left(n\right)   & F \left(n-1\right) \end{bmatrix} ,

ki namesto potenciranja uporablja kvadriranje.

Uporabe[uredi | uredi kodo]

Fibonaccijeva števila so pomembna pri analizi poteka Evklidovega algoritma za določitev največjega skupnega delitelja dveh celih števil. Izkaže se, da se algoritem najslabše izkaže ravno v primeru, ko določamo največji skupni delitelj dveh zaporednih Fibonaccijevih števil.

Matijasevič je pokazal, da lahko Fibonaccijeva števila določimo s posebno diofantsko enačbo, kar nas vodi do njegove izvirne rešitve 10. Hilbertovega problema.

Fibonaccijeva števila se pojavijo v enačbi za diagonale Pascalovega trikotnika.

Zanimiva uporaba Fibonaccijevega zaporedja je pri pretvarjanju milj v kilometre. Na primer, če bi radi vedeli koliko kilometrov je 5 milj, vzamemo Fibonaccijevo število (5) in poiščemo naslednje (8). 5 milj je približno 8 kilometrov. To deluje ker je pretvorbeni količnik med miljami in kilometri približno enak φ.

Logaritmično spiralo lahko poenostavimo, če začnemo v središču kartezičnega koordinatnega sestava, se premaknemo za F(1) enot v desno, za F(2) enot navzgor, za F(3) enot v levo, za F(4) enot navzdol, za F(5) enot v desno in tako naprej. To je podobno konstrukciji, omenjeni v članku o zlatem rezu. Fibonaccijeva števila se v naravi pojavijo velikokrat, kadar so logaritmične spirale sestavljene iz nezveznih enot, kot so tiste pri sončnicah ali pri borovih storžih.

Posplošitve[uredi | uredi kodo]

Posplošitev Fibonaccijevega zaporedja so Lucasova zaporedja. Eno vrsto lahko določimo z:

L(0) = 0
L(1) = 1
L(n+2) = PL(n+1) + QL(n)

kjer je običajno Fibonaccijevo zaporedje poseben primer P = Q = 1. Druga vrsta Lucasovega zaporedja se začne z L(0) = 2, L(1) = P. Takšna zaporedja se uporabljajo v teoriji števil in dokazovanju praštevilskosti.

Algoritem[uredi | uredi kodo]

V pascalu lahko rekurzivni postopek prepišemo neposredno :

function F(n:integer):integer;
begin
  if (n=0) or (n=1) then 
    F := 1
  else
    F := F(n-1) + F(n-2);
end;{F}

Vendar je taka neposredna uporaba rekurzije zelo neučinkovita in pravzaprav služi kot šolski primer, kako je ne smemo uporabljati. Učinkovitejši je iterativni postopek:

function F(n:integer):integer;
var a,b,c,j : integer;
begin
  a:=1; b:=1;
  for j:=3 to n do begin
    c := a+b;  a := b;  b := c;
  end;
  F := c;
end;{F}

V javi (kot metoda) bi algoritem zgledal tako:

static int fibonacci (int n) {	
  int f=0,f1=1,f2=1;
  for (int i=1; i<=n;i++) {
    if (i<3) f=1;
    else {
	f=f1+f;
	f1=f2;
	f2=f;
    }
}

Fibonaccijeva števila v naravi[uredi | uredi kodo]

Sončnica ima semena razporejena v dve družini, pri čemer je v eni 34 spiralnih zavojev, v drugi pa 55 zavojev. (glej tudi Fermatova spirala)
Glava cvetlice barvilna pasja kamilica (Cota tinctoria) kaže postavitev 21-h (modro) in 13-h (zelenomodro) spiralnih zavojev

Poleg rasti določenega števila zajcev so Fibonaccijeva števila tudi drugod v naravi,[3] npr. pri številu venčnih listov in v spiralnih strukturah, ki jih mnoge rastline uporabljajo za razporeditev semen (glej tudi Fermatova spirala). Poleg števila parov zajcev je znan primer tudi število čebel pri idealiziranemu razmnoževanju, če upoštevamo da:

  • se iz neoplojenega jajčeca izvali samec,
  • se iz jajčeca, ki ga oplodi samec, izvali samica.

Samec bo tako vedno imel enega starša, samica pa dva. Če analiziramo število prednikov kateregakoli samca (1), bo ta imel vedno enega starša, tj. samico (1). Slednja ima dva starša, samca in samico (2), ta samec pa bo prav tako imel enega starša in samica dva starša, kar da število 3.[4] V praksi se še danes uporablja izpopolnjene različice Fibonaccijeve sheme pri preučevanju drugih živalskih populacij.

Pri nekaterih cvetnicah so ta števila jasno izražena pri venčnih listih. Tako imajo lilije 3 venčne liste, zlatice 5, ostrožniki pogosto 8, ognjič 13, astre 21 in marjetice ter sončnice navadno po 34, 55 ali 89 listov. Lahko se pojavijo manj običajna števila, in sicer dvojna Fibonaccijeva števila, kar je posledica tehnike gojenja rastlin, ki podvoji število listov, ali pa podobna nepravilna zaporedja (npr. 1, 3, 4, 7, 18, ...). Pri razporeditvi semen so znani primer sončnice, ki imajo semena razporejena v dve družini, pri čemer je v manjših sončnicah v eni družini 34 spiralnih zavojev, v drugi pa 55, pri večjih pa sta ti dve števili 55 in 89 ali 89 in 144. Tudi luske na jelovih storžih so tipično razporejene v dveh družinah prepletenih spiral; storž norveške jelke ima tako 5 zavojev lusk v eni družini, v drugi pa 3.[5]

Fibonaccijeva števila v leposlovju[uredi | uredi kodo]

Fibonaccijeva števila je uporabil Dan Brown v svoji knjigi Da Vincijeva šifra.

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  1. ^ Knott (1996-2011).
  2. ^ http://www.quipus.it/english/Andean%20Calculators.pdf
  3. ^ Douady, S. & Couder, Y. (1996). "Phyllotaxis as a Dynamical Self Organizing Process". Journal of Theoretical Biology 178 (178): 255–274. doi:10.1006/jtbi.1996.0026. 
  4. ^ The Fibonacci Numbers and the Ancestry of Bees Pridobljeno 03.12.2009.
  5. ^ Prusinkiewicz, P.; Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer-Verlag. str. 101–107. ISBN 978-0387972978. 

Viri[uredi | uredi kodo]

  • Knott, Ron (1996-2011), "Fib table", Fibonacci (angleščini), Združeno kraljestvo: Surrey, pridobljeno dne 2013-05-10 . Stran navaja prvih 300 Fibonaccijevih števil 300 Fn razstavljenih na prafaktorje in povezavami na druge obsežnejše razpredelnice.