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. static int[] PoliczCyfryZakres(int min, int max)
  2. {
  3. int[] dane = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  4. while (min <= max)
  5. {
  6. int tmp = min;
  7. int dl = (int)Math.Log10(tmp) + 1;
  8. while (dl-- > 0)
  9. {
  10. dane[tmp % 10]++;
  11. tmp /= 10;
  12. }
  13. min++;
  14. }
  15. return dane;
  16. }

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. static void Main(string[] args)
  2. {
  3. Console.Write("Podaj dolny zakres:\n min = ");
  4. int min = Convert.ToInt32(Console.ReadLine());
  5. Console.Write("Podaj górny zakres:\n max = ");
  6. int max = Convert.ToInt32(Console.ReadLine());
  7. int[] dane = PoliczCyfryZakres(min, max);
  8. Console.WriteLine("\nWyniki:");
  9. for (int i = 0; i < 10; i++)
  10. {
  11. Console.WriteLine("{0}\t{1}", i, dane[i]);
  12. }
  13. Console.ReadKey();
  14. }