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 |
Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:
Krok | Operacja |
Liczba wykonań |
1 |
minZ ← Z[0] |
1 |
2 |
maxZ ← Z[0] |
1 |
3 |
i ← 1
|
1 |
4 |
Jeśli i = n, to idź do kroku 9 |
n
|
5 |
Jeśli Z[i] < minZ, to minZ ← Z[i] |
n - 1
|
6 |
Jeśli Z[i] > maxZ, to maxZ ← Z[i] |
n - 1
|
7 |
i ← i + 1 |
n - 1
|
8 |
Idź do 4 |
n - 1
|
9 |
Pisz minZ, maxZ |
1 |
10 |
Zakończ |
1 |
Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy
element zbioru z minZ oraz z maxZ. Tutaj tkwi nieefektywność. Obie operacje
Wyobraźmy sobie, iż ze zbioru bierzemy parę 2 elementów i porównujemy je ze sobą. Element większy nie może być minimalnym, zatem nie musimy go już porównywać z minZ. Wystarczy porównanie z maxZ. To samo dotyczy elementu mniejszego – porównujemy go tylko z minZ. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z minZ i maxZ). Teraz mamy:
Jedno porównanie dwóch elementów, które rozdzieli je na element
mniejszy i element większy.
Element mniejszy porównujemy z minZ.
Element większy porównujemy z maxZ.
Daje to 3 porównania zamiast 4. Ponieważ ze zbioru pobieramy po dwa kolejne elementy, to ich liczba musi być parzysta. Jeśli zbiór ma nieparzystą liczbę elementów, to po prostu dublujemy ostatni element i dostaniemy parzystą liczbę elementów.
Porównanie pary elementów dzieli zbiór na dwa podzbiory – zbiór elementów większych i mniejszych. W podzbiorze elementów większych szukamy elementu maksymalnego, a w podzbiorze elementów mniejszych szukamy minimalnego. Ponieważ ich liczebność jest o połowę mniejsza od liczebności zbioru wejściowego, to wykonamy mniej operacji porównań.
Metoda rozwiązywania problemów przez podział na mniejsze części w informatyce nosi nazwę Dziel i Zwyciężaj (ang. Divide and Conquer). Dzięki niej często udaje się zmniejszyć złożoność obliczeniową wielu algorytmów.
K01: Jeśli n mod 2 = 1, ; jeśli nieparzysta liczba elementów, to Z[n] ← Z[n-1] ; dublujemy ostatni K02: minZ ← największa liczba całkowita ; inicjujemy minZ i maxZ K03: maxZ ← najmniejsza liczba całkowita K04: i ← 0 K05: Dopóki i < n: ; wybieramy pary kolejnych elementów wykonuj kroki K06…K12 K06: Jeśli Z[i] > Z[i+1], ; rozdzielamy je na element to idź do K10 ; mniejszy i większy K07: Jeśli Z[i] < minZ, ; Z[i] : mniejszy, Z[i+1] : większy to minZ ← Z[i] K08: Jeśli Z[i+1] > maxZ, to maxZ ← Z[i+1] K09: Idź do K12 K10: Jeśli Z[i] > maxZ, ; Z[i] - większy, Z[i+1] - mniejszy to maxZ ← Z[i] K11: Jeśli Z[i+1] < minZ, to minZ ← Z[i+1] K12: i ← i + 2 ; przechodzimy do następnej pary elementów K13: Pisz minZ, maxZ ; wyprowadzamy wyniki K14: Zakończ
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 15 liczb
pseudolosowych z zakresu |
Pascal// Jednoczesne min i max // Data: 30.04.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- program prg; const N = 15; var Z : array [0..N] of integer; minZ, maxZ, i : integer; begin randomize; for i := 0 to N - 1 do Z [i] := random (10000); if N mod 2 = 1 then Z[N] := Z[N-1]; minZ := 10000; maxZ := -1; i := 0; while i < N do begin if Z[i] > Z[i+1] then begin if Z[i] > maxZ then maxZ := Z[i]; if Z[i+1] < minZ then minZ := Z[i+1]; end else begin if Z[i] < minZ then minZ := Z[i]; if Z[i+1] > maxZ then maxZ := Z[i+1]; end; inc(i, 2); end; for i := 0 to N-1 do writeln(Z[i]:4); writeln; writeln(minZ, ' : ', maxZ); writeln; end. |
// Jednoczesne min i max // Data: 30.04.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> #include <cstdlib> #include <ctime> using namespace std; const int N = 15; int main() { int Z[N+1], minZ, maxZ, i; srand(time(NULL)); for(i = 0; i < N; i++) Z[i] = rand() % 10000; if(N % 2) Z[N] = Z[N-1]; minZ = 10000; maxZ = -1; for(i = 0; i < N; i += 2) if(Z[i] > Z[i+1]) { if(Z[i] > maxZ) maxZ = Z[i]; if(Z[i+1] < minZ) minZ = Z[i+1]; } else { if(Z[i] < minZ) minZ = Z[i]; if(Z[i+1] > maxZ) maxZ = Z[i+1]; } for(i = 0; i < N; i++) cout << setw (4) << Z[i] << endl; cout << endl << minZ << ": " << maxZ << endl << endl; return 0; } |
Basic' Jednoczesne min i max ' Data: 30.04.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Const N = 15 Dim As Integer Z(N), minZ, maxZ, i Randomize For i = 0 To N-1 Z(i) = Cint(Rnd * 9999) Next If N Mod 2 = 1 Then Z(N) = Z(N-1) minZ = 10000: maxZ = -1 i = 0 While i < N If Z(i) > Z(i+1) Then If Z(i) > maxZ Then maxZ = Z(i) If Z(i+1) < minZ Then minZ = Z(i+1) Else If Z(i) < minZ Then minZ = Z(i) If Z(i+1) > maxZ Then maxZ = Z(i+1) End If i += 2 Wend For i = 0 To N-1 Print Using "####";Z(i) Next Print Print minZ;" : ";maxZ Print End |
Python
(dodatek)# Jednoczesne min i max # Data: 24.02.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- import random N = 15 # Liczba elementów Z = [] # Tablica for i in range(N): Z.append(random.randrange(10000)) if N % 2: Z.append(Z[N-1]) minZ, maxZ, i = 10000, -1, 0 while i < N: if Z[i] > Z[i+1]: if Z[i] > maxZ: maxZ = Z[i] if Z[i+1] < minZ: minZ = Z[i+1] else: if Z[i] < minZ: minZ = Z[i] if Z[i+1] > maxZ: maxZ = Z[i+1] i += 2 for i in range(N): print("%4d" % Z[i]) print() print(minZ,":",maxZ) print() |
Wynik: |
4850 3151 2213 272 7933 2490 1267 4923 713 987 3253 5533 1759 8103 9414 272 : 9414 |
![]() |
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.