Serwis Edukacyjny w I-LO w Tarnowie 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 |
ProblemW n-elementowym zbiorze Z należy 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.
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ę
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
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. |
// 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 |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.