Sistemul de numere Fibonacci

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 octombrie 2017; verificările necesită 14 modificări .

Sistem de numere Fibonacci - un sistem de numere mixt pentru numere întregi bazat pe numerele Fibonacci F 2 =1, F 3 =2, F 4 =3, F 5 =5, F 6 =8 etc.

Număr	Înregistrarea în FSS	Codul Fibonacci

0	0 …… 0
F 2 \u003d 1	unu	1 1
F 3 \u003d 2	zece	01 1
F4 = 3	100	001 1
patru	101	101 1
F5 = 5	1000	0001 1
6	1001	1001 1
7	1010	0101 1
F 6 \u003d 8	10000	00001 1
…
F n - 1	101010 …	… 010101 1
F n	10 …… 00	00 …… 01 1
F n + 1	10 …… 01	10 …… 01 1

Reprezentarea numerelor naturale

Orice număr întreg nenegativ poate fi reprezentat în mod unic printr-o succesiune de biți …ε k …ε 4 ε 3 ε 2 ( ) astfel încât și secvența {ε k } conține doar un număr finit de 1 și nu are perechi de 1 învecinați : . Cu excepția ultimei proprietăți, această reprezentare este similară cu sistemul de numere binar . $A$ $\varepsilon _{k}\in \{0,1\}$ $a=\sum _{k}\varepsilon _{k}F_{k}$ $\forall k\geq 2\colon (\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)$

Motivație

Se bazează pe teorema Zeckendorf [1] — orice număr întreg nenegativ este reprezentabil în mod unic ca suma unui set de numere Fibonacci distincte în perechi cu indici mai mari decât unu, care nu conține perechi de numere Fibonacci învecinate.

Dovada existenței este ușor de făcut prin inducție . Orice număr întreg va cădea în decalajul dintre două numere Fibonacci adiacente, adică pentru unele , inegalitatea este adevărată: . Astfel, , unde , astfel încât extinderea numărului să nu mai conțină termenul . $a\geq 1$ $n\geq 2$ $F_{n}\leq a<F_{{n+1}}$ $a=F_{n}+a'$ $a'=a-F_{n}\ <\ F_{{n-1}}$ $A'$ $F_{{n-1}}$

Utilizare

Yupana

Se crede că unele soiuri de yupana ( abacus Inca ) au folosit sistemul numeric Fibonacci pentru a minimiza numărul de boabe necesare calculelor [2] .

În teoria informației

Pe baza sistemului de numere Fibonacci, este construit codul Fibonacci (codificare) - un cod universal pentru numere naturale (1, 2, 3 ...), folosind secvențe de biți . Deoarece combinația 11 este interzisă în sistemul numeric Fibonacci, aceasta poate fi folosită ca marcator de sfârșit de înregistrare.

Pentru a compila codul Fibonacci prin scrierea unui număr în sistemul numeric Fibonacci, ar trebui să rescrieți numerele în ordine inversă (astfel încât cea mai mare unitate să fie ultimul caracter) și să adăugați din nou 1 la sfârșit (vezi tabelul). Adică, secvența de cod arată astfel:

ε 2 ε 3 …ε n 1 ,

unde n este numărul cifrei celei mai semnificative cu unu.

Aritmetică

Adăugarea numerelor în sistemele de numere poziționale se realizează folosind carry , care vă permite să eliminați consecințele depășirii biților. De exemplu, în binar: 01 + 01 = 0 2 = 10 .

În sistemul numeric Fibonacci, situația este mai complicată:

În primul rând, greutatea celor mai semnificativi biți nu este un multiplu al greutății bitului de la care este necesară transportul. Când adăugați două unități într-un bit, este necesar un transfer nu numai la stânga, ci și la dreapta: 0 2 00 \ u003d 1001 . Când transferați la biții lipsă ε 1 și ε 0 , amintiți-vă că F 1 =1=F 2 și F 0 =0.
În al doilea rând, este necesar să scăpați de unitățile învecinate: 0 11 = 100 . Regula pentru extinderea doi este o consecință a acestei egalități: 0 2 00 = 0100 + 00 11 = 0 11 1 = 1001 .

Generalizare la numere reale

Număr	Reprezentarea prin grade $\varphi$
unu	unu
2	10.01
3	100.01
patru	101.01
5	1000,1001
6	1010,0001
7	10000,0001
opt	10001,0001
9	10010.0101
zece	10100.0101
unsprezece	10101.0101
12	100000,101001
13	100010.001001
paisprezece	100100.001001

Un dispozitiv similar are un sistem numeric pozițional cu o bază irațională egală cu raportul de aur . $\varphi =(1+{\sqrt {5}})/2$

Orice număr real x din intervalul [0,1] poate fi extins într- o serie în termeni de puteri negative ale raportului de aur:

x=\sum _{{k=-1}}^{{-\infty }}\varepsilon _{k}\varphi ^{k},\qquad \varepsilon _{k}\in \{0,1\ }

unde are aceeași proprietate a absenței celor vecine. Coeficienții se găsesc comparând succesiv x cu raportul de aur al segmentului [0,1], scăzând (dacă ) și înmulțind cu . Din aceasta este ușor de observat că orice număr real nenegativ poate fi descompus: $\left\{\varepsilon _{k}\right\}$ $\varphi ^{{-1}}$ $\varphi ^{{-1}}$ $\varepsilon _{k}=1$ $\varphi$

a=\sum _{{k=N-1}}^{{-\infty }}\varepsilon _{k}\varphi ^{k}\,,

unde N este astfel încât . Desigur, ar trebui să presupunem că pentru toți . $a<\varphi ^{N}$ $\varepsilon _{k}=0$ $k \geqslant N$

Aceste formule sunt complet similare cu formulele pentru sistemele poziționale convenționale cu baze întregi. Rezultă că orice număr întreg nenegativ (și, mai general, orice element nenegativ al inelului ) are o reprezentare doar cu un număr finit de unități, adică ca o sumă finită a puterilor nerepetabile ale puterii de aur. raport. [3] ${{\mathbb Z}}+\varphi {{\mathbb Z}}$

Analogia dintre numerele Fibonacci și puterile secțiunii de aur se bazează pe aceeași formă de identități:

F_{k}=F_{{k-1}}+F_{{k-2}}

\varphi ^{k}=\varphi ^{{k-1}}+\varphi ^{{k-2}}

permiţând eliminarea unităţilor învecinate. Nu există o legătură directă între reprezentarea numerelor naturale în sistemul secțiunii de aur și în sistemul Fibonacci.

Regulile de adăugare sunt similare cu cele prezentate mai sus , cu modificarea că transferul către cifrele inferioare se extinde fără restricții. În acest sistem de numere se poate efectua și înmulțirea.

Înmulțirea Fibonacci

Pentru numere întregi și se poate defini „înmulțirea” [4] $a=\sum _{k}\varepsilon _{k}F_{k}\$ $b=\sum _{l}\zeta _{l}F_{l}\$

a\circ b=\sum _{{k,l}}\varepsilon _{k}\zeta _{l}F_{{k+l}},

care este analog cu înmulțirea numerelor în sistemul binar .

Desigur, această operație nu este o înmulțire reală a numerelor și este exprimată prin formula: [5]

a\circ b=3ab-a\lfloor (b+1)\varphi ^{{-2}}\rfloor -b\lfloor (a+1)\varphi ^{{-2}}\rfloor ,

unde este partea întreagă a , este raportul de aur . $\lfloor\cdot\rfloor$ $\varphi ={\frac {1+{\sqrt {5}}}{2}}$

Această operație are asociativitate , care a fost observată pentru prima dată de Donald Knuth [6] . O altă „lucrare” care diferă doar printr-o deplasare cu două cifre nu mai este asociativă. $\sum _{{k,l}}\varepsilon _{k}\zeta _{l}F_{{k+l-2}},$

Note

↑ Eduard Zeckendorf (link inaccesibil) . Consultat la 27 ianuarie 2010. Arhivat din original la 6 mai 2017. (nedefinit)
↑ Antonio Aimi, Nicolino De Pasquale. Calculatoare andine . Preluat: 12 decembrie 2009. (nedefinit)
↑ Sistem numeric bazat pe raportul de aur
↑ Secvența OEIS A101330 , teorema lui Zeckendorf
↑ Note despre cercul Fibonacci și produsele arroba
↑ D.E. Knuth. Înmulțirea Fibonacci (nedefinită) // Litere de matematică aplicată. - 1988. - T. 1 , Nr. 1 . - S. 57-60 . - doi : 10.1016/0893-9659(88)90176-0 .

Literatură

Vorobyov N. N. numerele Fibonacci . - Nauka, 1978. - T. 39. - ( Prelegeri populare de matematică ).

Sistem de numere Fibonacci, implementare C++ . - 2014. Arhivat la 16 octombrie 2014.

Stakhov A., Sluchenkova A., Shcherbakov I. Codul lui Da Vinci și seria Fibonacci. SPB. Editura: Piter, 2006. 320 p. ISBN: 5-469-01369-3
Stahov A.P. Teoria măsurării algoritmice: o nouă abordare a teoriei sistemelor numerice poziționale și a aritmeticii computerizate // Jurnalul „Mașini și sisteme de control”, 1994, nr. 4-5.
Stahov A.P. Fibonacci Computers and New Coding Theory: History, Theory, Prospects // Jurnalul electronic al Universității de Inginerie Radio Taganrog „Perspective Information Technologies and Intelligent Systems”, Nr. 2 (18), 2004// http://pitis.tsure.ru /files18/p5 .pdf .