System liczbowy Fibonacciego


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Obliczanie wartości liczby zapisanej w systemie Fibonacciego
Przeliczanie liczby dziesiętnej na zapis w systemie Fibonacciego
 

Problem

Znaleźć wartość dziesiętną liczby L(fib) zapisanej w binarnym 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 →  wn-1 wn-2    ...    w2 w1 w0
cyfra →  Cn-1 Cn-2    ...    C2 C1 C0
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 = Cn-1 × wn-1 + Cn-2 × wn-2 + ... + C2  × w2 + C1 × w1 + C0 × w0

 

gdzie

 

Cii-ta cyfra zapisu liczby
wi – 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 →  35
243
34
81
33
27
32
9
31
3
30
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)

 

Obliczanie wartości liczby zapisanej w systemie Fibonacciego

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

 

f0 = 0
f1 = 1
fi = fi-2 + fi-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 →  fn fn-1    ...    f3 f2 f1
cyfra →  Cn-1 Cn-2    ...    C2 C1 C0
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 →  f9
34
f8
21
f7
13
f6
8
f5
5
f4
3
f3
2
f2
1
f1
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
cn-1cn-2...c2c1c0  -  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
f1,f2  – zmienne zapamiętujące dwie poprzednio wyznaczone liczby Fibonacciego. f1,f2 N
Lista kroków:
K01: W ← 0 ; zerujemy wartość liczby
K02: f1 ← 1 ; początkowe dwie liczby ciągu Fibonacciego
K03: f2 ← 1  
K04: Dla i = 0,1, ..., n-1 wykonuj K05...K11 ; przeglądamy kolejne cyfry zapisu liczby
K05:     Jeśli i > 1, to idź do 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 K11  
K08:     ff1 + f2 ; dla pozostałych i liczbę Fibonacciego obliczamy jako sumę dwóch
K09:     f1f2 ; poprzednich liczb
K10:     f2f ; zawsze pamiętamy dwie ostatnie liczby Fibonacciego
K11:     Jeśli ci = 1, to WW + f ; jeśli cyfra wynosi 1, to liczbę Fibonacciego dodajemy do wartości liczby
K12: Pisz W ; wypisujemy wynik
K13: Zakończ  

 

Program

Ważne:

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.

 

Lazarus Code::Blocks Free Basic
// System Fibonacciego
// Data:   22.04.2008
// (C)2012 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.
// System Fibonacciego
// Data:   22.04.2008
// (C)2012 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;
}
' System Fibonacciego
' Data:   22.04.2008
' (C)2012 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
 

 

System liczbowy Fibonacciego
(C)2012 mgr Jerzy Wałaszek

L(fib) =


...

 

Problem

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

 

 

Przeliczanie liczby dziesiętnej na zapis w systemie Fibonacciego

Problem sprowadza się do znalezienia sumy:

 

L = cn-1×fn + cn-2×fn-1 + ... + c2×f3 + c1×f2 + c0×f1

gdzie

ci – cyfry reprezentacji liczby L w systemie Fibonacciego, i = 0,1,...,n-1, ci  {0,1}
fi – 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 f93 = 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 f93 i idąc w dół do f1. Jeśli liczba fi jest większa od L, to wyprowadzamy cyfrę 0. W przeciwnym razie wyprowadzamy cyfrę 1, a od liczby L odejmujemy liczbę Fibonacciego fi i operację powtarzamy dla następnej liczby Fibonacciego. Gdy dojdziemy do f1, 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 ci 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: wykonuj 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 K07... ; w pętli generujemy kolejne cyfry zapisu
K07:     Jeśli LTLF[i], to idź do K10 ; liczby L w systemie pozycyjnym Fibonacciego
K08:     c ← 0 ; wagi brak w wartościach liczby
K09:     Idź do K13  
K10:     z ← true ; ponieważ mamy cyfrę 1, zerujemy znacznik zer wiodących
K11:     c ← 1  
K12:     LL - TLF[i] ; usuwamy wagę z wartości liczby
K13:     Jeśli (z = true) ∨ (i = 1), to wyprowadź c ; wyprowadzamy cyfrę
K14: Zakończ  

 

Program

Ważne:

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.

 

Lazarus Code::Blocks Free Basic
// System Fibonacciego
// Data:   23.04.2008
// (C)2012 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.
// System Fibonacciego
// Data:   23.04.2008
// (C)2012 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;
}
' System Fibonacciego
' Data:   23.04.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

L(10) =


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.