Algorytmy i Struktury Danych - System liczbowy Fibonacciego

Liczbowy system pozycyjny pozwala zapisać dowolnie dużą liczbę przy pomocy skończonej ilości cyfr. Wspólną cechą wszystkich systemów pozycyjnych jest sposób obliczania wartości liczby. Cyfry stoją na pozycjach, które posiadają swoje numery oraz wagi:

waga pozycji →	w_n-1	w_n-2	…	w₂	w₁	w₀
cyfra →	C_n-1	C_n-2	…	C₂	C₁	C₀
numer pozycji →	n-1	n-2	…	2	1	0

Wartość liczby obliczamy zawsze jako sumę iloczynów cyfr przez wagi pozycji, na których te cyfry stoją. Zatem dla powyższego przypadku wartość liczby pozycyjnej obliczamy ze wzoru:

W = C_n-1×w_n-1+C_n-2×w_n-2+…+C₂×w₂+C₁×w₁+C₀×w₀

gdzie

C_i – i-ta cyfra zapisu liczbyw_i – waga i-tej pozycji

Przykład:

W systemie trójkowym wagi pozycji są kolejnymi potęgami podstawy tego systemu, czyli liczby 3. Cyfry należą do zbioru {0, 1, 2}. Mając zatem liczbę trójkową 221012 obliczamy jej wartość następująco:

waga pozycji →	3^5 243	3^4 81	3^3 27	3^2 9	3^1 3	3^0 1
cyfra →	2	2	1	0	1	2	= 2×243+2×81+1×27+0×9+1×3+2×1
numer pozycji →	5	4	3	2	1	0

Po wyliczeniu iloczynów cyfr przez wagi ich pozycji i zsumowaniu tych iloczynów otrzymujemy wynik:

221012₍₃₎ = 680₍₁₀₎

W systemie liczbowym Fibonacciego wagi pozycji są kolejnymi liczbami ciągu Fibonacciego, który definiujemy następująco:

f₀ = 0
f₁ = 1
f_i = f_i-2+f_i-1, dla i > 1.

Czyli, począwszy od elementu o numerze 2, kolejne wyrazy ciągu Fibonacciego są sumą dwóch wyrazów poprzedzających. Oto kilka początkowych liczb Fibonacciego:

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

Zapis liczby w systemie Fibonacciego wygląda następująco:

waga pozycji →	f_n	f_n-1	…	f₃	f₂	f₁
cyfra →	C_n-1	C_n-2	…	C₂	C₁	C₀
numer pozycji →	n-1	n-2	…	2	1	0

Cyfry w systemie liczbowym Fibonacciego należą do zbioru {0, 1}. Ponieważ zbiór taki możemy odwzorować za pomocą bitów – cyfr binarnych, system liczbowy Fibonacciego jest odmianą systemu binarnego. Mając daną liczbę 100101101_(fib) w systemie Fibonacciego, jej wartość obliczamy następująco:

waga pozycji →	f₉34	f₈21	f₇13	f₆8	f₅5	f₄3	f₃2	f_2 1	f₁ 1
cyfra →	1	0	0	1	0	1	1	0	1	= 34+8+3+2+1 = 48
numer pozycji →	8	7	6	5	4	3	2	1	0

Zwróć uwagę, iż w systemie liczbowym Fibonacciego liczby można zapisywać na kilka równoważnych sposobów:

7₍₁₀₎ = 10100_(fib) = 10011_(fib) = 1111_(fib)

Umówmy się, iż standardowym zapisem będzie ten, w którym liczba cyfr 1 jest najmniejsza.

Obliczanie wartości liczby Fibonacciego rozpoczniemy od wczytania jej cyfr do tablicy znakowej. Następnie idąc od końca zapisu do początku będziemy tworzyć kolejne liczby Fibonacciego algorytmem dynamicznym i dodawać je do wartości liczby, jeśli odpowiednia cyfra zapisu będzie ustawiona na 1.

Algorytm obliczania wartości liczby zapisanej w systemie Fibonacciego

Wejście:

c_n-1c_n-2…c₂c₁c₀ : kolejne cyfry zapisu liczby w systemie Fibonacciego.

Wyjście:

W : wartość dziesiętna odczytanej liczby w systemie Fibonacciego.

Elementy pomocnicze:

i : indeksuje cyfry zapisu liczby w systemie Fibonacciego, i ∈ N.
f : obliczona, (i+1)-sza liczba Fibonacciego, f ∈ N.
f₁, f₂ : zmienne zapamiętujące dwie poprzednio wyznaczone liczby Fibonacciego. f₁, f₂ ∈ N.

Lista kroków:

K01: W ← 0  ; zerujemy wartość liczby
K02: f₁ ← 1 ; początkowe dwie liczby ciągu Fibonacciego
K03: f₂ ← 1
K04: Dla i = 0, 1, …, n-1: ; przeglądamy kolejne cyfry zapisu liczby
     wykonuj kroki K05…K11
K05:   Jeśli i > 1, ; najpierw wyznaczamy (i+1)-szą liczbę Fibonacciego
       to idź do kroku K08
K06:   f ← 1 ; dla i = 0 i i = 1 liczba Fibonacciego ma wartość 1
K07:   Idź do kroku K11
K08:   f ← f₁+f₂; dla pozostałych i liczbę Fibonacciego
                 ; obliczamy jako sumę dwóch
K09:   f₁ ← f₂; poprzednich liczb
K10:   f₂ ← f  ; zawsze pamiętamy dwie ostatnie liczby Fibonacciego
K11:   Jeśli c_i = 1, ; jeśli cyfra wynosi 1, to liczbę Fibonacciego
       to W ← W+f  ; dodajemy do wartości liczby
K12: Pisz W ; wypisujemy wynik
K13: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

W pierwszym wierszu program odczytuje cyfry zapisu liczby w systemie Fibonacciego. W następnym wierszu wypisywana jest wartość dziesiętna liczby. Algorytm obliczeniowy reaguje tylko na cyfry 1. Jeśli napotka inny znak, to zostanie on potraktowany jak cyfra 0.

Pascal

// System Fibonacciego
// Data:   22.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var c : string;
    w, f, f1, f2 : qword;
    i, n : integer;

begin
  readln(c);
  n  := length(c);
  w  := 0;
  f1 := 1;
  f2 := 1;
  for i := n downto 1 do
  begin
    if i >= n-1 then
      f := 1
    else
    begin
      f  := f1+f2;
      f1 := f2;
      f2 := f;
    end;
    if c[i] = '1' then inc(w, f);
  end;
  writeln(w);
end.

C++

// System Fibonacciego
// Data:   22.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string c;
  unsigned long long w, f, f1, f2;
  int i, n;

  cin >> c;
  n  = c.length()-1;
  w  = 0;
  f1 = f2 = 1;
  for(i = n; i >= 0; i--)
  {
    if(i >= n-1) f = 1;
    else
    {
      f  = f1+f2;
      f1 = f2;
      f2 = f;
    }
    if(c[i] == '1') w += f;
  }
  cout << w << endl;
  return 0;
}

Basic

' System Fibonacciego
' Data:   22.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim c As String
Dim As Ulongint w, f, f1, f2
Dim As Integer i, n

Input c
n  = Len(c)
w  = 0
f1 = 1: f2 = 1
For i = n To 1 Step -1
  If i >= n-1 Then
    f = 1
  Else
    f  = f1+f2
    f1 = f2
    f2 = f
  End If
  If Mid(c, i, 1) = "1" Then w += f
Next
Print w
End

Python (dodatek)

# System Fibonacciego
# Data:   18.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

c = input()
w, f1, f2, f = 0, 0, 1, 0
for d in reversed(c):
    if not f:
        f = 1
    else:
        f  = f2+f1
        f1 = f2
        f2 = f
    if d == "1": w += f
print(w)

Wynik:

1111
7

Na początek: podrozdziału strony

Problem sprowadza się do znalezienia sumy:

L = c_n-1×f_n+c_n-2×f_n-1+…+c₂×f₃+c₁×f₂+c₀×f₁

gdzie

c_i – cyfry reprezentacji liczby L w systemie Fibonacciego, i = 0, 1, …, n-1, c_i ∈ {0, 1}
f_i – liczby ciągu Fibonacciego

Zadanie rozwiążemy następująco:

Zbudujemy tablicę TLF, której elementy będą odpowiadały kolejnym liczbom ciągu Fibonacciego. Dla danych 64 bitowych największą liczbą Fibonacciego jest:

f₉ = 12200160415121876738

Jeśli kodujemy wiele liczb w systemie Fibonacciego, to tablicę TLF tworzymy tylko jeden raz, a później wykorzystujemy ją przy każdej liczbie. Algorytm jest następujący:

Liczbę L przyrównujemy do kolejnych liczb Fibonacciego w tablicy TLF poczynając od liczby f₉₃ i idąc w dół do f₁. Jeśli liczba f_i jest większa od L, to wyprowadzamy cyfrę 0. W przeciwnym razie wyprowadzamy cyfrę 1, a od liczby L odejmujemy liczbę Fibonacciego f_i i operację powtarzamy dla następnej liczby Fibonacciego. Gdy dojdziemy do f₁, otrzymamy wszystkie kolejne cyfry liczby L w systemie Fibonacciego.

Algorytm możemy wyposażyć w usuwanie zer wiodących. W tym celu wystarczy dodać zmienną logiczną, którą ustawiamy na false. Jeśli w trakcie konwersji dostaniemy cyfrę 1, to zmienną decyzyjną ustawiamy na true. Wyprowadzanie cyfr możemy uzależnić od stanu tej zmiennej decyzyjnej: false – cyfry nie wyprowadzamy, true – cyfrę wyprowadzamy. Ostatnia cyfra musi być zawsze wyprowadzona bezwarunkowo – np. gdy L = 0, to konwersja powinna również dać wynik 0.

Algorytm przeliczania liczby dziesiętnej na zapis w systemie Fibonacciego

Wejście:

L : przeliczana nieujemna liczba całkowita.

Wyjście:

Ciąg cyfr binarnych c_i reprezentujących zapis liczby L w systemie pozycyjnym Fibonacciego.

Elementy pomocnicze:

TLF : tablica 93 kolejnych liczb Fibonacciego. Elementy są numerowane od 1 do 93.
c : cyfra binarna, c ∈ {0, 1}.
z : znacznik zer wiodących, z ∈ {false, true}.
i : indeksuje liczby w TLF, i ∈ N.

Lista kroków:

K01: TLF[1] ← 1 ; w tablicy ustawiamy 2 pierwsze liczby Fibonacciego
K02: TLF[2] ← 1
K03: Dla i = 3, 4, …, 93: ; tablicę wypełniamy kolejnymi
     wykonuj krok K04  ; liczbami Fibonacciego
K04:   TLF[i] ← TLF[i-2]+TLF[i-1]
K05: z ← false ; ustawiamy znacznik wyprowadzania zer wiodących
K06: Dla i = 93, 92, …, 1: ; w pętli generujemy kolejne cyfry zapisu
     wykonuj kroki K07…K13
K07:   Jeśli L ≥ TLF[i],   ; liczby L w systemie
       to idź do kroku K10 ; pozycyjnym Fibonacciego
K08:   c ← 0 ; wagi brak w wartościach liczby
K09:   Idź do kroku K13
K10:   z ← true ; ponieważ mamy cyfrę 1, zerujemy znacznik zer wiodących
K11:   c ← 1
K12:   L ← L-TLF[i] ; usuwamy wagę z wartości liczby
K13:   Jeśli (z = true) ∨ (i = 1), ; wyprowadzamy cyfrę
       to pisz c
K14: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

W pierwszym wierszu program odczytuje liczbę L. W następnym wierszu wypisywany jest zapis tej liczby w systemie pozycyjnym Fibonacciego.

Pascal

// System Fibonacciego
// Data:   23.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var
  TLF : array [1..93] of qword;
  L   : qword;
  i, c : integer;
  z   : boolean;

begin
  TLF[1] := 1;
  TLF[2] := 1;
  for i := 3 to 93 do
    TLF[i] := TLF[i-2]+TLF[i-1];
  readln(L);
  z := false;
  for i := 93 downto 1 do
  begin
    if L >= TLF[i] then
    begin
      c := 1; z := true;
      dec(L, TLF[i]);
    end
    else c := 0;
    if z or (i = 1) then
      write(c);
  end;
  writeln;
end.

C++

// System Fibonacciego
// Data:   23.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned long long TLF[94], L;
  int i, c;
  bool z;

  TLF[1] = TLF[2]+1;
  for(i = 3; i <= 93; i++)
    TLF[i] = TLF[i-2]+TLF[i-1];
  cin >> L;
  z = false;
  for(i = 93; i >= 1; i--)
  {
    if(L >= TLF[i])
    {
      c = 1; z = true;
      L -= TLF[i];
    }
    else c = 0;
    if(z || (i == 1)) cout << c;
  }
  cout << endl << endl;
  return 0;}

Basic

' System Fibonacciego
' Data:   23.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As Ulongint TLF(93), L
Dim As Integer i, c, z

TLF(1) = 1
TLF(2) = 1
For i = 3 To 93
  TLF (i) = TLF(i-2)+TLF(i-1)
Next
Input L
z = 0
For i = 93 To 1 Step -1
  If L >= TLF(i) Then
    c = 1: z = 1
    L -= TLF(i)
  Else
    c = 0
  End If
  if(z = 1) Or (i = 1) Then
    Print Using "#";c;
  End If
Next
Print
End

Python (dodatek)

# System Fibonacciego
# Data:   19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

tlf = [0, 1]
for i in range(2, 94):
    tlf.append(tlf[i-2]+tlf[i-1])
n = int(input())
z = False
for i in range(93, 0, -1):
    if n >= tlf[i]:
        c = 1
        z = True
        n -= tlf[i]
    else:
        c = 0
    if z or (i == 1):
        print("%1d" % c, end="")
print()

Wynik:

1234567890
100000101010010100000001001001000101010001010

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

System liczbowy Fibonacciego

Problem

Obliczanie wartości liczby zapisanej w systemie Fibonacciego

Przykład:

Algorytm obliczania wartości liczby zapisanej w systemie Fibonacciego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Problem

Przeliczanie liczby dziesiętnej na zapis w systemie Fibonacciego

Algorytm przeliczania liczby dziesiętnej na zapis w systemie Fibonacciego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy