Algorytmy i Struktury Danych

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.

Zmienne 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: wykonuj krok K03	przeglądamy kolejne elementy w zbiorze
K03:	Jeśli Z [ i ] = k, to L ← L + 1	zliczamy elementy spełniające kryterium
K04:	Zakończ z wynikiem L

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, wg którego zliczamy elementy w Z.

Wyjście:

Liczba elementów zbioru równych k.

Zmienne 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, to idź do kroku K07	sprawdzamy, czy element i-ty spełnia kryterium
K05:	L ← L + 1	jeśli tak, zliczamy go
K06:	Jeśli i = n, to zakończ z wynikiem L - 1	sprawdzamy, czy był to wartownik
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:2, ' : ', L - 1 );
end.

C++

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

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 40;

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

  srand ( ( unsigned )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 << setw ( 2 ) << 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 Using "## : ##";k;L-1
End

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

Na początek: podrozdziału 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:

Zmienne pomocnicze:

Lista kroków:

Algorytm zliczania liniowego z wartownikiem

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy