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. 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:

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.

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")

• Kod źródłowy Implementacja