Fibonaccijevo število
Fibonaccijeva števila, ki določajo Fibonaccijevo zaporedje, so v matematiki rekurzivno določena z naslednjimi enačbami:
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]
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
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
urediIzraz 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 značilnosti. 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:
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
urediRač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 toč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:
ki namesto potenciranja uporablja kvadriranje.
Uporabe
urediFibonaccijeva š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
urediPosploš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
urediV 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
urediPoleg 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
urediFibonaccijeva števila je uporabil Dan Brown v svoji knjigi Da Vincijeva šifra.
Glej tudi
urediSklici
uredi- ↑ Knott (1996-2011).
- ↑ Aimi, Antonio; De Pasquale, Nicolino. »ANDEAN CALCULATORS« (PDF) (v angleščini).
- ↑ Douady; Couder (1996).
- ↑ »The Fibonacci Numbers and the Ancestry of Bees« (v angleščini). Pridobljeno 3. decembra 2009.
- ↑ Prusinkiewicz; Lindenmayer (1990).
Viri
uredi- Douady, S; Couder, Y. (1996). »Phyllotaxis as a Dynamical Self Organizing Process« (PDF). Journal of Theoretical Biology. Zv. 178, št. 178. str. 255–274. doi:10.1006/jtbi.1996.0026. Arhivirano iz prvotnega spletišča (PDF) dne 26. maja 2006. Pridobljeno 3. decembra 2009.
- Knott, Ron (1996–2011), »Fib table«, Fibonacci (v angleščini), Združeno kraljestvo: Surrey, pridobljeno 10. maja 2013. Stran navaja prvih 300 Fibonaccijevih števil 300 Fn razstavljenih na prafaktorje in povezavami na druge obsežnejše razpredelnice.
- Prusinkiewicz, P.; Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer-Verlag. str. 101–107. ISBN 978-0387972978.