Matematika feladatok
-
#933
akkor fogalmazzuk meg a problémát!
szóval van n darab egyenes, az a kérdés, hogy az egységsikátorban mely egyenesek vesznek részt a felső burkológörbe kialakításában.
az egyeneseket az egységsikátorba eső szakaszaik sikátorfallal való metszéspontjaival jellemezzük.
konkrétan legyen a bal legfelső metszéspont az a1, alatta a2, a3, stb...
legyen az a1-hez tartozó egyenes az e1, az a2-höz az e2, az a3-hoz az e3, stb.
tekintsük a sikátor falait y irányúnak, így a magasságok (a(i) és b(i) tulajdonképpen y koordináták)
legyen az e1 egyenes másik végpontja a b1, az e2-é a b2, az e3-é b3, stb...
az egyenesek egymással való metszéspontjait kiszámítani nem ér.
ha egy e(i) egyenes része a burkolónak, akkor f(i):=1, ha nem, akkor f(i):=0
úgy kezdeném, hogy minden f(i) értékét -1 re állítanék, hogy tudjam, róla még nem dőlt el, alkot-e, vagy se. for ciklusban értékadás
aztán az e egyenesek halmazából kivenném azokat, akik tutira nem alkotják.
mégpedig az alábbi két algoritmust alkalmazva:
1: távolítsuk el a halmazból azokat, akik az egységsikátoron belül végig egy másik egyenes alatt (pontosabban végig nem felette) haladnak.
ezek konkrétan azok, akikre igaz, hogy b(i)>=b(j) és i<j.
for ciklusban(1-től, i-re, n-ig) for ciklus (i-től, j-re, n-ig), bennük feltételvizsgálat, ha igaz, akkor értékadás f(j):=0
2: távolítsuk el azokat, akik valamelyik másik két egyenes burkológörbéje alatt (pontosabban végig nem felette) futnak a sikátorban.
legyen a vizsgálandó egyenes e(i), a másik kettő e(j) és e(k),
ahol j<k (vagyis a a(j)>a(k), azaz a bal oldalon e(j) magasabban van mint e(k))
és b(k)>b(j) (vagyis a jobb oldalon e(k) van magasabban mint e(j))
(így e(j) és e(k) már metszik egymást)
és j<=i<=k (vagyis a(j)<a(i)<a(k), azaz a bal oldalon e(i) e(j) alatt, de e(k)f elett van)
és b(j)<=b(i)<=b(k) (vagyis a jobb oldalon e(k) és e(j) közé esik e(i).
ekkor tehát a 3 egyene 3 pontban metszi egymást, de még el kell döntenünk, hogy a vizsgált e(i) a másik kettő burkológörbéje alatt fut-e végig.
ez akkor* van, ha
a(j)-a(i)>=b(k)-b(i).
tehát ha a fenti feltételek igazak, akkor a vizsgált egyenes is kiejthető.
három egymásba ágyazott forciklus belül feltételvizsgálat, ha igaz, akkor értékadás f(i)=0
a két algoritmusocskát (szubrutint) alkalmazva előbb utóbb minden egyenesnél f(i)=1, vagy f(i)=0 lesz, és akkor készen vagyunk.
azt hogy a két szubrutint felváltva, vagy az egyiket (konkrétan a másodikat) gyakrabban alkalmazva kell-e eljárni, vagy hogy az elsőt esetleg elég egyszer lefuttatni, azt nem tudom.
de a két algoritmus összevonható eggyé, csak az az érzésem, hogy nagyob ortó költségű lesz.
ha már költség, akkor nyilván jó lenne a egy többszörösen láncolt lista is, melyben csak a még nem kizárt egyeneseket tartjuk a(i) és b(i)szerint is láncolva, de erre már télleg nincs időm!
*ebbe csak azért nem vagyok biztos, mert nem bizonyítottuk azóta se
lehet hogy kéne még oda az "és a(i)-a(k)<=b(i)-b(j)" ... egyre bizonytalanabb vagyok... lehet, hogy a meredekségük (a(i)-b(i)) és az bal metszéspontok alapján burkoltan kiszámítva a metszéspontot jobban járnánk, mert nem kell konkrétan a metszéspont, csak az, hogy fölötte van-e a ... na mindegy.
amit leírtam nem olvastam át, úgyhogy elgépelés, vagy logikai bukfenc sem kizárt!!!