Znajdowanie największej i drugiej największej liczby w zbiorze

0

Witam,
Mam problem z zadaniem z ksiązki "Algorytmy" pana Macieja Sysło. Mianowicie chodzi o wypisanie największej i drugiej największej liczby w zbiorze. Cały mój problem polega na tym,że ma się to odbywać poprzez "drabinkę turniejową". Tzn. porównujemy liczby parami i dalej bierzemy pod uwagę tylko większą liczbę z każdej kolejnej pary. Tworzą się nowe pary, znowu porównujemy, i tak do momentu aż dojdziemy do największego elementu. Następnie,aby określić drugi największy element, powtarzamy cały algorytm, tylko że za miejsce wcześniej wybranej(najwiekszej) liczby, podstawiamy liczbę bliską zeru,która będzie mniejsza od pozostałych. W ten sposób określimy drugą największa liczbę w tym zbiorze. Jednak nie mam pojęcia jak przerzucić to na C++.

Pozdrawiam. :)

PS:Jeżeli istnieje podobny wątek to przepraszam,ale szukałem i nie mogłem znaleźć.

0

Wartości masz stablicowane? Jeśli tak to robisz jak opisał autor. Raz:

max = 0;
for(int i = 0; i < wielkość_tablicy; i++)
{
    if (tablica[i] > max) max = tablica[i];
}

później drugi raz:

maxDruga = 0;
for(int i = 0; i < wielkość_tablicy; i++)
{
    if (tablica[i] == max) tablica[i] = 0;
    if (tablica[i] > maxDruga) maxDruga = tablica[i]
}

coś w ten deseń

1

Jedziesz po tablicy co dwa pola i porównujesz aktualny element z kolejnym, wynik wpisując do innej tablicy. Po pierwszym wykonaniu masz o połowę mniejszą tablicę na której możesz wykonać to samo działanie. Czy w warunkach zadania jest napisane co w przypadku gdy tablica jest nieparzysta?
Edit: Można też zrealizować ten program na jednej tablicy ale moim zdaniem lepiej zacząć tak jak napisałem a dopiero potem zastanawiać się jak można zrobić to lepiej.

1

Drabinka turniejowa może wyglądać tak:

vector<int> data;

vector<int> a = data, b;
while (a.size()>1)
{
      b.resize((a.size() + 1) / 2);
      b.back() = a.back(); // kopiuj nieparzystego

      for (int i = 0, n = a.size() / 2; i < n; ++i)
      {
            b[i] = std::max(a[2 * i], a[2 * i + 1]);
      }
      std::swap(a, b);
}
0
Tulio napisał(a):

Wartości masz stablicowane? Jeśli tak to robisz jak opisał autor. Raz:

max = 0;
for(int i = 0; i < wielkość_tablicy; i++)
{
    if (tablica[i] > max) max = tablica[i];
}

później drugi raz:

maxDruga = 0;
for(int i = 0; i < wielkość_tablicy; i++)
{
    if (tablica[i] == max) tablica[i] = 0;
    if (tablica[i] > maxDruga) maxDruga = tablica[i]
}

coś w ten deseń

W ten sposób potrafiłbym to zrobić bez problemu,ale chodzi właśnie o tę "drabinkę". :)

i20918 napisał(a):

Jedziesz po tablicy co dwa pola i porównujesz aktualny element z kolejnym, wynik wpisując do innej tablicy. Po pierwszym wykonaniu masz o połowę mniejszą tablicę na której możesz wykonać to samo działanie. Czy w warunkach zadania jest napisane co w przypadku gdy tablica jest nieparzysta?
Edit: Można też zrealizować ten program na jednej tablicy ale moim zdaniem lepiej zacząć tak jak napisałem a dopiero potem zastanawiać się jak można zrobić to lepiej.

Dzięki za odpowiedź. Też wpadłem na ten sposób, jednak pomyślałem sobie, że taki program nie byłby elastyczny,tj. przy większej liczbie elementów potrzebowałbym stworzyć kolejne tablice, na kolejne "szczeble drabinki". A chodzi mi bardziej o program, który poradzi sobie z każdą ilością elementów.

MarekR22 napisał(a):

Drabinka turniejowa może wyglądać tak:

vector<int> data;

vector<int> a = data, b;
while (a.size()>1)
{
      b.resize((data.size() + 1) / 2);
      b.back() = a.back(); // kopiuj nieparzystego

      for (int i = 0, n = data.size() / 2; i < n; ++i)
      {
            b[i] = std::max(a[2 * i], a[2 * i + 1]);
      }
      std::swap(a, b);
}

Dziękuję za odpowiedź! :) Z pewnością skorzystam, jednak jeżeli znajdzie się osoba mająca inny pomysł na ten algorytm to będę bardzo wdzięczny za przedstawienie go tutaj.

1 użytkowników online, w tym zalogowanych: 0, gości: 1