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.

C++C#
Python
  1. def czyZrownowazonaBin(a):
  2.   cyf0 = 0
  3.   cyf1 = 0
  4.   while (a != 0):
  5.     if (a % 2 == 0):
  6.       cyf0 += 1
  7.     else:
  8.       cyf1 += 1
  9.     a = int(a / 2)
  10.   return cyf0 == cyf1

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:

C++C#
Python
  1. def czyZrownowazonaSysb(a, system):
  2.   cyfry = [0] * system
  3.   while (a != 0):
  4.     cyfry[a % system] += 1
  5.     a = int(a / system)
  6.   for i in range(1, system):
  7.     if (cyfry[i - 1] != cyfry[i]):
  8.       return False
  9.   return True

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.

C++C#
Python
  1. a = int(input("Podaj liczbe do sprawdzenia\n a = "))
  2. baza = int(input("Podaje system\n system = "))
  3. print("Liczba w systemie " + str(baza) + " jest ", end = "")
  4. print(("" if czyZrownowazonaSysb(a, baza) else "nie") + "zrownowazona")
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1