Strona główna » Algorytmy » Teoria Liczb » Liczby Zrównoważone
 

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 102 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 10012 = 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. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1