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.

C++C#
Python
  1. def PoliczCyfryZakres(min, max):
  2.   dane = [0 for x in range(10)]
  3.   while (min <= max):
  4.     tmp = min
  5.     dl = int(math.log10(tmp)) + 1
  6.     while (dl > 0):
  7.       dane[tmp % 10] += 1
  8.       tmp //= 10
  9.       dl -= 1
  10.     min += 1
  11.   return dane

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:

C++C#
Python
  1. min = int(input("Podaj dolny zakres:\n min = "))
  2. max = int(input("Podaj górny zakres:\n max = "))
  3. dane = PoliczCyfryZakres(min, max)
  4. print("\nWyniki:")
  5. for i in range(10):
  6.   print(i, dane[i], sep='\t')