znajdywanie maxa i minimum

int main(){
    int n, nr, max, min;
    cin>>n>>nr;
    max = nr; min = nr;
    for(int i=0; i<(n-1); i++){
            cin>>nr;
            if(nr>max) max = nr;
            if(nr<min) min = nr;
    }
    cout<<max<<" "<<min;
    system("pause");
}

Czy ktoś ma inny pomysł na napisanie funkcji w C++ do znajdywania minimum i maksimum?

można użyć funkcji std::max i std::min, albo nawet std::max_element i std::min_element z nagłówka <algorithm>, ale to trochę strzelanie do muchy. twoje rozwiązanie jest dobre.

wiem, że są gotowe algorytmy, ale bardziej skłaniam się ku pomysłom na własne rozwiązanie.. dlatego też pytam Was drodzy programiści o taką funkcję, bo wiem że moja nie jest doskonała.

Pomijając kwestię iostream vs cstdio (wybierz cstdio jeśli piszesz na SPOJa), to jest coś co możesz poprawić.

Wczytuj wartości parami, mniejszą liczbę z pary porównuj z minimum, a większą z maksimum. Dzięki temu możesz zaoszczędzić ok 25 % porównań, z tym, że w praktyce różnica w wydajności nie musi być duża (o ile w ogóle).

int main(){
    int n, nr, max1, poz1, max2, poz2;
    cin>>n>>nr;
    max1=nr; poz1=1;
    cin>>nr;
    max2=nr; poz2=2;
    for(int i=3; i<=n; i++){
            cin>>nr;
            if(nr>max1 && max1 < max2){
                       max1=nr;
                       poz1=i;
                       continue;
            }
            if(nr>max2){
                       max2=nr;
                       poz2=i;
            }
    }
    cout<<max1<<" "<<max2<<" "<<poz1<<" "<<poz2;
    return 0;
}  

muszę znaleźć dla ciągu dwa max wartości i ich pozycje. Ma ktoś własny lepszy pomysł na kod?

Jeśli dodatkowa pamięć ma być tak jak tutaj rzędu O(1) to raczej nie. Jeśli nie, to można zbić ilość porównań. Wystarczy zbudować drzewo turniejowe dla danych wejściowych (co wymaga n - 1 porównań). Maksimum będzie w korzeniu, a drugą w kolejności wartość będzie można znaleźć w log2 n porównaniach. W sumie będzie więc około n + log2 n porównań. Z tym, że takie rozwiązanie na pewno będzie dużo wolniejsze.

Wibowit nie znam się na złożonościach. Mógłbyś przedstawić swój sposób rozwiązania w C++? Dzięki.

Jeśli się nie znasz to znaczy, że ci to raczej niepotrzebne :) Twój kod jest wystarczająco zwięzły i szybki.

Dla znających tematykę, bezużyteczny (?) algorytm z minimalną ilością porównań:

• schodzimy wgłąb drzewa turniejowego w poszukiwaniu elementu maksymalnego, tzn element maksymalny jest w korzeniu, potem w jednym jego dziecku, potem którymś dziecku tego dziecka itp
• przy każdym schodzeniu wgłąb porównujemy dzieci aktualnego węzła - jedno dziecko zawiera element maksymalny, a drugie może zawierać element drugi w kolejności,
• schodząc w głąb liczymy maksimum z tego "drugiego" dziecka,
• owe maksimum z drugiego dziecka to element drugi w kolejności,

ja myślę że łatwiej przyspieszenie dostanie się używając printf/scanf zamiast cout/cin, niż przez niewielkie ograniczenie ilości porównań…

Głowie się nad takim dziwnym zadaniem:
W ciągu składającym się z n elementów znaleźć wartość i pozycje k-tego co do wielkości elementu tego ciągu.
Ma ktoś może pomysł jak to rozwiązać?

http://en.wikipedia.org/wiki/Selection_algorithm

Dzięki Wibowit!

Mam problem z pewną macierzą 5x5:
0 1 2 3 4
15 16 17 18 5
14 23 24 19 6
13 22 21 20 7
12 11 10 9 8

Mój kod:

int main(){
    int arry[5][5]; //wiersz x kolumna
    for(int i=0; i<5; i++)
            for(int j=0; j<5; j++)
                   if(!(i%2))
                    arry[i][j] = j;
                   else
                    arry[j][5-(i+1)/2)] = j+1+arry[i-1][4];

    for(int i=0; i<5; i++){
            cout<<endl;
            for(int j=0; j<5; j++)
                    cout<<arry[i][j]<<" ";
    }
    return 0;
}

Mógłby ktoś poprawić mój kod, już nie mam pomysłu.. :/ dziękuję