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

Liczby Nieliczne

https://mattomatti.com/a0025

Definicja

Liczby Nieliczne to takie liczby naturalne, które w zapisie binarnym nie mają dwóch cyfr jeden koło siebie.

Przykład

Przykładowo liczbą nieliczną jest liczba 8 = (1000)2, ale 7 już nie, ponieważ w zapisie występują aż trzy jedynki koło siebie 7 = (111)2.

Ciąg liczb

Ciąg liczb Nielicznych to: 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, ...

Implementacja

Wersja podstawowa

Jedną z najprostszych metod sprawdzenia czy dana liczba jest liczbą Nieliczną jest wybieranie kolejnych bitów liczby i zapamiętywanie jaki był ostatni. Jeśli zarówno aktualny bit jak i poprzedni okazałoby się, że były cyframi jeden tj. prawdą po skonwertowaniu na wartość logiczną to należałoby zwrócić fałsz.

  1. bool czyNieliczna(int a) {
  2.   bool ostatni = false;
  3.   int p = 1;
  4.   for (int i = 0; i <= sizeof(a) * 8; i++, p *= 2) {
  5.     bool aktualny = a & p;
  6.     if (ostatni && aktualny)
  7.       return false;
  8.     ostatni = aktualny;
  9.   }
  10.   return true;
  11. }

W powyższym kodzie funkcja czyNieliczna() przyjmuje jeden argument a, który sprawdzi czy jest liczbą Nieliczną. Na początku (2.) deklarowana jest zmienna ostatni, która będzie przechowywać czy ostastnią wartość była cyfra 1. (3.) Dodatkowo deklarowana jest zmienna p, która będzie używana do wybierania kolejnych cyfr poprzez operację. (4.) W pętli dla każdego bitu: (5.) wybierany jest i-ty bit. (6.) Jeśli aktualny i ostatni bit są cyframi 1 to oznacza, że (7.) nie może być liczbą nieliczną. W przeciwnym wypadku (8.) należy przejść do następnej iteracji uprzednio wartość aktualnego bitu przypisując go do ostatniego. Po zakończeniu każdej iteracji należy pamiętać o pomnożeniu zmiennej p razy dwa, aby przejść do następnego bitu. Jeśli pętla nie zostanie przerwana po sprawdzeniu wszystkich bitów to (10.) można zwrócić, że jest to liczba Nieliczna.

Inne podejście

Poprzedni tok rozumowania można przeformułować następująco: sprawdź każdą kolejną parę bitów i sprawdź czy obie wartości nie są cyframi 1. Tego typu algorytm jest mniej efektywny, ale zdecydowanie prostszy w zapisie i w zrozumieniu.

  1. bool czyNieliczna(int a) {
  2.   int p = 2;
  3.   for (int i = 1; i <= sizeof(a) * 8; i++, p *= 2)
  4.     if ((a & p) && (a & p / 2))
  5.       return false;
  6.   return true;
  7. }

(2.) Tym razem p wskazuje drugi bit. (3.) Numer początkowego bitu należy zaznaczyć również w warunku sprawdzania ile bitów zostało do sprawdzenia. (4.) Sprawdzane są pary bitów na pozycji i-tej oraz pozycji poprzedniej. Jeśli oba bity są cyframi 1 to należy (5.) zwrócić fałsz. Tak samo jak poprzednio jeśli wykonywanie nie zostanie przerwane to (6.) można zwrócić, że to jest to liczba Nieliczna.

Zadania

Zadanie 1

Napisz program, który poda najmniejszą liczbę Nieliczną większą od podanego parametru k. Przykładowo dla liczby k = 22 będzie to 32, a dla k = 5 jest to 8.