Strona główna » Algorytmy » Teoria Liczb » Liczby Szalone
 

Liczby Szalone

Definicja

Liczbę a nazywamy szaloną kiedy jest liczbą całkowitą, która zawiera co najwyżej i cyfr równych i. W prostszych słowach oznacza to, że nie zawiera zer. Natomiast zawiera co najwyżej jedną jedynkę, dwie dwójki, ..., dziewięć dziewiątek.

Liczbami szalonymi są kolejno: 1, 2, 3, ..., 12, 13, ..., 22, 23, ..., 122, ... itd., ale nie 11, 222 czy 211.

Analiza

Z definicji wynika, że budowa liczby jest ograniczona poprzez ilość wystąpień określonej cyfry. Na tej podstawie można stwierdzić, że najmniejsza liczba szalona to 1, a największa to 999999999888888887777777666666555554444333221. Ma ona dokładnie 45 cyfr co odpowiada sumie liczb od 1 do 9. Co więcej wszystkie liczby szalone długości n to wszystkie permutacje dowolnych n cyfr wybranych z największej cyfry. (Rzecz jasna podążając ślepo za tym zdaniem uzyska się kilka razy tą samą n-cyfrową liczbę).

Implementacja

Chcąc odkryć czy liczba jest szalona trzeba sprawdzić ile ma każdych cyfr, a następnie sprawdzić czy któryś z cyfr nie ma za dużo. Jednak to sprawdzenie warto wykonać bezpośrednio po zwiększeniu licznika. Jeśli licznik przekroczy maksimum wcześniej nie będzie trzeba analizować całej liczby, że nie jest szalona. Kod realizujący to zadanie przedstawiam poniżej:

  1. bool czy_szalona(int a){
  2.   int* l = new int[10];
  3.   for(int i = 0; i < 10; i++)
  4.     l[i] = 0;
  5.   do {
  6.     l[a%10]++;
  7.     if(l[a%10] > a%10){
  8.       delete[] l;
  9.       return false;
  10.     }
  11.     a/=10;
  12.   } while(a > 0);
  13.   delete[] l;
  14.   return true;
  15. }

(1.) Funkcja przyjmuje jeden argument a - liczbę do sprawdzenia czy jest szalona. Wynikiem jest wartość logiczna czy tak jest czy nie. (2.) Alokowane jest lista dziesięciu liczb, które będą licznikami każdej z cyfr. (3. - 4.) Oczywiście należy pamiętać o wyzerowaniu liczników. (5.) Następnie dla każdej cyfry w liczbie: (6.) zwiększamy odpowiedni licznik. (7.) Aplikacja sprawdza czy licznik nie ma zbyt dużej wartości. Jeśli tak to (8.) dealokujemy liczniki i (9.) zwracamy fałsz. Jeśli jednak licznik ma odpowiednią wartość to (10.) usuwamy przejrzaną cyfrę i (11.) powtarzamy dopóki są jakiekolwiek cyfry. (12.) Jeśli pętla for nie zostanie ani razu przerwana oznacza to, że wystarczy (13.) zdealokować liczniki i (14.) zwrócić prawdę.

Testowanie funkcji

Funkcją można wykorzystać do wypisania wszystkich liczb szalonych w zakresie [0, 100]:

  1. int main () {
  2.   for(int i = 0; i < 100; i++){
  3.     if(czy_szalona(i)){
  4.       cout << i << endl;
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz program, który wczyta wartości a i b, a następnie wypisze wszystkie liczby szalone z zakresu od [a, b]. Liczby a i b należą z przedziału 1 ≤ a ≤ b ≤ 1012