Fibonači skaitļi ir skaitļu virkne matemātikā, kas nosaukta Leonardo no Pizas, pazīstama kā Fibonači, vārdā. Fibonači 1202. gadā uzrakstīja grāmatu Liber Abaci ("Aprēķinu grāmata"), ar kuru šo skaitļu virkni ieviesa Rietumeiropas matemātikā, lai gan matemātiķi Indijā to jau zināja.
Pirmais skaitlis rakstā ir 0, otrais skaitlis ir 1, un katrs nākamais skaitlis ir vienāds ar divu skaitļu, kas atrodas tieši pirms tā, saskaitīšanu kopā. Piemēram, 0+1=1 un 3+5=8. Šī secība turpinās bezgalīgi.
To var pierakstīt kā atkārtošanās sakarību,
F n = F n - 1 + F n - 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} 
Lai tam būtu jēga, ir jānorāda vismaz divi sākumpunkti. Šeit F 0 = 0 {\displaystyle F_{0}=0}
un F 1 = 1 {\displaystyle F_{1}=1}
.
Piemēri un pirmie skaitļi
Piemēram, sākot no dotajiem sākuma nosacījumiem, virkne izskatās šādi:
- F0 = 0
- F1 = 1
- F2 = 1 (0 + 1)
- F3 = 2 (1 + 1)
- F4 = 3 (1 + 2)
- F5 = 5 (2 + 3)
- F6 = 8 (3 + 5)
- F7 = 13 (5 + 8)
- F8 = 21 (8 + 13)
- F9 = 34 (13 + 21)
- F10 = 55 (21 + 34)
Secība turpinās bezgalīgi: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Slēgtā forma (Binet formula) un zelta attiecība
Pastāv arī slēgtā (ne-reakursīvā) atbilde uz Fn, ko sauc par Binet formulu:
Fn = (φⁿ − ψⁿ) / √5, kur φ = (1 + √5)/2 un ψ = (1 − √5)/2.
Šī formula ļauj tieši aprēķināt n-to Fibonači skaitli (parasti izmantojot reālos skaitļus un noapaļošanu), un tā parāda, ka Fibonači skaitļi aug aptuveni kā φⁿ / √5, kur φ (zelta attiecība) ≈ 1.6180339887. Attiecība Fn+1 / Fn tuvinās φ, jo n palielinās.
Dažas svarīgas īpašības
- Atkārtošanās sakarība: Fn = Fn−1 + Fn−2.
- Gaidāmā izaugsme: Fn ≈ φⁿ / √5 — eksponenciāla izaugsme ar bāzi φ.
- Bezgalīgs raksturs: virkne ir bezgalīga, visi locekļi ir veseli skaitļi.
- Dalāmība: ja m | n, tad Fm | Fn. Tāpat gcd(Fm,Fn) = Fgcd(m,n).
- Modulārā periodiskība: Fibonači skaitļi modulā m atkārtojas ar kādu periodu (Pisano periods).
- Negatīvie indeksi: virkne var tikt paplašināta uz negatīviem indeksiem ar formulu F−n = (−1)n+1 Fn.
- Matricas forma: [[1,1],[1,0]]ⁿ = [[Fn+1,Fn],[Fn,Fn−1]], kas ļauj ātri aprēķināt Fn ar eksponentāciju pēc dalīšanas (fast exponentiation).
Aplēses un ģenerējošā funkcija
Ģenerējošā funkcija Fibonači virknei ir G(x) = x / (1 − x − x²). Tā ir noderīga, lai iegūtu sakarības un identitātes ar kombinatorikas palīdzību.
Aprēķināšanas metodes un sarežģītība
- Vienkāršā rekurence: rekursīva implementācija ir viegla, taču bez memoizācijas tai ir eksponenciāla laika sarežģītība O(φⁿ), jo tiek daudz dublētu izsaukumu.
- Iteratīva/dinamiskā pieeja: uzglabājot iepriekšējos divus elementus vai izmantojot tabulēšanu, var iegūt lineāru laiku O(n) un konstanta papildu atmiņa O(1).
- Ātrā dubultošanas metode (fast doubling): ļauj aprēķināt Fn reizināšanas soļu skaitā O(log n) izmantojot identitātes, tāpat kā matricas veids ar bināro eksponenciāciju.
- Binet formula: teorētiski sniedz konstanta laika formulu, bet praktiskai lietošanai lieliem n nepieciešama precīza aritmētika (piem., veselu skaitļu big-int), jo reālo skaitļu noapaļošana var radīt kļūdas.
Pielietojumi un parādības dabā
- Fibonači skaitļi un zelta attiecība parādās botānikā (lapu izvietojums jeb filotaksija), čaumalu virsmu spirālēs un citos dabas rakstos.
- Tie ir nozīmīgi kombinatorikā (piem., skaita veidi, kā sadalīt objektus), algoritmos (rekurzīvas struktūras, dinamiski algoritmi), un kriptogrāfijā vai kodēšanā parādās atsevišķos kontekstos.
- Mākslā un arhitektūrā zelta attiecība, kas saistīta ar Fibonači, tiek uzskatīta par estētiski patīkamu proporciju.
Noslēgums
Fibonači skaitļi ir vienkārša, tomēr ļoti bagāta struktūra ar daudziem matemātiskiem un praktiskiem lietojumiem. No vienkāršas rekurences rodas daudzas interesantas īpašības — no zelta attiecības līdz dalāmības likumiem un ātrām aprēķina metodēm. Ja nepieciešams, varam izskaidrot konkrētas identitātes, pierādījumus (piem., Binet formulas atvasinājumu), vai parādīt praktiskas programmatūras īstenošanas piemērus.
