Strona główna » Algorytmy » Artykuły » Ile Cyfr?
 

Ile Cyfr?

https://mattomatti.com/a0244

Zagadka

Dany jest zbiór liczb od 1 do 1000 włącznie. Wśród wszystkich liczb, która cyfra występuje najczęściej, a która najrzadziej? W celu rozwiązania zadania spróbuj znaleźć pewien wzór postępowania. Nie trzeba podawać konkretnej ilości każdej z cyfr.

Odpowiedź

Najczęściej występującą cyfrą jest 1 (występuje 301 razy), a najtrudniej napotkać 0 (występuje 192 razy). Pozostałe cyfry mają tyle samo wystąpień: 300. Jeśli udało Ci się poprawnie zgadnąć to brawo!

Wyjaśnienie

Zadanie to można zrobić na logikę bez wykonywania jakichkolwiek obliczeń. Czemu cyfra 1 występuje najczęściej? Otóż jeśli weźmiemy pod lupę wszystkie liczby od 1 do 999 to każda z cyfr wystąpie dokładnie tyle samo razy. Łatwo to zauważyć np. na liczbach poniżej 100. Zawsze mamy grupę 1 coś, 2 coś itd. i każda z nich ma po 10 wartości. Zakres liczb nie jest do 999, a do 1000, a więc pojawia się dodatkowa cyfra 1 dzięki której jest ona najliczniej reprezentowana.

Jednak... 1000 ma dodatkowe trzy zera, więc dlaczego nie wygrało? Otóż w liczbie przyjmujemy, że 0 może wystąpić po pierwszej niezerowej cyfrze. Przez to 0 jest na straconej pozycji, ponieważ nigdy nie uwzględnimy takich liczb jak 001 czy 079. Innymi słowy nawet trzy dodatkowe cyfry 0 w 1000 nie pomogą tej cyfrze!

Ciekawostka

Dla zainteresowanych osób zamieszczam tabelkę, która przedstawia ilość każdej z cyfr w zakresie od 1 do 10n

od 1 do ..10100100010000
01111922893
12213014001
pozostałe1203004000

Implementacja

Poniższa funkcja PoliczCyfryZakres() pozwala odpowiedzieć na pytanie zadane w zagadce. Dla podanego zakresu liczb min, max zwraca dziesięcioelementową tablicę w której na i-tej pozycji jest zapisana ilość wystąpień cyfry i.

  1. int* PoliczCyfryZakres(int min, int max) {
  2.   int* dane = new int[10]{ 0 };
  3.   while (min <= max) {
  4.     int tmp = min;
  5.     int dl = (int)log10(tmp) + 1;
  6.     while (dl--) {
  7.       dane[tmp % 10]++;
  8.       tmp /= 10;
  9.     }
  10.     min++;
  11.   }
  12.   return dane;
  13. }

Na początku deklarowana jest lista dziesięciu zerowych wartości, a następnie dla każdej liczby w zakresie wyznaczona zostaje jej długość, a następnie wszystkie wystąpienia cyfr w liczbie zostają dołączone do tablicy. Na koniec zwracana jest wyliczona tablica.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu:

  1. int main () {
  2.   int min, max;
  3.   cout << "Podaj dolny zakres:\n min = ";
  4.   cin >> min;
  5.   cout << "Podaj gorny zakres:\n max = ";
  6.   cin >> max;
  7.   int* dane = PoliczCyfryZakres(min, max);
  8.   cout << "\nWyniki:\n";
  9.   for (int i = 0; i < 10; i++) {
  10.     cout << i << "\t" << dane[i] << endl;
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }