Strona główna » Algorytmy » Teoria Liczb » Liczby Wstrętne i Diabelskie
 

Liczby Wstrętne i Diabelskie

https://mattomatti.com/a93

Definicja

Wstrętne liczby to takie liczby nieujemne, które w zapisie binarnym mają nieparzystą liczbę cyfr 1. W przypadku, gdy liczba nie jest wstrętna to mówi się o liczbach Diabelskich (tj. w zapisie binarnym mają parzystą liczbę cyfr 1).

Przykłady

Kolejne liczby Wstrętne to: 1, 2, 4, 7, 8, 11, 13, 14, 16, ...

Z kolei kolejne liczby Diabelskie to: 0, 3, 5, 6, 9, 10, 12, 15, ...

Implementacja

Założenia

W artykule zostaną przedstawione dwie funkcje do wyznaczania ile w zapisie binarnym mają cyfr 1. Będzie ona nazwana policzBity() i będzie przyjmowała jeden argument a - liczbę, której w zapisie binarnym cyfr 1 mają zostać policzone. W celu wypisania jakiego rodzaju jest liczba wystarczy wywołać funkcję podajRodzaj().

Metoda I

Pierwsaz metoda sprawdzania ile cyfr 1 znajduje się w zapisie binarnym liczby a polega na przeprowadzeniu procesu przeliczania liczby dziesiętnej na binarny. W trakcie zamiany należy zliczyć wszystkie momenty kiedy zaistniała potrzeba zmniejszenia kopii liczby a. Przykładowa implementacja wygląda następująco:

  1. int policzBity(int a) {
  2.   int pot = 1;
  3.   while (pot < a)
  4.     pot *= 2;
  5.   int licznik = 0;
  6.   do {
  7.     if (a >= pot) {
  8.       a -= pot;
  9.       licznik++;
  10.     }
  11.     pot /= 2;
  12.   } while (pot > 0);
  13.   return licznik;
  14. }

(2. - 4.) Znajdź największą potęgę liczby 2 w liczbie a. Następnie (5.) przypisz licznikowi wartość 0 i (6. - 12.) przeprowadź proces przeliczania. W trakcie przeliczania pomijamy zapamiętywanie kolejności znalezionych 0 i 1, a jedynie (9.) należy zliczyć ilość znalezionych cyfr 1. (13.) Na koniec wystarczy zwrócić wartość zmiennej licznik.

Metoda II

Metoda I działa poprawnie dla dowolnej liczby. Warto jednak zwrócić uwagę, że dane w komputerze są przechowywane nie w systemie dziesiętnym, a systemie binarnym. Oznacza to, że dochodzi do zbędnego przeliczania podanej wartości w obydwie strony. Zdecydowanie lepszym rozwiązaniem jest sprawdzać kolejne bity podanej zmiennej a.

  1. int policzBity(int a) {
  2.   int licznik = 0;
  3.   while (a > 0) {
  4.     if ((a & 1) == 1)
  5.       licznik++;
  6.     a >>= 1;
  7.   }
  8.   return licznik;
  9. }

(2.) Zainicjuj licznik. Następnie (3.) dopóki jest chociaż jeden niezerowy bit to (4.) sprawdź czy najmniej znaczący bit ma wartość 1. Jeśli tak to (5.) zwiększ licznik. (6.) Na koniec każdej iteracji usuń ostatnią cyfrę liczby (w zapisie binarnym) poprzez przesunięcie o 1 w prawo. (8.) Na koniec zwróć wartość licznik.

Rodzaj liczby

Zastosowanie dotychczas dowolnej metody miało za zadanie jedynie policzyć ilość cyfr 1 w rozwinięciu binarnym liczby. Funkcja podajRodzaj() dla dowolnej liczby a wypisze na ekran w jednej linijce jakiego rodzaju jest podana liczba.

  1. void podajRodzaj(int a) {
  2.   cout << a << " jest ";
  3.   cout << ((policzBity(a) % 2 == 0) ? "diabelska" : "wstretna");
  4. }

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main(), która dla pierwszych 10 liczb poda jakiego są rodzaju:

  1. int main () {
  2.   for (int i = 0; i < 10; i++) {
  3.     podajRodzaj(i);
  4.     cout << "\n";
  5.   }
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję Metody II. Następnie napisz program, który wczyta od użytkownika liczbę a i użyje nowej metody w celu stwierdzenia jej rodzaju.