Wyszukiwanie max

Problem jest następujący. W zbiorze n  elementowym należy wyszukać największą wartość elementu. Zadanie rozwiązujemy następująco:

 

Za chwilowo największy element przyjmujemy pierwszy element zbioru. Następnie kolejno przeglądamy elementy zbioru poczynając od drugiego do ostatniego. Jeśli któryś z przeglądanych elementów jest większy od elementu chwilowo największego, to za nowy chwilowy element największy przyjmujemy ten element zbioru. Gdy przeglądniemy wszystkie elementy element chwilowo największy będzie zawierał największą wartość znalezioną w zbiorze.

 

Algorytm znajdowania największej wartości w zbiorze

Dane wejściowe:

n  - liczba elementów
T[] - tablica n elementowa zawierająca przeszukiwane elementy. Elementy są numerowane od 0 do n-1.

Dane wyjściowe:

vmax - największa wartość w zbiorze

Dane pomocnicze:

i  - indeksy elementów T[]

Lista kroków:

Krok 1: vmaxT[0]
Krok 2: Dla i  = 1,2,...,n-1 wykonuj krok 3
Krok 3:     Jeśli T[i] > vmax, to vmaxT[i]
Krok 4: Zakończ

Przykładowe dane dla programu:

Pierwsza liczba n  określa ilość elementów w zbiorze. Następne n liczb definiuje n  kolejnych elementów. Liczby zbioru są rzeczywiste.

100
309.58 122.55 -378.83 222.614 100.78 281.21 479.2 -67.17 -190.11 -355.854
-452.88 -14.33 -290.82 -382.94 491.62 -114.23 43.68 -165.22 -57.14 451.944
-81.21 429.24 -104.91 147.35 64.24 -420.34 -403.92 -335.13 -307.073 57.658
63.37 -165.96 -322.86 418.46 -63.72 245.47 69.957 435.526 489.225 41.146
311.06 -361.61 369.82 496.097 333.34 248.82 -197.91 -452.55 34.52 370.28
59.767 -50.481 265.92 -35.345 14.21 -161.67 -498.86 -386.22 -124.5 -222.74
319.1 -307.25 -68.49 -489.31 195.34 171.28 -361.22 -493.12 171.47 -409.77
398.42 58.692 378.22 -95.74 297.55 -204.4 362.496 111.386 -220.78 45.943
-199.874 -20.92 410.52 387.28 -221.11 179.67 -327.87 -178.77 176.25 -31.21
-75.48 278.5 -335.4 439.25 -382.8 303.405 207.925 -60.527 -481.694 -29.104
 

Program znajdowania największej wartości w zbiorze n elementowym

 

// Wyszukiwanie max
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    double * T,vmax;
    int i,n;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new double[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy max

    vmax = T[0];

    for(i = 1; i < n; i++)
        if(T[i] > vmax) vmax = T[i];

    // wyświetlamy wynik

    cout << endl << vmax << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}
// Wyszukiwanie min
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    double * T,vmin;
    int i,n;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new double[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy min

    vmin = T[0];

    for(i = 1; i < n; i++)
        if(T[i] < vmin) vmin = T[i];

    // wyświetlamy wynik

    cout << endl << vmin << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

Jednoczesne wyszukiwanie wartości najmniejszej i największej w zbiorze wymaga w powyższym algorytmie wykonania 2n-2 porównań - pętla szukająca wykonuje n-1 obiegów, a w każdym obiegu wykonujemy dwa porównania - jedno dla vmin a drugie dla vmax.

 

// Wyszukiwanie min i max
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    double * T,vmin,vmax;
    int i,n;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new double[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy max

    vmin = vmax = T[0];

    for(i = 1; i < n; i++)
    {
        if(T[i] < vmin) vmin = T[i];
        if(T[i] > vmax) vmax = T[i];
    }

    // wyświetlamy wynik

    cout << endl
         << vmin << endl
         << vmax << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

Okazuje się, iż stosując zasadę dziel i zwyciężaj (ang. divide and conquer) możemy zmniejszyć liczbę porównań, jeśli interesuje nas jednoczesne znalezienie wartości min i max w zbiorze. Zasada jest następujące:

 

Zbiór dzielimy na dwa równe zbiory, elementów mniejszych i większych. Podziału dokonujemy biorąc ze zbioru po dwa elementy i porównując je ze sobą. Element mniejszy zaliczymy do zbioru elementów mniejszych, a element większy zaliczymy do zbioru elementów większych. Operacja ta wymaga, aby zbiór posiadał parzystą liczbę elementów (jeśli ma nieparzystą liczbę elementów, to ostatni element dublujemy). Ponieważ bierzemy po dwa elementy, wykonamy n/2 porównań. Teraz w zbiorze elementów mniejszych szukamy min. Operacja ta wymaga n/2 - 1 porównań, ponieważ elementy te tworzą tylko połowę elementów wejściowego zbioru. Podobnie w zbiorze elementów większych szukamy max. Ta operacja również wymaga n/2 - 1 porównań. W efekcie otrzymujemy:

n/2 + n/2 - 1 + n/2 - 1 = 3/2n - 2 porównań, co jest mniejsze od 2n-2!

 

Algorytm znajdowania jednocześnie min i max w zbiorze

Dane wejściowe:

n  - liczba elementów, musi być parzysta.
T[] - tablica n elementowa zawierająca przeszukiwane elementy. Elementy są numerowane od 0 do n-1.

Dane wyjściowe:

vmin - najmniejsza wartość w zbiorze

vmax - największa wartość w zbiorze

Dane pomocnicze:

i  - indeksy elementów T[]

Lista kroków:

Krok 1: Jeśli T[0] > T[1], to idź do kroku 5
Krok 2: vminT[0]
Krok 3: vmaxT[1]
Krok 4: Idź do kroku 7
Krok 5: vminT[1]
Krok 6: vmax T[0]
Krok 7: Dla i  = 2,4,...,n-2: wykonuj kroki 8...14
Krok 8:     Jeśli T[i] > T[i+1], to idź do kroku 12
Krok 9:     Jeśli T[i] < vmin, to vminT[i]
Krok 10:       Jeśli T[i+1] > vmax, to vmaxT[i+1]
Krok 11:     Wykonaj następny obieg pętli
Krok 12:     Jeśli T[i] > vmax, to vmaxT[i]
Krok 13:     Jeśli T[i+1] < vmin, to vmin T[i+1]
Krok 14:     Wykonaj następny obieg pętli
Krok 15: Zakończ

 

Program jednoczesnego znajdowania min i max w zbiorze n elementowym

 

// Wyszukiwanie min i max
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    double * T,vmin,vmax;
    int i,n;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n + 1 elementach

    T = new double[n+1];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // dublujemy ostatni element, gdyby n było nieparzyste

    T[n] = T[n-1];

    // bierzemy dwa pierwsze elementy, mniejszy do vmin, a większy do vmax

    if(T[0] > T[1])
    {
        vmin = T[1]; vmax = T[0];
    }
    else
    {
        vmin = T[0]; vmax = T[1];
    }

    // szukamu min i max wśród pozostałych elementów

    for(i = 2; i < n; i += 2)
      if(T[i] > T[i+1])
      {
          if(T[i]   > vmax) vmax = T[i];
          if(T[i+1] < vmin) vmin = T[i+1];
      }
      else
      {
          if(T[i+1] > vmax) vmax = T[i+1];
          if(T[i]   < vmin) vmin = T[i];
      }

    // wyświetlamy wynik

    cout << endl
         << vmin << endl
         << vmax << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe