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

• #10646 Jim-Y veterán

  Új Válasz 2017-01-30 11:27:06 #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.

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