Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

System liczbowy Fibonacciego

SPIS TREŚCI
Podrozdziały

Problem

Należy obliczyć wartość dziesiętną liczby L ( fib ) zapisanej w binarnym systemie Fibonacciego.

Obliczanie wartości liczby zapisanej w systemie 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 2 w 1 w 0
cyfra →  C n-1 C n-2    ...    C 2 C 1 C 0
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 2  × w 2 + C 1 × w 1 + C 0 × w 0

gdzie

C i  – i-ta cyfra zapisu liczby
w 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 ( 3 ) = 680 ( 10 )

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

f 0 = 0
f 1 = 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 ...

I dalej zapis liczby w systemie Fibonacciego wygląda następująco:

waga pozycji →  f n f n-1    ...    f 3 f 2 f 1
cyfra →  C n-1 C n-2    ...    C 2 C 1 C 0
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 9
34
f 8
21
f 7
13
f 6
8
f 5
5
f 4
3
f 3
2
f 2
1
f 1
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 ( 10 ) = 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 2c 1c 0  -  kolejne cyfry zapisu liczby w systemie Fibonacciego.

Wyjście:

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

Zmienne pomocnicze:

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

Lista kroków:

K01: W  ← 0 zerujemy wartość liczby
K02: f 1 ← 1 początkowe dwie liczby ciągu Fibonacciego
K03: f 2 ← 1  
K04: Dla i  = 0, 1, ..., n - 1:
wykonuj kroki K05...K11
przeglądamy kolejne cyfry zapisu liczby
K05:     Jeśli i  > 1,
    to idź do kroku K08
najpierw wyznaczamy ( i+1 )-szą liczbę Fibonacciego
K06:     f  ← 1 dla i = 0 i i = 1 liczba Fibonacciego ma wartość 1
K07:     Idź do kroku K11  
K08:     f  ← f 1 + f 2 dla pozostałych i liczbę Fibonacciego obliczamy jako sumę dwóch
K09:     f 1f 2 poprzednich liczb
K10:     f 2f zawsze pamiętamy dwie ostatnie liczby Fibonacciego
K11:     Jeśli c i  = 1,
    to W  ← W  + f
jeśli cyfra wynosi 1, to liczbę Fibonacciego 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
Wynik:
1111
7
Na początek:  podrozdziału   strony 

Problem

Daną, dodatnią liczbę dziesiętną L  należy zapisać w binarnym systemie liczbowym Fibonacciego.

Przeliczanie liczby dziesiętnej na zapis w systemie Fibonacciego

Problem sprowadza się do znalezienia sumy:

L  = c n - 1 × f n  + c n - 2 × f n - 1 + ... + c 2 × f 3 + c 1 × f 2 + c 0 × f 1

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 93 = 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 93 i idąc w dół do f 1. 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 1, 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.

Zmienne 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, iN.

Lista kroków:

K01: TLF [ 1 ] ← 1 w tablicy ustawiamy 2 pierwsze liczby Fibonacciego
K02: TLF [ 2 ] ← 1  
K03: Dla i  = 3, 4, ..., 93:
wykonuj krok K04
tablicę wypełniamy kolejnymi 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:
wykonuj kroki K07...K13
w pętli generujemy kolejne cyfry zapisu
K07:     Jeśli L  ≥ TLF [ i  ],
    to idź do kroku K10
liczby L w systemie 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 ),
    to pisz c
wyprowadzamy cyfrę
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
Wynik:
1234567890
100000101010010100000001001001000101010001010
Przeliczanie liczby dziesiętnej na zapis w systemie Fibonacciego
(C)2020 mgr Jerzy Wałaszek

L ( 10 ) =


...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.