Keresés

Részletes keresés

wice Creative Commons License 1999-03-08 15:29:04 424
nemtom, emlekeztek-e meg maya feladvanyara. tudjatok, amit egy szamtech ceg szokott feladni munka utan kuncsorgoknak. (btw, a hurkos-pointeres is egy ilyen cucc.)

na, akkor en most megoldom, annal is inkabb, mert penteken adta fel, es ha jol emlexem, erre ket nap gondolkodasi idot ad az a bizonyos ceg (igen, en is palyaztam, es vissza is hivtak, csak addigra mar volt allasom... :-)), szal, most mar nem juttatom mayat tisztessegtelen elonyhoz. akik esetleg csak ezutan palyaznak... nos, megerdemli az a ceg, amelyik fel ev alatt sem bir uj tesztkerdest kitalalni. sok szerencset!

tehat, emlekeztetoul:
van egy file, amely ismeretlen szamu, max N hosszusagu rekordokbol all, minden rekordot egy 0 erteku byte zar le. hogyan valaszthato ki (= toltheto be a memoriaba) a filebol egy rekord veletlenszeruen ugy, h minden rekordnak egyenlo eselye legyen. csak N byte-nyi memoria hasznalhato. (+ nyilvan meg annyi, amennyiben a program elfer, de ez konstans.)

nos:
1. a file byte-okban megadott hosszaval generalni kell egy veletlenszamot,

2a. ha a veletlenszam erteke 0: beolvasunk N byte-ot a 0-dik poziciotol. a memoriaban ekkor benne lesz a rekord 0-val lezarva, utana esetleg vmi maszat.

2b. ha a veletlenszam erteke egyenlo a filehosszal: goto 1.

2c. ha a veletlenszam erteke nem = 0: az annak megfelelo poziciobol kiolvasni 1 byte-ot.

3a. ha a byte erteke 0: az utana kovetkezo N byte-ot beolvassuk a memoriaba, es voila'.

3b. ha a byte erteke nem 0: goto 1.

attol ilyen bonya az egesz, mert nem szabad segedvaltozot hasznalni. meg viccesebb volt, h ezt nekem teljes komolysaggal meg kellett irni c-ben. ekkor meg bejonnek pl ilyenek is, h a random(int a) fuggveny short int-et ad vissza, a filepozicio pedig long int. mindezt segedvaltozo nelkul. kerem, lehet probalkozni, van megoldas... ja, es csak nem ilyen szep ez az egesz, mert ahhoz, h olvashass egy file-bol, c-ben minimum kell egy filehandle. jo, monnyuk az is konstans, belefer.

ejnye, bocs, h ennyire elmentunk programozoba, ez vegulis egy logika topik. hat, legyen:

van harom kapu, ezek kozul ketto a pokolba vezet, egy a mennyorszagba. a kapukat egy torpe orzi, akirol tudjuk, h egyszer hazudik, egyszer igazat mond, felvaltva. egy kerdest tehetsz fel neki, amibol meg kell tudnod, h merre menj tovabb (visszafordulni nem lehet :-))

vegulis nem tul nehez, de sajat termes, ugyhogy buszke vagyok ra...

ja, cowboyos feladat nagyon spiral volt, koszi. persze en is megoldottam, nem mintha, csak ugy mondom :-)

ja2, nem lehetetlen, h az infos kivegzos feladatnak akkor is van vmi 50%-nal jobb megoldasa, ha feltetelezzuk, h az infosok mind hiperoptimalisan gondolkoznak, es ezt tudjak is egymasrol. ugye a hiperoptimalis megoldas a paritasbites, a kerdes csak az, h az elso nehany bemondasbol (es abbol, h kivegzik-e a bemondokat), a tobbiek rajohetnek-e, h mit jelent a "fekete" es a "feher" bemondas, kialakulhat-e vmi konszenzus, ami a tobbieket megmenti. ehhez faradt vagyok kicsit, de ha vkit erdekel, lehet gondolkozni.

na, momentan ennyi, tsok.

Lasley Creative Commons License 1999-03-05 21:26:34 225
OnOFF

Kedves Maya!

Nagyon gyanús vagy Te nekem!
Ugye ez nem a "házi feladatod"?
Ugyanis pont ezt a feladatot kapta egy haverom a napokban egy bizonyos cégtol, ahova jelentkezett, "szintfelméro" feladatnak.
EndOFF

A hozzászólás:
maya Creative Commons License 1999-03-05 19:41:19 221
Na akkor legyen egy feladat is...infósoknak...bocs.:-)
*** Van egy fájlod, melyben változó hosszúságú rekordok vannak. A rekord-elválasztó ismert, pl. legyenek benne null-terminált stringek.
Feladat: ki kell választani véletlenszerűen egyet a rekordok közül, úgy hogy mindegyiknek azonos legyen az esélye.
Megszorítások: Csak akkora memóriát használhatsz amelybe garantáltan belefér bármelyik rekord, de több nem, plusz még konstans méretűt. Vagyis adott a max rekordméret (pl. N), a használható memcsi: N+O(1)

Remélem elég precíz voltam :)
Ja, lehetőleg optimális megoldásokkal bombázzatok... :))))
(A filéből való olvasás nagyon-nagyon drága művelet)

Maya

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