Program wskazujący 5 element co do wilkości w tablicy

Odpowiedz Nowy wątek
2018-11-03 20:29
0

Witam, mam napisać program, który wskaże 5 co do wielkości element w tabeli. Użytkownik wpisuje liczby naturalne zakończone zerem , który stanowi tylko i wyłącznie znacznik końca danych. Można założyć że użytkownik podał przynajmniej 5 lioczb naturalnych i zakończył wpisywanie 0. Czyli dla np danych wejściowych: 3 5 4 1 2 0 pogram powinien zwrócić wartość 5. Nie chce sortować całej tabeli tylko potrzebny mi jest szybszy sposób tylko nie mam pomysłu za bardzo.

edytowany 2x, ostatnio: furious programming, 2018-11-03 20:55
Na forum dla programistów tag programowanie jest lekką redundancją, nieprawdaż? - furious programming 2018-11-03 20:54

Pozostało 580 znaków

2018-11-03 20:51
kq
2

std::nth_element


Pozostało 580 znaków

2018-11-03 20:53
0

Okej, ale mam napisać algorytm, a nie korzystać z gotowych funkcji czy bibliotek.

edytowany 1x, ostatnio: kaktus123, 2018-11-03 20:53

Pozostało 580 znaków

2018-11-03 20:55
kq
0

No to dla piątego elementu po prostu utworzyłbym sobie tablicę tymczasową do przetrzymywania pięciu największych i po przejechaniu całego zestawu wybrał najmniejszą liczbę z tej tablicy.


Pozostało 580 znaków

2018-11-03 20:56
0

A pomógłbyś mi napisać algorytm? Bo jestem całkiem zielony w tym i nie mam pomysłu na to.

edytowany 1x, ostatnio: kaktus123, 2018-11-03 20:56

Pozostało 580 znaków

2018-11-03 20:57
2

Napisz sobie max Heap. Zbudujesz go z tablicy arr[n]w czasie O(n) i Wyciągasz z niego piąty element - sumarycznie złożoność O(n).


Pozostało 580 znaków

2018-11-03 20:59
1
kaktus123 napisał(a):

Witam, mam napisać program, który wskaże 5 co do wielkości element w tabeli.

Nie w tabeli, a w tablicy – tabele to elementy baz danych lub widoku witryny.

Bez sortowania tablicy? Hmm… Możesz sobie zadeklarować tablicę na pięć elementów o najwyższej wartości i podczas iteracji po wszystkich pobranych z klawiatury liczbach dodawać do niej bieżący, jeśli jest wikęszy od któregoś elementu. Aby dodać nowy element do takiej tablicy, trzeba będzie napisać sobie kod, który najpierw znajdzie dla niego odpowiednie miejsce, przesunie elementy (kasując ten o najmniejszej wartości) i wpisze bieżący. Sporo zachodu.


edytowany 1x, ostatnio: furious programming, 2018-11-03 21:00

Pozostało 580 znaków

2018-11-03 21:00
kq
3

Pewnie.

  1. TablicaMax ⟵ WczytajPierwszePięć()
  2. N ⟵ WczytajLiczbę()
    • jeśli N = 0, idź do kroku 3.
    • dodaj N do TablicaMax
    • posortuj TablicaMax
    • usuń najmniejszą liczbę z TablicaMax
    • idź do kroku 2.
  3. Wypisz najmniejszą liczbę z TablicaMax

To będzie na pewno nie gorsze niż O(n)? - lion137 2018-11-03 21:09
Sortowanie 5 elementów można uznać za stałą ;​) Ogółem Twoje rozwiązanie wygląda mi znacznie lepiej, ale to jest trywialne do zaimplementowania dla świeżaka. - kq 2018-11-03 21:10
Kroki dodaj N do TablicaMax i posortuj TablicaMax można scalic w jeden - Sortowanie przez wstawianie. - vpiotr 2018-11-04 10:40

Pozostało 580 znaków

2018-11-03 21:07
0

Okej rozumiem, i teraz pytanie czy lepiej sortować jest na początku całą tablicę np bąbelkowo i wypisać 10 element tabeli czy zrobić sobie tablicę 5-elementową i sortować ją za każdym razem jeśli dodaję do niej element mniejszy od największego w niej?

Pozostało 580 znaków

2018-11-03 21:13
0

Jeśli możesz skorzystać z sortowania to posortuj sobie od razu tablicę liczb wczytanych z klawiatury. Wtedy żadna inna tablica nie będzie Ci potrzebna i cały kod drastycznie się uprości.


edytowany 1x, ostatnio: furious programming, 2018-11-03 21:13
Okej, ale mam napisać algorytm, a nie korzystać z gotowych funkcji czy bibliotek. strzelam, że nie. - kq 2018-11-03 21:14
To zdanie nie wyklucza własnej implementacji funkcji sortującej. ;) - furious programming 2018-11-03 21:15

Pozostało 580 znaków

2018-11-03 21:15
kq

W sumie dobrze napisany bubblesort dla tablicy kilkuelementowej jest całkiem sensownym rozwiązaniem. Dla całej tablicy może okazać się zabójczy, bo to ogółem beznadziejny algorytm sortowania jest.


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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