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 w2 - wartość drugiego największego elementu zbioru. p2 - pozycja drugiego największego elementu zbioru. p2 Zmienne pomocnicze
i - zmienna licznikowa pętli. i
krok 1: w1 d[n]; p1
krok 2: Jeśli w2 > w1, to w1 w2; p1
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 krok 6: Jeśli w2 > w1, to w1 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 |
// 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"
# 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 "w1 = %2d na pozycji %2d" % (w1, p1)
print "w2 = %2d na pozycji %2d" % (w2, p2)
# Gotowe
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><" + d[i] + "></font></b>";
else if(i == p2) t += " <b><font color=blue>|" + d[i] + "|</font></b>";
else t += " " + d[i] + " ";
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.
Źródło: mgr Jerzy Wałaszek