• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

szukanie kilku elementów najmniejszych

0 głosów
113 wizyt
pytanie zadane 10 października w C i C++ przez tomason Nowicjusz (140 p.)
#include <iostream> //test
using namespace std;

int main()
{
int tab[]={8,4,5,9,3,2,7};
int minimum, indeks=0;
//wyswietl rosnąco 3 najmniejsze wartosci z tablicy

for(int k=0;k<3;++k){
    for(int i=0;i<7;++i){
        if(minimum>tab[i])
        {
            minimum=tab[i];
            indeks =i;
        }
    }
    tab[indeks]=10;
    cout<<"minimum "<<minimum<<endl;
}
return 0;
}

pytanie: Jak znaleźć i wypisać na ekran 3 elementy najmniejsze

idea: znajduje element najmniejszy i zastępuje go jakimś dużym (spoza zakresu)

 

4 odpowiedzi

+2 głosów
odpowiedź 11 października przez Criss Mędrzec (150,380 p.)

idea: znajduje element najmniejszy i zastępuje go jakimś dużym (spoza zakresu)

Kompletnie nie rozumiem o co ci tutaj chodzi, więc to zignoruję w mojej odpowiedzi.

Jakbyś szukał najmniejszego elementu? Załóżmy, że na szukaną wartość tworzysz sobie zmienną `n`. Więc przypisujesz do `n` wartość zerowego indeksu i iterujesz po tablicy od pierwszego indeksu sprawdzając czy dany element jest mniejszy od `n`. Jeśli jest, to przypisujesz do `n` wartość tego elementu i przechodzisz do kolejnej iteracji.

Teraz zmodyfikujmy to troche dla trzech szukanych. Troche słabo, żebyśmy musieli przy każdej iteracji porównywać ze wszystkimi trzema dotychczas znalezionymi. Jak możemy to ominąć? Trzymajmy wynik (nasze 'n') w formie posortowanej. Malejąco dla wygody. Tworzymy sobie naszą tablice na wynik: n[3]. Do wszystkich indeksów wpisujemy na start wartość zerowego indeksu przeszukiwanej tablicy i zaczynamy iteracje od indeksu 1. Pamiętamy, że zakładamy nasze `n` jako posortowane malejąco. Więc porównujemy dany element z n[0]. Jeśli dany element jest większy (lub równy) od n[0], to z pewnością jest też wikszy (lub równy) od n[1] oraz n[2]. Jeśli jednak jest mniejszy od n[0], to porównujemy z n[1]. Jeśli jest większy od n[1], to przypisujemy wartość danego elementu do n[0], a jeśli okaże się mniejszy również od n[1], to porównujemy z n[2]. Jeśli jest większy od n[2], to przypisujemy wartość danego elementu do n[1], jeśli jednak jest większy, to przypisujemy wartość danego elementu do n[2]. Przechodzimy do kolejnej iteracji. Analogicznie sprawa wygląda dla dowolnej liczby szukanych najmniejszych, ale przy jakichś większych ilościach szukanych bardziej opłacałoby się pewnie sortować wynikową tablice (`n`) jakimś quicksortem przy każdej iteracji.

0 głosów
odpowiedź 10 października przez profesorek96 Nałogowiec (31,440 p.)
Ja bym tablice po sortował rosnąco i wypisał pierwsze 3 elementy. Sortować możesz np. za pomocą algorytmu sortowania bombelkowego.
komentarz 10 października przez tomason Nowicjusz (140 p.)
dzięki za odpowiedź, wiem że można posortować, ale zależy mi na przedstawionej metodzie
komentarz 10 października przez garris Użytkownik (610 p.)

Sprawdź w swoim programie wartość minimum przed wykonaniem pętli.

Aktualnie porównujesz zmienną, której wartości nie znasz. Jeżeli koniecznie chcesz to robić swoim sposobem to spróbuj zrobić pętle w ten sposób:

for(int k=0;k<3;k++){
    minimum=tab[0];
    for(int i=0;i<7;i++){
        if(minimum>tab[i])
        {
            minimum=tab[i];
            indeks=i;
        }
    }
    tab[indeks]=10;
    cout << minimum << endl;
}

Ale możesz rozwiązać ten problem wydajniejszymi sposobami

0 głosów
odpowiedź 10 października przez Sheida Użytkownik (950 p.)
chyba najlepiej bedzie jak uzyjesz sortowania babelkowego i wypisal 3 pierwsze liczby. Pan Miroslaw Zelent ma o tym odcinek w kursie c++.
komentarz 11 października przez Secrus Stary wyjadacz (12,940 p.)
Jesli juz sortowanie, to quicksort. Babelkowe o ile w tym przypadku byloby rownie dobre, to mimo wszystko jest mniej wydajne i raczej rzadko sie do uzywa
komentarz 12 października przez Sheida Użytkownik (950 p.)
Masz racje. Wydaje mi sie jednak ze jesli chodzi o latwosc algorytmow, to bubble sort jest tym prostrzym. Mimo to, warto znac oba.
0 głosów
odpowiedź 11 października przez mokrowski Szeryf (88,240 p.)

Zapewne odpowiesz że jeszcze tych kontenerów nie przerabiałeś, ale spróbujmy... 

Jeśli miałbyś rozwiązać problem a nie ćwiczyć rozwiązanie, użyłbyś std::nth_element z <algorithm>. 

#include <iostream> 
#include <algorithm>

int main() {
    int tab[]={8, 4, 5, 9, 3, 2, 7};
    for(auto i = 0; i < 3; ++i) {
        std::nth_element(std::begin(tab) + i, std::begin(tab) + i, std::end(tab));
        std::cout << "minimum = " << *(std::begin(tab) + i) << '\n';
    }
}

Właściwością tego rozwiązania jest modyfikacja kontenera pierwotnego.

Jeśli wymaganie było by postawione włącznie z "kontener pierwotny ma nie być zmieniony", potrzebował byś struktury która naturalnie zwróci elementy najmniejsze. Nadaje się do tego kolejka priorytetowa:

#include <iostream> 
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    int tab[] = {8, 4, 5, 9, 3, 2, 7};
    std::priority_queue<int, std::vector<int>, std::greater<int>> que;
    std::for_each(std::begin(tab), std::end(tab), [&que](int val) { que.push(val);});
    for(auto i = 0; i < 3; ++i) {
        std::cout << "minimum = " << que.top() << '\n';
        que.pop();
    }
}

Właściwością tego rozwiązania jest konieczność alokowania 2 kontenera (std::vector dla std::priority_queue) o wielkości pierwotnego. Oczywiście łatwo dodać jego zmniejszanie do wartości 3 w każdym zasileniu que przez push(...).

Jeśli żadne z powyższych rozwiązań, to tak naprawdę manualnie będziesz implementował kolejkę priorytetową graniczoną do 3 wartości.

komentarz 11 października przez tomason Nowicjusz (140 p.)
edycja 11 października przez tomason
dziękuje za tak liczne i merytoryczne odpowiedzi :) takie wyszukiwanie (3 najmniejszych elementów) jest częścią zadania (na uczelni) i ma pewne ograniczenia co do użytej pamięci (o czym wcześniej nie napisałem), stąd wyszukiwanie powinno odbywać się na bieżąco, tj. linijka po linijce, (wczytywanie całej tablicy przekracza dozwolony limit pamięci). Aha, można (jeszcze) korzystać z STL'a :)

zadanie przeszło pozytywnie przez sprawdzarkę :) Także, co ambitniejsi mogą spróbować zakodować przypadek dla wczytywania tablicy n-elementowej (i to w dodatku struktur) chociażby celem edukacji

Podobne pytania

+2 głosów
1 odpowiedź 117 wizyt
pytanie zadane 14 października w Sprzęt komputerowy przez program naczelny Obywatel (1,790 p.)
0 głosów
1 odpowiedź 59 wizyt
0 głosów
1 odpowiedź 76 wizyt
Porady nie od parady
Nie wiesz jak poprawnie zredagować pytanie lub pragniesz poznać którąś z funkcji forum? Odwiedź podstronę Pomoc (FAQ) dostępną w menu pod ikoną apteczki.FAQ

56,369 zapytań

101,067 odpowiedzi

208,200 komentarzy

28,040 pasjonatów

Przeglądających: 343
Pasjonatów: 12 Gości: 331

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...