Keresés

Részletes keresés

N e t S h a r k Creative Commons License 1999-03-05 22:01:38 227
Nem erre gondoltam. Azon meg gondolkodom, hogy egyaltalan jo-e. De nem hiszem, mert pl. az a kiteteled, hogy
"ha pl. N elem van, akkor 1-től N-ig minden szám legyen kiosztva sorszámnak."
Csak ugy teljesitheto minden N-re, ha pontosan sorban vannak sorszamozva 1-tol. Nem jol gondolom? Ugy meg ugye konnyu lenne.
A hozzászólás:
maya Creative Commons License 1999-03-05 19:28:23 218
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

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!