System Fibonacciego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

System Fibonacciego to binarny, pozycyjny system liczbowy, w którym poszczególnym pozycjom odpowiadają kolejne liczby Fibonacciego.

W zapisie liczby nie używa się pierwszych dwóch liczb z ciągu Fibonacciego (czyli zera i pierwszej z dwóch występujących w nim jedynek). Zaczynającemu się od 1 ciągowi cyfr 0 i 1 (tylko takich się używa) anan-1...a2 odpowiada liczba an⋅Fn+an-1⋅Fn-1 + ... + a2⋅F2.

Na przykład liczba zapisana w systemie Fibonacciego jako 1000F oznacza piątą liczbę w ciągu Fibonacciego czyli 5,

  • 1000101F = F8+F4+F2 = 21+3+1 = 25
  • 10010010F = F9+F6+F3 = 34+8+2 = 44

Taki sposób zapisu liczb nie byłby jednoznaczny (np. 100F=11F), więc dodaje się wymaganie, by kolejne dwie liczby nie były jednocześnie jedynkami (dwie jedynki zastępujemy jedną na wcześniejszym miejscu). W ten sposób otrzymujemy jednoznaczny zapis każdej liczby naturalnej.

Modyfikacje[edytuj | edytuj kod]

Kompresja[edytuj | edytuj kod]

W systemie Fibonacciego jedynkę zawsze poprzedza zero (z wyjątkiem pierwszego wyrazu) możemy zatem dopisać na początku zero i zastąpić pary cyfr 01 przez 1. Skracamy w ten sposób zapis liczby o tyle cyfr ile było jedynek poza pierwszą w standardowym kodzie.

Kod Fibonacciego[edytuj | edytuj kod]

W systemie Fibonacciego nigdy dwie jedynki nie występują na kolejnych miejscach, możemy zatem kolejne dwie jedynki uznać za dodatkowy symbol końca liczby. Daje nam to sposób zapisu ciągu liczb. W kodzie Fibonacciego liczby zapisujemy w porządku odwrotnym niż w systemie Fibonacciego i każdą z liczb kończymy jedynką. Przy odczytywaniu drugą z jedynek w parze traktujemy jako znak końca liczby.

Przykład[edytuj | edytuj kod]

  • 1000F = 5
  • 1000101F = 25
  • 10010010F = 44

"Odwracamy liczby" i otrzymujemy:

  • 0001
  • 1010001
  • 01001001

Dopisujemy jedynki:

  • 00011
  • 10100011
  • 010010011

Łączymy i otrzymujemy binarny ciąg 0001110100011010010011 kodujący ciąg liczb 5,25,44