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

• #97 dabadab titán DopeBob #95

  Új Válasz 2021-12-15 13:57:15 #97

  Ú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 DopeBob #95 üzenetére

  Szerintem a Dijkstra mehet az első helyre (szerintem van elég egyszerű ahhoz, hogy ne legyen értelme saját megoldáson töprengeni), a többi meg igazán nem is kell.

  Én egyébként nekiálltam tisztán brute force-szal (miszerint végigpróbálni az összes lehetséges útvonalat), de az már a példa 10x10-es mátrixával sem végzett azelőtt, hogy meguntam volna várni rá , aztán közbejött minden más, de most az ebéd utáni sziesztában nekiállok megcsinálni rendesen.

• #96 axioma veterán DopeBob #95

  Új Válasz 2021-12-15 13:04:41 #96

  Ú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

  

  axioma

  veterán

  válasz DopeBob #95 üzenetére

  En a mait buta modszerrel oldottam meg. Eredmenymatrix mindenki szumma all value, bal felso sarok 0. Amig van javitas, addig vegigmegyek minden cellan es akinek az eredmenye+adott szomszed kockazata kisebb, mint ami a szomszed eredmenye, ott a szomszedot felfrissitem a kisebbel, modositasjelzo on. Nyilvan output a jobb also sarok. Lehetne rengeteget optimalizalni (itt most konkretan ha nagyon akarod, dijkstra-zhatsz), de szerintem tok felesleges. Ez is lefut a nagyra is online ide-ben is par max. partiz masodperc alatt. Es kodsorban joval kevesebb (konkretan az elso 20 sor, pythonban).

  A temakorokhoz:
  A linked list szerintem ma mar eloben tok folosleges, ha valami nagyon beszuras-torles-heavy es gyors is kell legyen, akkor van a nyelvekben beepitett megoldas ra.
  A stack es queue kell, plusz kene a priority queue. Nem feltetlen kell sajat megvalositassal foglalkozni (pl. heap), csak a beepitetteket hasznalni.
  Fa talan, de pl. kiegyensulyozott keresofa tok folosleges...
  Tree traversal egyes esetekben lehet, de sztem ilyen verseny jellegu feladatnal meg interjun, a valo eletben ez szerintem ritkan jon elo. Legjellemzobb hogy a levelektol felfele tudod szamolni az adott tulajdonsagot, erdemes root node-bol feldolgozasi listat csinalni (ennek nem feltetlen kell valamelyik nevesitett bejarasnak lennie, persze jellemzoen azokat konnyebb programozni). Ha valami 20-50-nel tobb melysegi hivas lenne, en mar kerulnem a tiszta fuggvenyrekurziot.
  Heap: en egy esetben szoktam hasznalni, ha modositassal kell a priority queue, de sztem ez se fontos igazan, az elvet tudni nice to have.
  Graf es bejarasok: ez szokott kelleni, valami tokegyszeru objektumos tarolast erdemes a matrix helyere betenni (pl. id+e'lek listaja a tuloldali node id-vel), bejaras nyilvan kellhet, backtrack itt ugyis elojon. De egyebkent nyelvektol fugg, szokott lenni kesz graf, csak beparameterezed es tudsz tole pl. akar max. parositast is lekerdezni (ami tok altalanos esetben kezzel nem egy leanyalom).
  Dijkstra: akar. De lasd fent, nem tartom mindig szuksegesnek. Ha ordo-ssagot kell teljesiteni akkor persze nem art. Szerintem me'g az is lehet, hogy ez a mai megoldhato (most nem tudom kiprobalni) cska jobbra es le lepesekkel, akkor meg siman eleg egyszer vegigmenni a tombon (a balrabb es fentebb levo ertekek mar veglegesek), ilyen jellegu szerintem tobb volt.

  Azert tedd hozza hogy nem en vagyok az etalon, en tul sok eleve is feladvanynak keszult problemat oldok meg.

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