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

©2024 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, 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: ; przeglądamy kolejne
     wykonuj krok K03            ; elementy w zbiorze
K03:   Jeśli Z[i] = k,           ; zliczamy elementy
       to LL + 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, 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,     ; 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 = []
for i in range(N):
    Z.append(random.randrange(10))
k = random.randrange(10)
Z.append(k)  # wartownik
L = 0
i = 0
while True:
    if Z[i] == k:
        L += 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, L - 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

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
©2024 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.