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

szukanie kilku elementów najmniejszych

VPS Starter Arubacloud
0 głosów
655 wizyt
pytanie zadane 10 października 2018 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 2018 przez criss Mędrzec (172,590 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 2018 przez profesorek96 Szeryf (91,420 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 2018 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 2018 przez garris Użytkownik (660 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 2018 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 2018 przez Secrus Nałogowiec (32,880 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 2018 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 2018 przez mokrowski Mędrzec (155,460 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 2018 przez tomason Nowicjusz (140 p.)
edycja 11 października 2018 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

0 głosów
2 odpowiedzi 296 wizyt
pytanie zadane 12 lutego 2019 w C# przez gameone Nowicjusz (230 p.)
0 głosów
2 odpowiedzi 116 wizyt
pytanie zadane 16 maja 2023 w HTML i CSS przez niezalogowany
0 głosów
2 odpowiedzi 77 wizyt
pytanie zadane 26 kwietnia 2023 w JavaScript przez zbiku25 Bywalec (2,940 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...