Milyen algoritmussal lehetne a leghatékonyabban megoldani a következő problémát?
válasza:Rendben. Tehát vannak számhármasaim, tegyük fel az egyszerűség kedvéért, hogy 500 helyett csak 3 darab. { {x=20, y=50, z=30 }, {x=80, y=40, z=20}, {x= 44, y= 11, z= 99}}. Fel is lehet úgy fogni mint egy objektum gyűjteményt, ahol az objektumoknak három property-je van (x, y, z).
Aztán. Én megadom paraméterben azt, hogy {x = 100, y = 61, z = 129}, és erre szeretném visszakapni azokat a számhármasokat (objektumokat) amelyeknek a különböző elemeinek az összege kiadja ezeket az értékeket. Vagyis az X összegek, az Y összegek, és a Z összegek. Ebben a példában az 1. és a 3. a válasz vagyis: { {x=20, y=50, z=30 }, {x= 44, y= 11, z= 99}} mivel x1 + x3 = 100, y1 + y3 = 61, z1 + z3 = 129.
Ha pedig nincs pontosan ilyen érték, akkor a legközelebbit. Ha még mindig kicsit kusza, kérlek szólj megint. És köszönöm a gyors választ.
válasza:Arra vagy kíváncsi, hogy milyen egy konkrét algoritmussal lehetne ezt megoldani (fogalmam sincs, hogy van-e erre) vagy inkább az érdekelne, hogy aki programozó az milyen algoritmust írna erre a problémára?
Ha az első eset áll fenn, akkor lehet van aki tud segíteni, de én még algoritmusok óráról se emlékszem ilyesmire ami jó erre, aztán persze lehet volt:D
Viszont ha a második eset áll fenn, akkor már lehet tudnék én is és mások is segíteni.
A második esethez annyit kérdeznék előre, hogy maximum 500 darab ilyen számhármas lehet vagy ezt csak úgy példának mondtad?
A legközelebbi esetét nézve pedig mi legyen, ha egynél több is ugyan annyira lenne közel?
Köszönöm a hozzászólást. Igen, a második (programozó megközelítés) tökéletesen megfelelő lenne. Szóval igen, maximum 500-ban maximalizáljuk. Viszont fontos, hogy kell példa arra az esetre is amikor ismétlődhetnek az elemek, és olyanra is amikor nem.
Ami a legközelebbi esetet illeti, valójában az lenne a legjobb, ha a legközelebbi 5-öt adná vissza mindig (ha van pontos találat ha nincs). Ha több mint 5 ugyanolyan közel van, akkor mindegy melyik 5 a kiválasztott. De ha az 5 legközelebbit visszaadni macera, akkor elég az egyetlen legközelebbi is (ebben az esetben egyenlő esetén mindegy melyik)
Tehát a visszatérési érték az egy 5 elemű, tömböket tartalmazó tömb. pl:
[
[{x=20, y=50, z=30 }, {x= 44, y= 11, z= 99}],
[{x=50, y=20, z=70 }, {x=220, y=530, z=130 }, {x= 4, y= 1, z= 9}]
]
válasza:Ha felfogod az xyz-ket egy 3 dimmenziós tér pontjainak.
Megoldás #1: parasztba összeadsz minden pontot mindennel így új pontokat létrehozva, amikben tárolod, hogy melyekből jött ki.
Minden pontot kategorizálsz hogy a 3 tengelyű koordinátán hol helyezkedik el. Ebből ugye 8 van:
- x,y,z
- -x,y,z
- x,-y,z
- -x,-y,z
Ugyanezek -z vel. Mínuszok akkor, ha megengedett a negatív. Ha nem, csak egy zónád lesz a x,y,z.
Továbbá minden ponthoz rendelsz távolságoz a zérus helytől.
Sokat fog foglalni, de cserébe gyors lesz. És ha beadsz egy koordinátát, akkor nemes egyszerüséggel számolsz egy závolságot, negatív számok esetén tudod mely koordináta zónában vagy. Innentől a legközelebbi pontot kell megtalálni, így meg is van azok a x,y,z számhármas amikből kijönne.
válasza:#8 wow, zseniális válasz!
Én arra amúgy kíváncsi lennék, hogy milyen nyelvet használsz kérdező? Mert ha pythont, akkor lehet kevésbé matekos megoldást is kihozni pandas és numpy segítségével. De ez mondjuk nem változtat a tényen, hogy #8 válasza lesz a leggyorsabb és legszebb megoldás, wow.
válasza:"Ebben a példában az 1. és a 3. a válasz vagyis: { {x=20, y=50, z=30 }, {x= 44, y= 11, z= 99}} mivel x1 + x3 = 100, y1 + y3 = 61, z1 + z3 = 129"
20 + 44 < 100 ?? Miért x1 + x3 = 100 ?
50 + 11 = 61
99 + 30 = 129
"Sokat fog foglalni, de cserébe gyors lesz."
A legenerálás viszont nem lesz gyors. Ordóba köbös idejű és tárigényű/memória igényű.
"én még algoritmusok óráról se emlékszem ilyesmire ami jó erre, aztán persze lehet volt"
Pedig volt. Ládapakolási algoritmus angolul bin packing, röviden BP.
Algoritmusok közül a kombinatorikus optimalizálási feladathoz tartozik.
További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!