Login lub e-mail Hasło   

Algorytmy wyszukujące - k-ty największy element

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Na początek rozwiążmy prostszy problem: W n elementowym zbiorze ( n > 1) znaleźć drugi największy element. Jeśli z...
Wyświetlenia: 3.212 Zamieszczono 03/11/2006

Na początek rozwiążmy prostszy problem:

W n elementowym zbiorze (n > 1) znaleźć drugi największy element.

Jeśli zbiór jest uporządkowany, to zadanie staje się trywialnie proste - zwracamy przedostatni element. W przypadku zbioru nieuporządkowanego możemy zbiór posortować i zwrócić przedostatni element. Jednakże sortowanie jest kosztowne i zajmuje drogocenny czas. Istnieje o wiele prostsza metoda, która wymaga jednokrotnego przeglądnięcia zbioru, zatem ma klasę czasowej złożoności obliczeniowej O(n). Co więcej, nie zmienia ona struktury zbioru (kolejności elementów) oraz nie wymaga dodatkowej pamięci zależnej od ilości elementów w zbiorze.

Umówmy się, iż wynikiem poszukiwań będzie wartość elementu zbioru oraz jego położenie, czyli indeks. Dodatkowo nasz algorytm będzie zwracał wartość oraz położenie największego elementu w zbiorze.

Dane wejściowe

n - ilość elementów w przeszukiwanym zbiorze.  n N
d[ ] - zbiór, w którym poszukujemy drugiego największego elementu. Indeksy elementów rozpoczynają się od 1.

Dane wyjściowe

w1 - wartość największego elementu zbioru.
p1 - pozycja największego elementu zbioru. p1 N
w2 - wartość drugiego największego elementu zbioru.
p2 - pozycja drugiego największego elementu zbioru. p2 N

Zmienne pomocnicze

i - zmienna licznikowa pętli. i N
krok 1: w1 d[n];   p1 n;   w2 d[n - 1];   p2 n - 1
krok 2: Jeśli w2 > w1, to  w1 w2;   p1 p2
krok 3: Dla i = n - 2, n - 3,...,1: wykonuj kroki 4...6
krok 4:     Jeśli d[i] > w2, to idź do kroku 5. Inaczej wykonaj następny obieg pętli z kroku 3.
krok 5:     w2 d[i];   p2 i;
krok 6:     Jeśli w2 > w1, to  w1 w2;   p1 p2
krok 7: Zakończ algorytm

Na początku algorytmu wybieramy ze zbioru dwa ostatnie elementy i umieszczamy je odpowiednio w zmiennych w1 i w2. Dlaczego rozpoczynamy od końca zbioru? Otóż jeśli w przyszłości posortujemy zbiór stabilnym algorytmem sortującym (czyli takim, który nie zmienia kolejności elementów równych), to wyznaczony przez nasz algorytm drugi największy element będzie przedostatnim elementem zbioru posortowanego. Rozpoczynając przeglądanie od początku zbioru nie mielibyśmy takiej gwarancji (na przykład w przypadku, gdy w zbiorze są dwa elementy równe drugiemu największemu elementowi zbioru).

W zmiennych p1 i p2 zapamiętujemy pozycję tych elementów.

Umawiamy się, iż w1, p1 identyfikuje największy element w zbiorze, a w2 i p2 identyfikuje drugi największy element. Po inicjalizacji zmiennych musimy sprawdzić, czy wprowadzone do nich dane spełniają ten warunek. Jeśli nie, to wymieniamy ze sobą odpowiednie zawartości zmiennych.

Rozpoczynamy pętlę przeglądającą kolejne elementy zbioru od n - 2 do pierwszego. Pozycje n i n - 1 pomijamy, ponieważ odpowiadające im elementy są już w w1 i w2.

W każdym obiegu pętli sprawdzamy, czy i-ty element zbioru jest większy od tymczasowego drugiego największego elementu, czyli w2. Jeśli tak, to zapamiętujemy i-ty element w w2 oraz jego pozycję w p2. Teraz musimy sprawdzić, czy operacja ta nie spowodowała, iż w2 stało się większe od w1. Jeśli tak, to wymieniamy ze sobą zawartości zmiennych w1 z w2 oraz p1 z p2.

Po zakończeniu pętli w zmiennej w1 mamy wartość największego elementu zbioru, w p1 jego pozycję w zbiorze, w w2 mamy wartość drugiego największego elementu zbioru i w p2 jego pozycję. Algorytm kończymy.

   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Program tworzy 100 elementowy zbiór liczb pseudolosowych z zakresu od 0 do 99 i wyszukuje w nim elementu największego oraz drugiego elementu największego.

Efekt uruchomienia programu
Wyszukiwanie drugiego największego elementu
-------------------------------------------
(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie

31 69 9 75 89 98 38 65 14 71 2 47 67 34 71 94 92 90 39 1
55 66 36 66 23 99 53 89 51 52 10 |99| 7 52 29 6 16 56 48 79
31 38 53 45 26 2 31 15 20 27 61 41 21 22 16 85 92 22 95 27
53 2 86 87 <99> 12 44 80 42 41 2 90 86 13 1 73 19 93 51 83
36 29 11 24 80 19 97 25 19 94 18 46 35 39 29 97 48 26 19 98

w1 = 99 na pozycji 65
w2 = 99 na pozycji 32

KONIEC. Naciśnij dowolny klawisz...

// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//---------------------------------------------

program search2b;

{$APPTYPE CONSOLE}

// Procedura wymienia zawartość dwóch zmiennych
// przekazanych jako parametry
//---------------------------------------------
procedure Zamien(var a, b : integer);
var
x : integer;
begin
x := a; a := b; b := x;
end;

const
N = 100; // Liczba elementów w zbiorze
M = 99; // Maksymalna wartość elementu

var
d : array[1..N] of integer;
i,p1,p2,w1,w2 : integer;

begin
writeln('Wyszukiwanie drugiego najwiekszego elementu');
writeln('-------------------------------------------');
writeln('(C)2006 mgr Jerzy Walaszek I LO w Tarnowie');
writeln;

// Generujemy zbiór pseudolosowy

randomize;
for i := 1 to N do d[i] := random(M + 1);

// Szukamy elementu

w1 := d[N]; p1 := N; w2 := d[N - 1]; p2 := N - 1;
if w2 > w1 then
begin

Zamien(w1, w2); Zamien(p1, p2);
end;
for i := N - 2 downto 1 do
if
d[i] > w2 then
begin

w2 := d[i]; p2 := i;
if w2 > w1 then
begin

Zamien(w1, w2); Zamien(p1, p2);
end;
end;

// Prezentujemy wyniki

for i := 1 to N do
if
i = p1 then
write('<', d[i]:2, '>')
else if i = p2 then
write('|', d[i]:2, '|')
else
write(' ', d[i]:2, ' ');
writeln;
writeln('w1 =', w1:3, ' na pozycji ', p1:3);
writeln('w2 =', w2:3, ' na pozycji ', p2:3);

// Gotowe

writeln;
writeln('Nacisnij klawisz Enter...');
readln;
end.
// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//---------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Procedura wymienia zawartość dwóch zmiennych
// przekazanych jako parametry
//---------------------------------------------
void Zamien(int &a, int &b)
{
int x;

x = a; a = b; b = x;
}


int main(void)
{
const int N = 100; // Liczba elementów w zbiorze
const int M = 99; // Maksymalna wartość elementu

int d[N],i,p1,p2,w1,w2;

cout << "Wyszukiwanie drugiego najwiekszego elementu\n"
"-------------------------------------------\n"
"(C)2006 mgr Jerzy Walaszek I LO w Tarnowie\n\n"
;

// Generujemy zbiór pseudolosowy

srand((unsigned)time(NULL));
for(i = 0; i < N; i++) d[i] = rand() % (M + 1);

// Szukamy elementu

w1 = d[N - 1]; p1 = N - 1; w2 = d[N - 2]; p2 = N - 2;
if(w2 > w1)
{
Zamien(w1, w2); Zamien(p1, p2);
}
for(i = N - 3; i >= 0; i--)
if(d[i] > w2)
{
w2 = d[i]; p2 = i;
if(w2 > w1)
{
Zamien(w1, w2); Zamien(p1, p2);
}
}

// Prezentujemy wyniki

for(i = 0; i < N; i++)
if(i == p1) cout << "<" << setw(2) << d[i] << ">";
else if(i == p2) cout << "|" << setw(2) << d[i] << "|";
else cout << " " << setw(2) << d[i] << " ";
cout << endl;
cout << "w1 =" << setw(3) << w1 << " na pozycji " << setw(2) << p1 << endl;
cout << "w2 =" << setw(3) << w2 << " na pozycji " << setw(2) << p2 << endl;

// Gotowe

cout << endl;
system("PAUSE"); return 0;
}
' Wyszukiwanie drugiego największego elementu
'---------------------------------------------
' (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
'---------------------------------------------

Module Module1

Sub Main()
Const N = 100 ' Liczba elementów w zbiorze
Const M = 99 ' Maksymalna wartość elementu

Dim d(N), i, p1, p2, w1, w2, tmp As Integer

Console.WriteLine("Wyszukiwanie drugiego największego elementu")
Console.WriteLine("-------------------------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie")
Console.WriteLine()

' Generujemy zbiór pseudolosowy

Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

' Szukamy elementu

w1 = d(N) : p1 = N : w2 = d(N - 1) : p2 = N - 1
If w2 > w1 Then
tmp = w1 : w1 = w2 : w2 = tmp
tmp = p1 : p1 = p2 : p2 = tmp
End If
For
i = N - 2 To 1 Step -1
If d(i) > w2 Then
w2 = d(i) : p2 = i
If w2 > w1 Then
tmp = w1 : w1 = w2 : w2 = tmp
tmp = p1 : p1 = p2 : p2 = tmp
End If
End If
Next


' Prezentujemy wyniki

For i = 1 To N
If i = p1 Then
Console.Write("<{0,2}>", d(i))
ElseIf i = p2 Then
Console.Write("|{0,2}|", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next

Console.WriteLine()
Console.WriteLine("w1 = {0,2} na pozycji {1,3}", w1, p1)
Console.WriteLine("w2 = {0,2} na pozycji {1,3}", w2, p2)

' Gotowe

Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
# -*- coding: cp1250 -*-
# Wyszukiwanie drugiego największego elementu
#---------------------------------------------
# (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
#---------------------------------------------

import random

N = 100 # Liczba elementów w zbiorze
M = 99 # Maksymalna wartość elementu

d = []

print "Wyszukiwanie drugiego najwiekszego elementu"
print "-------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek I LO w Tarnowie"
print

# Generujemy zbiór pseudolosowy

for i in range(N): d.append(random.randint(0, M))

# Szukamy elementu

w1, p1 = d[N - 1], N - 1
w2, p2 = d[N - 2], N - 2
if w2 > w1:
w1, w2 = w2, w1
p1, p2 = p2, p1
for i in range(N - 3, -1, -1):
if d[i] > w2:
w2, p2 = d[i], i
if w2 > w1:
w1, w2 = w2, w1
p1, p2 = p2, p1

# Prezentujemy wyniki

for i in range(N):
if i == p1: print "<%2d>" % d[i],
elif i == p2: print "|%2d|" % d[i],
else: print " %2d " % d[i],
print
print

print "w1 = %2d na pozycji %2d" % (w1, p1)
print "w2 = %2d na pozycji %2d" % (w2, p2)

# Gotowe

print
raw_input("Nacisnij klawisz ENTER...")
<html>
<head>
</head>
<body>
<div align=
"center">
<form style=
"BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"
name="frmSearch2B">
<h4 id="out_t0" style="text-align: center">
Wyszukiwanie drugiego największego elementu
</h4>
<p style=
"TEXT-ALIGN: center">
(C)2006 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<p style=
"TEXT-ALIGN: center">
<input type=
"button" value="Szukaj" name="B1" onclick="main();">
</p>
<p style=
"TEXT-ALIGN: center" id="t_out">...</p>
</form>

<script language=
javascript>

// Wyszukiwanie drugiego największego elementu
//---------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//---------------------------------------------

function main()
{
var N = 100; // Liczba elementów w zbiorze
var M = 99; // Maksymalna wartość elementu

var d = new Array(N);
var i,p1,p2,w1,w2,x;

// Generujemy zbiór pseudolosowy

for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Szukamy elementu

w1 = d[N - 1]; p1 = N - 1; w2 = d[N - 2]; p2 = N - 2;
if(w2 > w1)
{
x = w1; w1 = w2; w2 = x;
x = p1; p1 = p2; p2 = x;
}
for(i = N - 3; i >= 0; i--)
if(d[i] > w2)
{
w2 = d[i]; p2 = i;
if(w2 > w1)
{
x = w1; w1 = w2; w2 = x;
x = p1; p1 = p2; p2 = x;
}
}

// Prezentujemy wyniki

t = "";
for(i = 0; i < N; i++)
if(i == p1) t += " <b><font color=red>&lt;" + d[i] + "&gt;</font></b>";
else if(i == p2) t += " <b><font color=blue>|" + d[i] + "|</font></b>";
else t += " &nbsp;" + d[i] + "&nbsp;";
t += "<br><br>";
t += "<b><font color=red>w1 = " + w1 + " na pozycji " + p1 + "</font></b><br>";
t += "<b><font color=blue>w2 = " + w2 + " na pozycji " + p2 + "</font></b>";

// Gotowe

document.getElementById("t_out").innerHTML = t;
}

</script>
</div>
</body>
</html>
 
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6262
16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64980
12
komentarze: 3 | wyświetlenia: 29779
37
komentarze: 9 | wyświetlenia: 28522
11
komentarze: 2 | wyświetlenia: 33154
18
komentarze: 11 | wyświetlenia: 9268
7
komentarze: 1 | wyświetlenia: 34650
17
komentarze: 4 | wyświetlenia: 14189
15
komentarze: 5 | wyświetlenia: 32763
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 1 | wyświetlenia: 86408
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska