2. Fórumok
  3. Szoftverfejlesztés
  4. C++ programozás
Keresés

Új hozzászólás Aktív témák

  • #4245 mgoogyi senior tag Ron Swanson #4243
    Új Válasz #4245
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    mgoogyi

    senior tag

    válasz Ron Swanson #4243 üzenetére

    A mohó mintáshoz hasonló lesz a megoldás, sokat segített volna, ha az elején ismerem már azt a példafeladatot.
    Annak a pdf-je többet mond, mint a kódja.
    Szerintem távozási idő szerint kell rendezni a vendégeket, venni az elsőt és mindenki, akivel ő találkozik, azzal nem kell foglalkozni, mert az nem lehet jobb nála. Ez a halmaz kiesik és ugyanezt ismételni, amíg el nem fogynak a vendégek.

    Egyébként neked az alapokat kéne rendberakni, nem algoritmusokon görcsölni.
    Majd nekifutok még1x, ha lesz kedvem.

  • #4244 Zalanius tag Ron Swanson #4243
    Új Válasz #4244
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    Zalanius

    tag

    válasz Ron Swanson #4243 üzenetére

    Az én olvasatomban bármi, amiben van sort() az időpontokra, az legfeljebb olyasmire lesz jó, hogy mikor voltak a legkevesebben, de sok fontos info elveszik. A feladat meg nagyon nem erről szól, egy egyszerű "házigazda" példával könnyen megmutatható:

    1 3
    1 3
    1 3
    1 8
    5 8
    5 8

    Nyilván nem az a megoldás, hogy ki volt bent mondjuk 4-nél (a "házigazda" egyedül, de ő meg pont nem a megfejtés). Az meg már a múltkor is első olvasatra feltűnt a már törölt hozzászólásokban, hogy az 1 millió vendég és a 100 ezer időegység azért van a feltételek között, hogy kizárjon minden O(n^2)+ vagy teljes mátrixos próbálkozást.

  • #4203 kobe24 tag Ron Swanson #4202
    Új Válasz #4203
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    kobe24

    tag

    válasz Ron Swanson #4202 üzenetére

    for(int i = 0; i < varosDb; i++){
    for(int j = 0; j < napDb; j++){
    if (homerseklet[i][j] == maxHomerseklet[j]){
    hanyszorVanHely[j] = i + 1;
    hanyszorVan[i]++;
    }
    }
    }

    Ebben a ciklusban van a hiba, hiszen itt a "hanyszorVanHely" tömmben minden egyes alkalommal felülírod a tömb elemeit az aktuális sorral. Gyakorlatilag erre a változóra nincs is szükség. Tehát ha ezt a ciklust kijavítod

    for (int i = 0; i < varosDb; i++) {
    for (int j = 0; j < napDb; j++) {
    if (homerseklet[i][j] == maxHomerseklet[j]) {
    hanyszorVan[i]++;
    }
    }
    }

    erre, akkor megkapod, hogy az egyes városokban hányszor volt meg a napi maximum. Az utolsó ciklust kell már csak módosítani.

    for (int i = 0; i < varosDb; i++) {
    if (hanyszorVan[i] == hanyszorVanMax) {
    cout << i+1 << " ";
    }
    }

    A "hanyszorVan" tömb elemei megegyeznek azzal, hogy az adott indexű városban hányszor fordult elő a napi maximum. Így még egy tömböt meg is spóroltunk :)

  • #4175 mgoogyi senior tag Ron Swanson #4174
    Új Válasz #4175
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    mgoogyi

    senior tag

    válasz Ron Swanson #4174 üzenetére

    Rendezésből a buborékrendezést szokták elsőnek tanítani, de az O(n^2)-es, nem leszel vele előrébb.
    Ez a sort(...) gyorsrendezést használ, nyugodtan használd.
    A feladat megoldását meg nem tanultad órán, azt magadnak kéne kitalálnod, ezzel fejlődsz.
    Értsd meg a beszúrt kódot, próbálgasd. Ha azt érted az utolsó betűig, meg tudod majd oldani a saját feladatod is.

  • #4173 mgoogyi senior tag Ron Swanson #4172
    Új Válasz #4173
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    mgoogyi

    senior tag

    válasz Ron Swanson #4172 üzenetére

    Melyik része nem sikerül?
    A megértés?

    Amit linkelt Drizzt fórumtárs, az pont ezt oldja meg:

    #include<iostream>
    #include<algorithm>
    using namespace std;

    void findMaxGuests(int arrl[], int exit[], int n)
    {
    // Sort arrival and exit arrays
    sort(arrl, arrl+n);
    sort(exit, exit+n);

    // guests_in indicates number of guests at a time
    int guests_in = 1, max_guests = 1, time = arrl[0];
    int i = 1, j = 0;

    // Similar to merge in merge sort to process
    // all events in sorted order
    while (i < n && j < n)
    {
    // If next event in sorted order is arrival,
    // increment count of guests
    if (arrl[i] <= exit[j])
    {
    guests_in++;

    // Update max_guests if needed
    if (guests_in > max_guests)
    {
    max_guests = guests_in;
    time = arrl[i];
    }
    i++; //increment index of arrival array
    }
    else // If event is exit, decrement count
    { // of guests.
    guests_in--;
    j++;
    }
    }

    cout << "Maximum Number of Guests = " << max_guests
    << " at time " << time;
    }

    Az int arrl[] az érkezési időpontok tömbje, a int exit[] pedig a távozási időpontok tömbbje.

    Ez rendezi le neked ezt a két tömböt gyorsrendezéssel O(N*logN) időben:

    sort(arrl, arrl+n);
    sort(exit, exit+n);

    A while ciklus pedig végigmegy a két tömbbön úgy, hogy hol az egyiket lépteti, hol a másikat.
    Az"i" az érkezés indexe, a "j" a távozásé.

    Annyi, hogy ennek a programnak a kimenete az, hogy melyik időpontban voltak a legtöbben és nem az, hogy melyik vendég találkozott a legtöbb másikkal, de a két probléma technikailag szinte azonos.

    Ha valami nem világos, kérdezz.
    Az eredeti kódoddal a legfőbb baj, hogy volt benne egy egymásba ágyazott for ciklus pár, ami N darab vendég esetén N*N-nel arányos mennyiségű műveletet végez. Ezt hívják O(n^2)-nek és emiatt van az, hogy nagy N-re már túl sok ideig fut a programod. Ugye N=10-nél a a valahány 100 művelet nem gáz, de N=1000-nél már valahány millióról beszélünk.

  • #4172 Ron Swanson senior tag Ron Swanson #4171
    Új Válasz #4172
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    Ron Swanson

    senior tag

    válasz Ron Swanson #4171 üzenetére

    Próbálkozom, de nem sikerül :(
    Vasárnapig meg kéne csinálnom, addig kell beadni.

  • #4168 dabadab titán Ron Swanson #4165
    Új Válasz #4168
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    dabadab

    titán

    válasz Ron Swanson #4165 üzenetére

    "Kis mennyiségű adatnál szépen le is fut, de ha mondjuk N = több ezer, akkor nem fut le 0,2s alatt... :("

    Ó, hát erre egyszerű a megoldás, a lista tetejéről válassz valamit: [link] :D

    Komolyabbra fordítva a szót, az a gondod, hogy kb. a vendégek számának négyzetével nő az elvégzendő számítások mennyisége. A megoldás az, ha találsz ennél kisebb ordójú algoritmust. Első blikkre ilyen lehet az, ha a vendégeket nem direktben hasonlítod össze egymással, hanem az időintervallummal machinálsz.

    Például csinálsz egy listát, amiben olyan elemek vannak, amik állnak egy időpontból, a már ott lévő vendégek számából és az abban az időpillanatban érkezett vendégek számából és simán ezen a listán mész végig minden egyes vendégre.

    Ez egyébként továbbra is algoritmikus kérdés, nem C++ - specifikus.

    Hogy ontopic legyek, a C++ kódod valami egészen rettenetes és elavult, szóval fogadni mernék, hogy ezt a magyar (felső)oktatás keretében tanultad :DDD, szerintem azt is érdemes jobb átnézni:

    1. TVendegek:
    Minek az a T? Most komolyan? Mitől lesz bárkinek is jobb attól, hogy az összes osztály neve T-vel kezdődik, mint "type" (sőt, "típus"). Szóval legyen inkább Vendegek.
    Miért Vendegek? Egyetlen vendég adatait tárolja, nem többét, szóval legyen inkább Vendeg.
    És persze kódot szigorúan angolul írunk, szóval a végleges változat az a Guest.

    2. erkezes / tavozas
    Ha már név: itt pont van értelme annak, hogy jelöljük, hogy ezek adattagok, szóval m_arrive, m_leave
    Adattagokat csak kivételes esetben érdemes kirakni publikba, ez meg semmiképpen sem az, szóval legyenek csak private-ok (és a private tagokat érdemes a publicok mögé rakni, mert így jobban olvasható a kód: az elején ott van a mindenkit érdeklő rész, a class API-ja, az implementáció meg elfér hátul).

    3. TVendegek(const int E, const int T):
    A constok itt elég feleslegesek (érték szerit átadott primitívekről van szó), a nevek meg lehetnek nyugodtan beszédesek, a C++-ban a scope-ok miatt az is tök jól működik, hogy
    C::C(int x) : x(x) {}
    De mivel a tagok neve pont az előbb kapott egy m_ előtagot, amúgy se lenne névütközés legyen inkább
    Guest(int arrive, int leave)

    ....

    és most mennem kell, majd folytatom, addig a többiek úgyis belekötnek abba, amit írtam :D

  • #4167 Drizzt nagyúr Ron Swanson #4165
    Új Válasz #4167
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    Drizzt

    nagyúr

    válasz Ron Swanson #4165 üzenetére

    Szerintem itt van az idealis megoldas, a 3 kozul a kozepso. De elkepzelhetonek tartom teljesen mas megkozelitesek is hasonloan gyorsak lehetnek. [link]
    A te megoldasod o(n2) - nek nez ki.

  • #4166 mgoogyi senior tag Ron Swanson #4165
    Új Válasz #4166
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    mgoogyi

    senior tag

    válasz Ron Swanson #4165 üzenetére

    Pontos feladatleírás?

    for (i = 1; i < vendegek.size(); i++) {
    Itt 0-tól kéne indulni, az első vendég is lehet a megoldás.
    A TVendegek osztályt átnevezném Vendeg-re, mert az egy darab vendég szerintem.

    A feltöltésnél add át a vektornak a ctor-ba a méretét, hogy a push_back-nél elkerüld az átméretezést.
    Ha kevés benne a hely, újrafoglal magának helyet és másolgat. De várhatóan nem ezen múlik.

    A kódodnál viszont valszeg a dupla for ciklusnál lehet fogni sokat, az teszi négyzetessé a futási idejét a bemenet méretétől függően. Ez a feladat gyakorlatilag annyi, hogy melyik zárt intervallumnak van a legtöbb metszete a többivel.
    Én valami olyasmit csinálnák, hogy rendezném a vendégeket érkezési sorrendben (/távozásiban ) és végigmennék rajtuk lineárisan és jegyezném, hogy most jött valaki, most elment, és azt nézném, hogy mikor voltak a legtöbben.
    Oké, most esestt le. Nem kell a vendégeket rendezni, külön az érkezési idejüket egy tömbbe teszed, külön a távozásit és párhuzamosan haladsz a kettőn két külön indexszel. Ha a soron követő két szám között az érkezési <=, akkor növelsz a számlálón, ha meg nem, akkor csökkentesz. Ennek a számlálónak a maximumát keresed és egy vendéget, aki akkor ott volt.
    Ez már elég erős tipp szerintem. Lényeg, hogy az egymásba ágyazott ciklusokkal nem fogod tudod megoldani elég gyorsan, csak lineárisan mehetsz végig a vendégek dolgain.

  • #4164 EQMontoya veterán Ron Swanson #4163
    Új Válasz #4164
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    EQMontoya

    veterán

    válasz Ron Swanson #4163 üzenetére

    Neked nem c++ kerdesed van, hanem algoritmikai, adatszerkezeti,

    Eloszor is gondolkozz. :)

    Tarolnod kellene valahol az orhelyeket. Mondjuk tombben, mert azt tudod indexelni.
    Tehat beolvasol egy orseget (ami egy szam), azzal indexeled a tombot, igy oda be tudsz rakni egy orseget.

    Neked nem a sorszam[I]-be kell beolvasnod, hanem beolvasol egy intbe, es azzal indexeled a tombot.

    Utana meg kell talalnod, hogy hogyan lehet optimalisan lefedni az egeszet. Ehhez gondolkodni kell kicsit, de gondolkodni nem fogunk helyetted, a c++ reszeben segitunk szivesen.

Új hozzászólás Aktív témák

Hirdetés