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. static 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. static bool czyZrownowazonaSysb(int a, int system) {
2.   int[] cyfry = new int[system];
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. static void Main(string[] args) {
2.   Console.Write("Podaj liczbe do sprawdzenia\n a = ");
3.   int a = Convert.ToInt32(Console.ReadLine());
4.   Console.Write("Podaje system\n system = ");
5.   int baza = Convert.ToInt32(Console.ReadLine());
6.   Console.Write("Liczba w systemie {0} jest ", baza);
7.   Console.Write("{0}zrownowazona", czyZrownowazonaSysb(a, baza) ? "" : "nie");
8.   Console.ReadKey();
9. }

• Kod źródłowy Implementacja