Liczby Zrównoważone

Definicja

Liczba zrównoważona w pewnym systemie liczbowym b to taka liczba w której tyle samo razy występuje każda z cyfr tego systemu.

Przykład

W systemie binarnym są tylko dwie cyfry: 0 oraz 1. Najmniejsza liczba zrównoważona w tym systemie to 10₂ czyli 2. Liczbą zrównoważoną nie jest np. 1, ponieważ wszystkie nieznaczące zera muszą zostać usunięte z liczby tj. 01 to 1. Kolejna liczba to 1001₂ = 9. Układając liczby w ciąg otrzymamy:

2, 9, 10, 12, 35, 37, 38, 41, 42, 44, ..

Z kolei w systemie trójkowym ciąg ten przedstawia się następująco:

11, 15, 19, 21, 260, 266, 268, 278, 290, 294, ..

Implementacja

System binarny

W celu określenia czy liczba w zapisie binarnym jest zrównoważona wymaga policzenia bitów ustawionych na zero i tych ustawionych na 1. W tym uproszczonym scenariuszu wystarczą w tym celu dwie zmienne oraz pętle, która będzie odpowiednio je zwiększać w zależności od kolejnej reszty podczas dzielenia. Wynikiem jest wartość logiczna, która jest wynikiem porównania dwóch liczników.

1. bool czyZrownowazonaBin(int a) {
2.   int cyf0 = 0;
3.   int cyf1 = 0;
4.   while (a != 0) {
5.     if (a % 2 == 0) {
6.       cyf0++;
7.     } else {
8.       cyf1++;
9.     }
10.     a /= 2;
11.   }
12.   return cyf0 == cyf1;
13. }

Dowolny system

Zastanówmy się jak należałoby zmienić powyższy algorytm, aby można było sprawdzić czy liczba jest zrównoważona w dowolnym systemie. Po pierwsze nie wystarczą już tylko dwa liczniki, ponieważ w systemie o podstawie b jest dokładnie b cyfr (licząc razem z 0). Najbardziej praktyczna będzie tutaj tablica, która początkowo zostanie wypełniona samymi zerami.

Kolejny zmiany dotyczą pętli. Dotychczas pobierana była reszta z dzielenia przez 2, teraz będzie trzeba dzielić przez b i dokładnie przez tą samą później podzielić całą liczbę. Na koniec wystarczy sprawdzić czy kolejne pary liczb są identyczne. Jeśli tak to znaczy, że liczba jest zrównoważona. W przeciwnym razie należy zwrócić wartość fałsz.

Oto przykładowy kod po wprowadzeniu stosownych modyfikacji:

1. bool czyZrownowazonaSysb(int a, int system) {
2.   int* cyfry = new int[system] {0};
3.   while (a != 0) {
4.     cyfry[a % system]++;
5.     a /= system;
6.   }
7.   for (int i = 1; i < system; i++)
8.     if (cyfry[i - 1] != cyfry[i])
9.       return false;
10.   return true;
11. }

Testowanie funkcji

W celu przetestowania funkcji, która sprawdza czy liczba jest zrównoważona w pewnym systemie wystarczy poniższy kod. Wczyta on od użytkownika liczbę oraz system, a następnie wypisze na ekran wynik.

1. int main() {
2.   int a, baza;
3.   cout << "Podaj liczbe do sprawdzenia\n a = ";
4.   cin >> a;
5.   cout << "Podaje system\n system = ";
6.   cin >> baza;
7.   cout << "Liczba w systemie " << baza << " jest ";
8.   cout << (czyZrownowazonaSysb(a, baza) ? "" : "nie") << "zrownowazona";
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja