Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Zliczanie wg kryterium

SPIS TREŚCI
Tematy pomocnicze

Problem

W n-elementowym zbiorze Z  należy zliczyć elementy posiadające pożądane własności.

Rozwiązanie

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, nN.
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. pC.
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, LC.

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, nN.
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. pC.
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. iC.
L  – licznik znalezionych elementów, LC.

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
Zliczanie liniowe z wartownikiem
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.