Sziasztok!
(Most vagyok először az Asztalnál, de ez a topic nagyon rulez, úgyhogy gyorsan regisztráltattam magam, remélem nem bánjátok.)
N e t S h a r k:
Nagyon király ez a láncolt listás feladat. Furcsa, de valamire nagyon emlékeztet, de nem tudok rájönni mire (valami tétel bizonyítás ? nemtom...), ilyen formában viszont még nem találkoztam vele.
IMHO a megoldás: Tfh. minden listaelemnek van egy sorszáma, amely egy pozitív egész szám. Ezenkívül ne legyen "kihagyás", azaz ha pl. N elem van, akkor 1-től N-ig minden szám legyen kiosztva sorszámnak.
Ezután sétálgassunk szépen a listában, és jegyezzük meg, hogy hány elemet láttunk, és hogy mi volt a látott sorszámok maximuma.
Namármost, ha bármikor a látott elemek száma nagyobb, mint a sorszámmaximum(sic!), akkor van hurok, egyébként nincs (ha tényleg végtelen a lista, akkor utóbbi esetben sose lesz vége, vagyis ez egy parciálisan eldönthető probléma) a hurkolódás helyét viszont sajna nem tudjuk megmondani.
Erre gondoltál?
Az is igaz viszont, hogy szigorúan véve ehhez nem konstans, hanem N-től függő nagyságú memcsi kell, ha jól érzem, akkor O(log(N)), a szokásos architektúrákon.
maya |