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

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

Rejestracja: 2 lata temu

Ostatnio: 10 miesięcy temu

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

kq
2018-11-03 20:51
kq
Moderator C/C++

Rejestracja: 7 lat temu

Ostatnio: 57 sekund temu

Lokalizacja: Szczecin

2

std::nth_element


Pozostało 580 znaków

2018-11-03 20:53

Rejestracja: 2 lata temu

Ostatnio: 10 miesięcy temu

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

kq
2018-11-03 20:55
kq
Moderator C/C++

Rejestracja: 7 lat temu

Ostatnio: 57 sekund temu

Lokalizacja: Szczecin

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

Rejestracja: 2 lata temu

Ostatnio: 10 miesięcy temu

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

Rejestracja: 3 lata temu

Ostatnio: 1 minuta temu

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
Moderator Delphi/Pascal

Rejestracja: 8 lat temu

Ostatnio: 1 minuta temu

Lokalizacja: Tuchów

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

kq
2018-11-03 21:00
kq
Moderator C/C++

Rejestracja: 7 lat temu

Ostatnio: 57 sekund temu

Lokalizacja: Szczecin

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

Rejestracja: 2 lata temu

Ostatnio: 10 miesięcy temu

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
Moderator Delphi/Pascal

Rejestracja: 8 lat temu

Ostatnio: 1 minuta temu

Lokalizacja: Tuchów

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

kq
2018-11-03 21:15
kq
Moderator C/C++

Rejestracja: 7 lat temu

Ostatnio: 57 sekund temu

Lokalizacja: Szczecin

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

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