Algorytmy i Struktury Danych - Zliczanie wg kryterium

Zliczanie (ang. counting) jest równoważne wyszukiwaniu. Tworzymy licznik elementów, który wstępnie zostaje wyzerowany. Następnie przeglądamy kolejne elementy zbioru w poszukiwaniu tych, które spełniają zadane kryterium. Gdy znajdziemy odpowiedni element, zwiększamy stan licznika i wyszukiwanie kontynuujemy od następnego elementu. Wynikiem jest zawartość licznika, czyli liczba elementów w zbiorze spełniających podane kryterium.

Algorytm podajemy w dwóch wariantach – z wyszukiwaniem liniowym oraz z wyszukiwaniem liniowym z wartownikiem. W tym drugim przypadku zawsze zliczamy o jeden element za dużo (elementy zbioru spełniające kryterium plus wartownik). Dlatego zwracamy zawartość licznika pomniejszoną o 1.

W naszym algorytmie kryterium zliczania jest to, iż element zbioru jest równy kluczowi k. W rzeczywistości kryteria mogą być zupełnie inne, np. zliczamy wszystkie elementy zbioru o wartości większej od średniej arytmetycznej wszystkich elementów, zliczamy elementy podzielne przez k, itp.

Algorytm zliczania liniowego

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1.
p : indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. p ∈ C.
k : poszukiwana wartość, czyli tzw. klucz, wg którego zliczamy elementy w Z.

Wyjście:

Liczba elementów zbioru równych k.

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
L : licznik znalezionych elementów, L ∈ C.

Lista kroków:

K01: L ← 0 ; zerujemy licznik
K02: Dla i = p, p+1, …, n-1: ; przeglądamy kolejne
     wykonuj krok K03     ; elementy w zbiorze
K03:   Jeśli Z[i] = k, ; zliczamy elementy
       to L ← L+1      ; spełniające kryterium
K04: Zakończ z wynikiem L ; zwracamy ich liczbę

Algorytm zliczania liniowego z wartownikiem

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n. Ostatni element, Z[n], przeznaczony jest na wartownika.
p : indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. p ∈ C.
k : poszukiwana wartość, czyli tzw. klucz (ang. key), wg którego zliczamy elementy w Z.

Wyjście:

Liczba elementów zbioru równych k.

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
L : licznik znalezionych elementów, L ∈ C.

Lista kroków:

K01: Z[n] ← k ; na koniec zbioru wstawiamy wartownika
K02: L ← 0 ; zerujemy licznik znalezionych elementów
K03: i ← p ; przeszukiwanie rozpoczynamy od pozycji p
K04: Jeśli Z[i] ≠ k,     ; sprawdzamy, czy element i-ty
     to idź do kroku K07 ; spełnia kryterium
K05: L ← L+1 ; jeśli tak, zliczamy go
K06: Jeśli i = n, ; sprawdzamy, czy był to wartownik
     to zakończ z wynikiem L-1
K07: i ← i+1 ; jeśli nie, przechodzimy do następnego elementu
K08: Idź do K04

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 40 liczb pseudolosowych z zakresu od 0 do 9. Wygenerowane liczby zapisuje w tablicy Z. Następnie generuje liczbę pseudolosową k z zakresu od 0 do 9 i zlicza jej wystąpienia w Z. Na końcu wypisuje w jednym wierszu zawartość tablicy Z, a w następnym liczbę k wraz z ilością jej wystąpień w Z.

Pascal

// Zliczanie z wartownikiem
// Data:   27.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 40;

var
  Z : array [0..N] of integer;
  k, i, L : integer;
begin
  randomize;
  for i := 0 to N-1 do
    Z[i] := random(10);
  k    := random(10);
  Z[N] := k;
  L    := 0;
  i    := 0;
  while true do
  begin
    if Z[i] = k then
    begin
      inc(L);
      if i = N then break;
    end;
    inc(i);
  end;
  for i := 0 to N-1 do
    write(Z[i]:2);
  writeln(' ', k, ' : ', L-1);
end.

C++

// Zliczanie z wartownikiem
// Data:   27.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 40;

int main()
{
  int Z[N+1], k, i, L;

  srand(time(NULL));
  for(i = 0; i < N; i++)
    Z[i] = rand() % 10;
  Z[N] = k = rand() % 10;
  L = 0;
  for(i = 0;;i++)
    if(Z[i] == k)
    {
      L++;
      if(i == N) break;
    }
  for(i = 0; i < N; i++)
    cout << setw(2) << Z[i];
  cout << " " << k << ": " << L-1
       << endl;
  return 0;
}

Basic

' Zliczanie z wartownikiem
' Data:   27.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 40

Dim As Integer Z(N), k, i, L

Randomize
For i = 0 To N-1
  Z(i) = Cint(Rnd*9)
Next
k = Cint(Rnd*9)
Z(N) = k
L = 0
i = 0
Do
  If Z(i) = k Then
    L += 1
    If i = N Then Exit Do
  End If
  i += 1
Loop
For i = 0 To N-1
  Print Using "##";Z(i);
Next
Print " ";k;" : ";L-1
End

Python (dodatek)

# Zliczanie z wartownikiem
# Data:   27.04.2008
# (C)2020 mgr Jerzy Wałaszek
# --------------------------

import random

N = 40 # liczba elementów
z = [random.randrange(10) for j in range(N)]
k = random.randrange(10)
z.append(k) # wartownik
cnt, i = 0, 0
while True:
    if z[i] == k:
        cnt += 1
        if i == N: break
    i += 1
c = 0
for i in range(N):
    print("%2d" % z[i], end="")
    c += 1
    if c == 50:
        c = 0
        print()
print()
print(" %1d : %d" % (k, cnt-1))
print()

Wynik:

 2 0 6 8 5 1 7 4 2 8 0 0 0 5 8 7 0 5 5 7 1 5 7 6 0 0 4 6 7 1 7 0 2 4 4 5 1 7 1 1
 5 : 6

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Zliczanie wg kryterium

Problem

Rozwiązanie

Algorytm zliczania liniowego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm zliczania liniowego z wartownikiem

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy