Jo estet Coderek!
Beleolvastam a listaba, nem tudtam eldonteni, hogy csak
bizonyos programnyelvekkel foglalkoztok, vagy programozasi
logikaval is. Mindenesetre nekem az utobbival van most
problemam, kozzeteszem, legfeljebb nem kapok ra valaszt.;)
Van egy szamomra eleg bonyolult feladat, keresem hozza a
legrovidebb utat jelento programozasi logikat.
Adott egy kor, amin veletlenszeruen kijelolunk n (min. 10) pontot,
majd ebbol az n pontbol veletlenszeruen kijelolunk k (max 4) pontot,
es veletlenszeruen kerul kivalasztasra a 4 pont kozul a kezdeti, es
attol kezdve a masik harom ponton keresztul eloall a koriv, aminel
a szakaszokat ismerem.
A feladat az, hogy ezt a korivet minel gyorsabban megtalalni a
korben, hogy mely pontokbol all es hol a kezdete.
pelda: (360 a kor osszege)
n=20
5, 12, 35, 56, 78, 123, 188, 234, 296, 312
k=4
296, 312, 35, 123 (296 a kezdete, ez lesz a 0 pont, azaz a
korivunk igy nez ki: 0, 16, 83, 88)
(tehat a kor (n) pontjait es a koriv (k-1) szakaszhosszait ismerem)
Ugyebar, ha szakaszban keresnek szakaszt, akkor egyszeru a
helyzet, az elso ponttol kezdve haladok addig, amig meg nem
talalom az elso resz-szakaszt es maris nyertem.
Veletlenszeru keresesnel az a gond, hogyan tudom tarolni,
hogy merre kerestem mar.
Eloszor kizarasos keresesre gondoltam, hogy megnezem a
szakasztavolsagokat, mert ugye a koriv egymas mellett
levo pontjai kozotti tavolsag mindig nagyobb vagy egyenlo a
teljes kor ket szomszedos pontjainak szakasztavolsaganal, de
ez csak akkor mukodik, ha sikerul kivalasztani a legrovidebb
egymas melletti szakaszt mind a koron mind a koriven, azaz,
ha 5-12 szakasz ki lenne valasztva, akkor rogton meg lenne
a megoldas. Igy azonban bizonytalan vagyok, mert ugye nem
lehet tudni, hogy melyik a kiindulopont, hogy hany pontbol all
a koriv keresett szakasza, azonban a 296-312 = 16 rogton
kiadja a megoldast - csak odaig el kell jutni.
Meg arra gondoltam, hogy a koriv minden szakaszat kiszamitom
es sorba rakom, es amikor elindulok a koron a szakaszokat
keresve, akkor nagysag szerint mindig elvetem.
(5-12, 5-35, ... 5-188 ...)
a masik megoldas visszafele mukodne, azaz a szakaszok
hosszai alapjan probalom beazonositani, hogy van-e esely arra,
hogy ket szomszedos pont kozott van (ekkor rogton fennall az
egyenloseg)
Szerintetek milyen elv szerint kellene megkeresni a megoldast,
mi a legrovidebb utja?
elek
|
