Șirul lui Fibonacci


Editat de Candale Silviu (silviu) la data 2019-11-13
Etichete: Fibonacci

De pe Wikipedia :

Leonardo Pisano Bogollo, (c. 1170 – c. 1250) cunoscut și sub numele de Leonardo din Pisa, Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci, sau pur și simplu Fibonacci, a fost un matematician italian considerat de unii drept “cel mai talentat matematician din Occidentul Evului Mediu”.

Fibonacci este cel mai bine cunoscut lumii moderne pentru:

  • Răspândirea sistemului de numărare hindu-arab în Europa, prin publicarea în primul rând la începutul secolului al 13-lea a cărții sale denumită Cartea de calcul , sau Liber Abaci.
  • Un șir de numere, care i-a purtat ulterior numele, și anume șirul lui Fibonacci, pe care el nu l-a descoperit, dar pe care l-a folosit ca un exemplu în cartea sa, Liber Abaci.

Definiție

Numerele Fibonacci sunt numere naturale care fac parte din următorul șir, în care fiecare număr este egal cu suma celor două de dinainte:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Uneori, șirul este extins cu încă un termen, la început:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Termenul Fn este calculat prin următoarea relație de recurență:

Fn = Fn-1 + Fn-2

cu valorile inițiale F1=1, F2=1 sau F0=0 și F1=1.

Algoritm de determinare a termenilor șirului

Cum determinăm primii N termeni din șirul lui Fibonacci? Vom folosi trei variabile simple a b c. Două dintre ele vor reprezenta termenii anteriori Fn-1 și Fn-2, iar a treia va reprezenta termenul curent Fn:

a ← 1 
b ← 1 
scrie a, b
pentru i ← 3,n execută
    c ← a + b
    scrie c
    a ← b
    b ← c
sfarsit_pentru 

Câteva proprietăți

Paritatea termenilor

Proprietate: \( F_n \) este par dacă și numai dacă \(n = 3k\).

Divizibilitatea numerelor Fibonacci

Proprietate: Fie \(n,m > 2\) două numere naturale. Atunci \(F_n | F_m \Leftrightarrow n | m \).

Demonstrație: aici.

Corolar: Fie \(n,m > 0\) două numere naturale. Atunci \(F_n | F_{n \cdot m}\).

Exprimarea unui termen în funcție de termeni mai mici

Proprietate: Fie \(n,m > 0\) două numere naturale. Atunci \( F_{n+m} = F_{n-1} \cdot F_m + F_n \cdot F_{m+1}\).

Demonstrație: aici.

Video

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0255 - Fibonacci 9 ușoară consola
2 #0423 - Fibonacci1 9 ușoară consola
3 #0256 - FiboVerif 9 medie consola
4 #0257 - FiboSum 9 medie consola
Editat de Candale Silviu (silviu) la data 2019-11-13