2. Fórumok
  3. Szoftverfejlesztés
  4. Programozás topic
  5. (kiemelt téma)

Hirdetés

  • Letartóztatták a bitcoin-Jézust

    it Amerikai adókerülés vádjával, Spanyolországban tartóztatták le a bitcoin-Jézusként ismert Roger Vert.

  • Mindent megtudtunk az új Nokia 3210-ről

    ma Részletes képek, specifikációk és euróban megadott ár is van a legendás modell újraélesztett verziójához.

  • Lunar Lander Beyond teszt

    gp Nagyon sok évtizeddel az eredeti Lunar Lander megjelenése óta ismét ezen a címen jelent meg Atari logóval egy játék. Vajon mennyit javult a játékdesign a hetvenes évek óta?

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

  • #10646 Jim-Y veterán
    Új Válasz #10646
    Ú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

    Jim-Y

    veterán

    Sziasztok, egy egyszerű algoritmust kell implementálnom és érdekelne hogy van-e nagyságrendekkel jobb futásidejű megoldás mint amire gondoltam.

    Feladat: vannak időben egymást követő események, A,B,C stb.. össze kell számolnom, hogy ezek közül melyek azok amik "futottak" majd átadták a futást, majd újból "futottak". Pl AABABCCD, ennek az eredménye az kell, hogy legyen, hogy A: igen, B: igen, C: nem, D: nem. Nem kell összeszámolni hogy sorozaton belül hányszor "mondtak" le a futásról majd megint futottak a lényeg, hogy egyszer lemondtak majd megint futottak. Remélem érthető.

    Amit kitaláltam: Egyszer végigmenni a soron, illetve csinálni egy táblát ({ A: -, B: -, C: -, D - }) amibe gyűjtöm, hogy a bizonyos node-ok milyen állapotba kerültek a következő állapotokkal:

    0: futott
    1: lemondott a futásról
    2: újra futott

    Tehát szimulálva az algoritmust erre a sorra AABABCCD

    1) A
    { A: 0, B: -, C: -, D - }

    2) A
    { A: 0->0, B: -, C: -, D - }

    3) B
    { A: 0->0->1, B: 0, C: -, D - }

    4) A
    { A: 0->0->1->2, B: 0->1, C: -, D - }

    5) B
    { A: 0->0->1->2, B: 0->1->2, C: -, D - }

    6) C
    { A: 0->0->1->2, B: 0->1->2, C: 0, D - }

    7) C
    { A: 0->0->1->2, B: 0->1->2, C: 0->0, D - }

    8) D
    { A: 0->0->1->2, B: 0->1->2, C: 0->0->1, D: 0 }

    És a végén megézem a táblában, hogy melyiknél van 2-es. Ez így O(n) futásidejű + a táblában a változtatások nem tudom, hogy ennél van-e jobb megoldás. Az implementálása ennek meg egyszerű.

    Üdv és köszi

    megj: ha valaki nagyon belejött, vagy ha az összkép segít egy hatékony(abb) algoritmus kitalálásában, akkor AABABCCD szerű sorból nem csak egy van, hanem N, és a feladatom, hogy minden A,B,C stb node-ra összesítve kiszámoljam hogy az N darab sorban hányszor "mondtak le a futásról". Nyílván így már a nagy algoritmus O(n*m)-es lesz de nem hiszem, hogy ezt meg lehetne úszni.

    [ Szerkesztve ]

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