- This topic has 15 hozzászólás, 8 résztvevő, and was last updated 19 years, 2 months telt el by
.
-
Bejegyzés
-
vizsla wrote:Most komolyan egy ujjgyakorlatot akarsz itt megcsináltatni?
Bocsi, de nekem ez meghaladja…
Valami útvonalra vágyom, ehhez milyen módon kell nekifogni?A megoldáshoz segítséget nyújthat ez a fórum, ha átnézed:
Természetesen egy, az egyben nincs itt a válasz, de ezután már könnyen megírod.
„Bocsi, de nekem ez meghaladja…”
Monjuk, ha valaki olyan kifejezéseket használ, mint „ismétlés nélküli permutáció”, annak már nem hiszem… (legfeljebb a programozási ismeretekben van hiánya) 🙂Hogy érdekes legyen C++-ban (kiszámolni és összeállítani képes a kombinációkat; az elemek típusa megadható tetszõlegesen). Ha csak számolni kell, akkor az az egy pici részlet kell csak. (Ha valami nem világos lehet kérdezni.) 🙂
Ma „ebédszünetben” gondolkoztam egy kicsit rajta és ilyen gagyi algoritmust találtam ki rá – de még a ti javaslataitokat most fogom megnézni és akkor átdolgozom:
pl.: 3 különbözõ elem esetén kell 3!=6 db hely; elemeket számmal jelölöm (sztring tömb, aminek a dimenziója a helyettesítõ szám)
generáltatok 3 db 0..2 közötti véletlenszámot, megnézem, hogy ebben a sorren szerepel-e már a 3*6-os mátrixomban, ha nem felveszem; ezt ismételtetem, míg nem telik be a 3*6-os mátrix; az elemeket kiíratom az eredeti tömbbõl a koordinátákkaal…Na de ez anti-hatákony… Mindjárt megnézem a ti javaslataitokat is…
xcut: nem azzal van baj, a megoldása jó, csak nem hatékony (amennyiben feltételezzük, hogy véges idõn belül minden lehetséges értéket visszaad a véletlenszám generátor).
[[Delphiben jártam meg egyszer a véletlenszám generátorral…
8-as csoportokban akartam generáltatni õket (önkormányzatnak tajszám generátor kellett), de hamar kiderült, hogy mindig ugyan azt a 32 db 8-as csoportot állította elõ ugyan olyan sorrendben; amikor megadtam neki, hogy órától függjön, akkor az elsõ szám-nyolcas kiválasztása véletlen volt, de aztán ugyan az a 32 periódus ismétlõdött…„Na de ez anti-hatákony…”
Egy pettyet.
Ha valamit akarsz, akkor a köv. képpen járj el! Az összes kombináció eléréséhez mindig cserélj ki két elemet… és mindig mást, amíg el nem fogynak a kombinációk. Ezt két módon lehet megvalósítani.
a) összes komb. számának kiszámolása, majd egyenként egy kombináció elõállítása (én ezt alkalmaztam a példában)
+ nem kell tárolni az adatokat
– n!-t kell számolni (mert a kombinációk végét ez jelzi), vigyázni kell, hogy (használat elõtt) mindig ki legyen számolva a következõ
b) rekúrzív hívás
+ n!-t nem kell számolni, az összes kombináció egyszerre készül el
– memória felhasználás nagy (persze, most nem a te 5 elemedrõl van szó, de ha már megírsz egy algoritmust, akkor az lehetõség szerint legyen minnél általánosabb)
Pl. a (b) esetben
– 10 elem esetén épp belefér 14 MB-ba, de
– 13 elem esetén meghaladja a 13 GB-ot, de ez csak az adat terület
nem beszéltünk a rekúrzív hívásokból származó nagyságrendileg min. 50 GB-os!!! foglalásról.Nem tudom miért, de az (a) nekem szimpibb. Persze aztán lehet olyat csinálni, hogy egy operator++ mindig megadja a köv. kombinációt, vagy az operator– az elõzõt… persze ez már csak programozás-technikai kárdés.
„de hamar kiderült, hogy mindig ugyan azt a 32 db 8-as csoportot állította elõ ugyan olyan sorrendben”
Valójában, hogy a számítógép képes legyen valódi véletlen-számot generálni, annyi az esélye, minthogy te most hirtelen Hawaii strandján nyaralsz. :))))
- Be kell jelentkezni a hozzászóláshoz.
legutóbbi hsz