Melyik az a matematikai művelet vagy eljárás, ami a következőt tudja?
Melyik az a matematikai művelet vagy eljárás, ami a következőt tudja:
Adott több darab szám, különböző értékek, mind hasonló nagyságrendben (például 1024,2048,4242,4241,2000,2020, ...) és ezen számokból szeretnék összeadással "összerakni" egy adott értéket (például 5000), illetve ahoz minél közelebbi értéket. Ezt lehet "találgatással", hogy tudom, hogy a listában szereplő számokból általában három vagy négy szám összegével kaphatom meg, az eddig a megfigyelésem, akkor választok kettőt random, majd egyet úgy, hogy az összegük a keresett érték körül legyen. Tudtok erre egy egyszerűbb eljárást? Mi ennek az eljárásnak és problémának a matematikai megnevezése?
(Nem házi feladat, egy hobbimhoz kell.)
Próbálgatással a legegyszerűbb.
Veszed a legnagyobb számot, ami van, hozzáadod az eddigi összeghez, és megnézed, hogy kisebb-e a szükséges összegnél (adott hibát elfogadhatsz).
Ha nem, kidobod.
Ha igen, visszalépsz az elejére.
Ha végigfutottál az összes számon, és nem jó az eredmény, akkor kidobod a legnagyobb számot, és kezded elölről.
Ezt a matematikai eljárást algoritmusnak hívják. Jellemzően egy eljárási sorrend, ezt nevezik numerikus módszernek is. Bármely feladathoz rengeteg algoritmus található, az igazi kérdés az, hogy közülük melyik a leggyorsabb.
A kérdésbeli feladat pontatlan, arra nem lehet módszert adni. A hasonló feladat így szól. Adott n darab szám, ahol a két szomszédos különbsége nm lehet k-nál nagyobb. Adott az S szám, kérdés, létezik-e, és ha igen hány megoldás, ahhoz, hogy m darab számot kiválasztva összegük éppen S legyen.
A primitív (szekvenciális) módszer az, hogy sorba rendezed a számokat, és sorra veszed őket, ha nem jó, eggyel odébb lépsz. Ha elfogytak, nincs megoldás (az egyezőségre). Ez ó sokszámolással jár, attól függően hány darab számod van. A viszonylag gyors módszerek a felezős eljárások. Itt többféle szempont szerint kettéosztják a számokat és felváltva választanak. A pontos és gyors algoritmus függ attól, mekkora n és m.
Ez a feladat:
> Adott több darab szám, különböző értékek, mind hasonló nagyságrendben (például 1024,2048,4242,4241,2000,2020, ...) és ezen számokból szeretnék összeadással "összerakni" egy adott értéket (például 5000), illetve ahoz minél közelebbi értéket.
és ez egy algoritmus:
> Például egy módszer: felírja az összes kombinációt, sorbarendezi az összegeiket és az 5000-et, megnézi az 5000 két szomszédját a listában, és amelyik közelebb van, az lesz a jó felírás.
Így utólag kicsit kontextusba is helyezném a már megválaszolt problémát, hátha másoknak is hasznos lehet, hogy ez hol jöhet jól bárkinek, vagy akár lehet belőle jó kis példafeladatokat kiadni:
Eszközök vásárlásához egy boltban egy bizonyos érték fölött adott fix kedvezményt adnak, ezt a minimum értéket szeretném éppen elérni és nem túlzottan meghaladni. A bolt kedvezményének érdekessége, hogy nem százalékosan adják, hanem adott értékben a vásárláshoz, ami azt jelenti, hogyha a kedvezmény eléréséhez szükséges érték kétszereséért szeretnék eszközöket vásárolni, akkor jobban járok, ha azt két külön körben teszem meg: így nem egyszer, hanem két külön vásárlásra érvényesül a fix értékű kedvezmény. Többször is így vásároltam, még a vásárlási feltételeket is elolvasva, hogy ez tényleg így az optimális, így a legkedvezőbb egy adott eszközre eső ár. Megjegyzendő, hogy mindez eléggé indokolatlan időráfordítás és mint valami játék, leginkább maga a rendszer megértése érdekelt, nem a pár forint különbség, így is épp elég nagy mértékben támogatom a boltot. Hasonló funkciójú eszközökből válogattam össze egy nagy listát, amiből szeretnék fokozatosan minél többet megszerezni, ilyen több adagos vásárlással. Annyira azért nem nagy mennyiség, hogy egyedi ajánlatot tudjak kérni, mert saját felhasználás, minden eszközből elég egy darab. Egy adag, egyszerre megvásárolandó eszköz értékének számítását optimalizálom tehát, nagy sikerrel, bár indokolatlanul nagy időráfordítással, mert jól szórakozok ezen a számoláson, amikor éppen kereken annyi, mint a minimum érték. A számolási időn akartam javítani és keresni a legjobb eljárást, leginkább azért, mert érdekes feladvány, másrészt így a minimális zsebpénzemből sikerül beszereznem mindent.
Annyiban különbözik a hátizsákos feladattól, hogy ott éppen ne haladja meg az adott értéket, itt éppen érje el, de ne túlzottan haladja azt meg.
Kapcsolódó 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!