Strona główna » Algorytmy » Teoria Liczb » Liczby Fibbinary
 

Liczby Fibbinary

https://mattomatti.com/a0089

Definicja

Liczby Fibbinary to takie liczby naturalne, które w zapisie binarnym nie mają dwóch cyfr 1 zapisanych obok siebie.

Przykład

Liczbą Fibbinary jest przykładowo liczba 10, ponieważ 10 = 10102. Jak można zauważyć, że w zapisie nie ma dwóch cyfr 1 obok siebie. Jednak już dla 11 = 10112 taka sytuacja ma miejsce, więc 11 nie należy do tego zbioru liczb.

Ciąg Liczb

Ustawiając liczby Fibbinary w ciąg otrzymujemy: 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, ...

Implementacja

Zadanie

Napisz funkcję, która sprawdzi czy podana liczba całkowita a jest liczbą Fibbinary. Przetestuj działanie napisanej funkcji.

Poszukiwanie Par Cyfr

Pierwszy sposób rozwiązania tego zadania polega na sprawdzeniu każdej pary bitów przekazanej liczby w poszukiwaniu wartości 11. Tego typu rozwiązanie jest zależne od ilości bitów z których składa się liczba. Oto przykładowa implementacja funkcji czyFibbinary().

C++
C#
  1. bool czyFibbinary(int a) {
  2.   for (int i = 0; i < sizeof(a) * 8 - 1; i++) {
  3.     if (((a >> i) & 3) == 3)
  4.       return false;
  5.   }
  6.   return true;
  7. }

(2.) Dla każdej pary bitów: (3.) pobierz dwa kolejne i sprawdź czy obie wartości są ustawione (112 = 3).

Szybkie Sprawdzenie

Wbrew pozorom sprawdzenie każdej pary bitów jest procesem czasochłonnym i istnieje bardziej efektywne rozwiązanie. Wiadomo, że między każdą parę cyfr 1 w zapisie musi istnieć wartość 0. Oznacza to, że jeśli wszystkie bity zostałyby przesunięte o 1 w prawo to gwarantowane jest, że w miejsce 1 pojawi się 0. W przypadku, gdy nie jest to liczba Fibbinary to na któreś pozycji zamiast 0 wciąż będzie znajdować się wartość 1. Sprawdzenie czy dwie liczby mają wartość na tej samej pozycji można wykonać wywołując operacje binarną AND na obu wartościach. Cyfry 1 zostaną tylko tam gdzie występują w jednej i drugiej liczbie na tej samej pozycji i wtedy wynik jest niezerowy. (Wszystkie pary 0 i 1 oraz 0 i 0 przyjmą wartość 0).

Rozpatrzmy przykładowo przykład wartości 10 zapisanej na 8 bitach:

1000001010
10 >> 100000101
AND00000000

Jak można zauważyć wynik operacji AND jest 0, więc jest to liczba Fibbinary. Z kolei dla liczby 11 zostaną otrzymane następujące wartości:

1100001011
11 >> 100000101
AND00000001

Tym razem wynik jest niezerowy. Oznacza to, że nie jest to liczba Fibbinary. Tego typu rozwiązanie jest niezależne od długości liczby, ponieważ przyjmuje się, że operacje binarne są operacjami atomowymi. Oto przykładowa implementacja:

C++
C#
  1. bool czyFibbinary(int a) {
  2.   return (a & (a >> 1)) == 0;
  3. }

Testowanie funkcji

Poniższy kod wypisze pierwsze n liczb Fibbinary, gdzie n to liczba wczytana od użytkownika.

C++
C#
  1. int main () {
  2.   int n;
  3.   cout << "Ile liczb Fibbinary wypisac?\n n = ";
  4.   cin >> n;
  5.   cout << "Liczby Fibbinary:" << endl;
  6.   for(int i = 0; n > 0; i++) {
  7.     if (czyFibbinary(i)) {
  8.       cout << i << " ";
  9.       n--;
  10.     }
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Przyjmuje się, że każdą liczbę Fibbinary można zapisać jako sumę dwóch innych liczb Fibbinary. Napisz funkcję podajeSume(), która dla podanej liczby a znajdzie jakich dwóch liczb Fibbinary jest sumą liczba a. Jeśli jest więcej niż jedno unikalne rozwiązanie też je wypisz. Zakładamy, że dodawane liczby nie muszą być różne. Przetestuj działanie napisanej funkcji.

Przykładowo dla liczby 18 będzie to:

  1. 18 = 0 + 18 = 1 + 17 = 2 + 16 = 8 + 10 = 9 + 9