System Fibonacciego

Definicja

System Fibonnaciego jest to system pozycyjny, oznaczany przez literę F, do zapisu, którego używa się jedynie 0 i 1. Jeśli k-ta cyfra wynosi 0 to oznacza wartość 0. W przeciwnym wypadku k-ta cyfra reprezentuje F(k + 1), gdzie F(n) to n-ta liczba Fibonacciego. Zakłada się, że dwie pierwsze liczby Fibonacciego to 0 oraz 1 i nie są one brane podczas kodowania. Liczby zapisane przy pomocy systemu Fibonacciego nie mogą zawierać dwóch jedynek stojących koło siebie. Ponadto każda liczba w kodzie Fibonacciego ma dopisaną na końcu 1, która podczas rozkodowywania oznacza jedynie koniec liczby.

Przykład

Przykładowo liczba 3 zostanie zapisana jako . Gdyby nie zastrzeżenie, że dwie jedynki nie mogą wystąpić koło siebie to liczba trzy mogłaby być reprezentowana przez co by oznaczało, że nie każda liczba jest jednoznacznie identyfikowana. Warto pamiętać, że każdy fragment liczby postaci 011 lub 11 można zastąpić przez 100.

Podczas rozkodowywania liczby należy pamiętać, aby usunąć z zapisu ostatnią cyfrę 1. Przykładowo w celu rozkodowania początkowo należy usunąć 1 na końcu, a potem należy zsumować wszystkie cyfry pomnożone przez odpowiednią wartość kodu Fibonacciego. W tym przypadku będzie to:

Implementacja

Dziesiętny na Fibonacciego

W celu przeliczenie liczby dziesiętnej a na system Fibonacciego należy najpierw znaleźć największą liczbę Fibonacciego jaka się mieści w podanej liczbie a, a następnie szukać mniejszych wartości. W ten sposób uniknie się powtarzających się dwóch jedynek koło siebie. Bardzo ważne jest też, aby podczas zwracania wartości nie zapomnieć o dopisaniu na końcu cyfry 1.

W celu uproszczenia konwersji 0 i 1 będą przechowywane w pamięci jako tekst. Metoda ta wymaga dużo więcej pamięci niż przy zapisywaniu np. bezpośrednio bitów w pamięci. Jednak na potrzeby zadania jest to wystarczające.

1. char* konwertujDecnaFib(int a) {
2.   int wyraz_n = 1, wyraz_n_1 = 1, cyfr = 1, pom;
3.   while (wyraz_n + wyraz_n_1 <= a) {
4.     pom = wyraz_n + wyraz_n_1;
5.     wyraz_n_1 = wyraz_n;
6.     wyraz_n = pom;
7.     cyfr++;
8.   }

(1.) Funkcja konwertujDecnaFib() zwróci zapis liczby dziesiętnej a w systemie Fibonacciego. (2.) Inicjalizacja zmiennych: wyraz_n i wyraz_n_1 będą przechowywać dwa ostatnio wyliczone wyrazy ciągu Fibonacciego, cyfr - będzie zliczać ile cyfr jest potrzebnych do zapisu liczby oraz pom - zmienna pomocnicza do wyliczania kolejnych wartości ciągu Fibonacciego. (4.) Dopóki dwie ostatnie liczby są mniejsze od a to (5. - 7.) wyliczaj kolejne liczby Fibonacciego. Na zakończenie działania funkcji while zmienna wyraz_n będzie zawierać największą liczbę Fibonacciego, którą zawiera liczba a.

9.   char* liczbaF = new char[cyfr + 2];
10.   liczbaF[cyfr] = '1';
11.   liczbaF[cyfr + 1] = '\0';
12.   while (cyfr-- > 0) {
13.     if (a >= wyraz_n) {
14.       a -= wyraz_n;
15.       liczbaF[cyfr] = '1';
16.     } else {
17.       liczbaF[cyfr] = '0';
18.     }
19.     pom = wyraz_n - wyraz_n_1;
20.     wyraz_n = wyraz_n_1;
21.     wyraz_n_1 = pom;
22.   }
23.   return liczbaF;
24. }

(9.) Zaalokuj pamięć pod wynik i na dwóch ostatnich pozycjach dopisz kolejno (10.) cyfrę 1 oraz (11.) znak końca danych \0. Następnie (12.) dopóki są cyfry do zapisania: (13.) sprawdź czy aktualna liczba Fibonacciego się mieści w a. Jeśli tak to (14.) zmniejsz a i (15.) dopisz 1. (16.) W przeciwnym wypadku (17.) dopisz po prostu 0. (18. - 20.) Potem oblicz poprzednią liczbę Fibonacciego. (22.) Po zakończeniu zapisywania cyfr zwróć listę cyfr.

Fibonacciego na Dziesiętny

Zamiana z systemu Fibonacciego na dziesiętny jest zdecydowanie prostsza niż konwersja w drugą stronę. Wystarczy wyliczać kolejne wartości liczb Fibonacciego i dodać liczbę F(k + 1) jeśli na k-tej pozycji jest 1.

1. int konwertujFibnaDec(char* liczbaF) {
2.   int wyraz_n = 1, wyraz_n_1 = 1, pom;
3.   int wynik = 0;
4.   for (int i = 0; liczbaF[i + 1]; i++) {
5.     wynik += wyraz_n * (liczbaF[i] - '0');
6.     pom = wyraz_n + wyraz_n_1;
7.     wyraz_n_1 = wyraz_n;
8.     wyraz_n = pom;
9.   }
10.   return wynik;
11. }

(1.) Na podstawie tekstu złożonego z 0 i 1 zostanie zwrócona wartość dziesiętna. (2.) Zadeklaruj zmienne do wyliczania kolejnych liczb Fibonacciego oraz (3.) zmienną do której będą sumowane odpowiednie wartości liczb Fibonacciego. (4.) Dla każdej cyfry, prócz ostatniej jedynki, wykonuj: (5.) dodaj do wyniku i + 1 liczbę Fibonacciego pomnożoną przez i-tą cyfrę. (6. - 8.) Oblicz kolejny wyraz ciągu Fibonacciego. (10.) Na koniec zwróć wartość zmiennej wynik.

Testowanie funkcji

W celu przetestowania konwersji można skorzystać z poniższej funkcji main(). Po uruchomieniu program będzie oczekiwał wprowadzenia liczby dziesiętnej, a następnie wypisze jej wartość skonwertowaną na system Fibonacciego, a następnie na podstawie zapisu Fibonacciego obliczy wprowadzoną na początku liczbę.

1. int main () {
2.   int a;
3.   cin >> a;
4.   char* liczbaF = konwertujDecnaFib(a);
5.   cout << liczbaF << "F" << endl;
6.   cout << konwertujFibnaDec(liczbaF) << endl;
7.   delete[] liczbaF;
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który wczyta liczbę n, a następnie n linijek zawierających maksymalnie po 10 znaków. Każda linijka będzie zawierać liczbę w systemie dziesiętnym lub w systemie Fibonacciego. Ten drugi będzie miał na końcu linijki literę F. Program powinien wypisać na ekran sumę wszystkich podanych cyfr w systemie dziesiętnym oraz Fibonacciego.

Przykładowo dla danych:

1. 5
2. 142
3. 00100011F
4. 1011
5. 11F
6. 100101011F

Prawidłowy wynik to:

1. 1231 = 0010100000010011F

• Kod źródłowy Zadanie 1