Zliczanie

Zacznijmy od prostego problemu – zliczanie wystąpień pojedynczego elementu.

Ile zer jest w napisie?

Proszę napisać funkcję policz(kod, element), której wynikiem jest liczba wystąpień elementu w parametrze kod.

Wynikiem policz('12034056078','0') jest 3,

wynikiem policz('11001001','1') jest 4.

Proszę zauważyć, że w powyższym algorytmie można wyróżnić następujące kroki:

  • wprowadzenie wartości zmiennych kod i element;
  • inicjalizacja zmiennej - przypisujemy zmiennej ile wartość 0;
  • przeglądamy wszystkie elementy i sprawdzamy, czy występuje szukany elementu. Jeśli występuje, zwiększamy o 1 wartość zmiennej ile ;
  • wynikiem jest wartość zmiennej ile.

Algorytm można uogólnić na zliczanie wielu elementów naraz. Wystarczy zmodyfikować algorytm tak, by zamiast pojedynczej zmiennej ile, było wiele zmiennych, na których pamiętamy liczbę wystąpień poszczególnych elementów. Proszę przyjrzeć się poniższemu zadaniu.

Proszę napisać funkcję policz_cyfry(kod), której wynikiem jest liczba wystąpień poszczególnych cyfr w parametrze kod. Wynikiem funkcji powinna być 10-elementowa lista liczb, gdzie pierwszy element to liczba wystąpień 0, drugie - 1 itd.

Wynikiem policz_cyfry('12034056078') jest [3, 1, 1, 1, 1, 1, 1, 1, 1, 0],

wynikiem policz_cyfry('11001001') jest [4, 4, 0, 0, 0, 0, 0, 0, 0, 0].

Niełatwo zauważyć analogię między rozwiązaniami zadania 1 i 2. Konstrukcja algorytmu jest ta sama, algorytmy różnią się strukturą danych. W pierwszym jest to pojedyncza zmienna, w drugim lista 10-elementowa.

W powyższym zapisie można inicjalizację zmiennych za pomocą konstrukcji zwanej listy składane. Zapis jest krótszy, choć nie koniecznie łatwiejszy do rozumienia.

Jeśli chcielibyśmy nie tyle wiedzieć, ile jakich cyfr występuje, ale ile jest różnych cyfr, możemy skorzystać również z powyższego algorytmu. Pozostaje jedynie policzyć, ile cyfr występuje przynajmniej raz. Można to zrobić, licząc, ile jest wartości zerowych i odjąć od ogólnej liczby. Poniżej przedstawiamy trzy różne sposoby.

Jeśli znamy zakres elementów listy i jest ich stosunkowo niedużo, to możemy posortować listę zliczając wystąpienia elementów.

  • Najpierw tworzymy listę złożoną z samych 0 o długości odpowiadjącej zakresowi sorotowanych danych.
  • Potem przeglądamy sorotowaną listę krok po kroku zliczając wystepujące wartości.
  • Na koniec budujemy nową listę kolejno dołaczając elementy według zliczonych wartości.

| Back to top