Zliczanie wg kryterium


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

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

 

 

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 K03 ; przeglądamy kolejne elementy w zbiorze
K03:     Jeśli Z[i] = k, to LL + 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: ip ; przeszukiwanie rozpoczynamy od pozycji p
K04: Jeśli Z[i] ≠ k, to idź do K07 ; sprawdzamy, czy element i-ty spełnia kryterium
K05: LL + 1 ; jeśli tak, zliczamy go
K06: Jeśli i = n, to zakończ z wynikiem L - 1 ; sprawdzamy, czy był to wartownik
K07: ii + 1 ; jeśli nie, przechodzimy do następnego elementu
K08: Idź do K04  

 

Program

Ważne:

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.

 

Lazarus
// Zliczanie z wartownikiem
// Data:   27.04.2008
// (C)2012 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.
Code::Blocks
// Zliczanie z wartownikiem
// Data:   27.04.2008
// (C)2012 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;
}
Free Basic
' Zliczanie z wartownikiem
' Data:   27.04.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.