Algoritmusok

Ma pistike-gányolás közben beleütköztem egy problémába, amit csak nagyon rondán tudtam megoldani. A probléma általánosítása a következő:

Legyen A egy véges, nemüres halmaz, melynek bármely két eleme összemérhető. Soroljuk fel ennek a halmaznak az elemeit az összes lehetséges módon; éspedig úgy, hogy minden felsorolásban minden elem részt vegyen.

Intuitíve érzem, hogy erre létezik valami igazán egyszerű algoritmus, de sehogysem tudom megtalálni. Elővettem már a faktoriális definícióját, nézegettem az elemszám oszthatóságait, meg mindent, de hiányzik az "isteni" szikra. Azt szeretném kérni, hogy NE oldjátok meg helyettem a feladatot, csak adjatok valami ötletet, ami a lehető legelegánsabb megoldás első lépésére vezet rá. Köszönöm!

-------------------------------

A megoldás: rekurzió, ahogyan az első válaszban le van írva. Annyira végtelenül egyszerű, hogy talán pont emiatt nem is gondoltam rá.

Most, hogy mar "annyi mindent" megtanultam az OO programmozasrol, szivesen megtanulnam hasznalni is. Mert az egy dolog, hogy tudom, mi az inheritance, association, getters/setters (kedvenc setterem), stb, de nem igazan erzem azt, hogy tudnam, hogyan is irjak programmot. Mi hova keruljon, mi az, aminek mar kulon class kene, mit hanyjak egy helyre, egy classba mi menjen, egy adott dolog objektumon belul menjen le, vagy egy tobb objektumot bevono folyamatkent... tudnam meg sorolni, de azt hiszem ennyibol mar vilagos lesz, mire is lennek kivancsi.

http://en.wikipedia.org/wiki/Software_design_pattern

Erdekesnek tunik, bar egyelore meg nem neztem at alaposan az infot, szoval nem tudom, ezt keresem-e valojaban. Javasolnatok? Mas konyvvel esetleg jo tapasztalatok? Esetleg valami Java centrikusabb javaslat? (C-vel es Java-val mar igen, C++szal meg nem talalkoztam, az szeptembertol van teriteken)

Van egy eros preferenciam, a konyvnek angolul beszerezhetonek kene lennie.

Tud valaki ennél rövidebb "hordozható"-t? (válaszokat ugyanide, pls)

Szervusztok!

Idén is lesz Challenge24!

Szombaton, február 16-án lesz egy próbaforduló azoknak akik még nem indultak, vagy nem tudják, hogy mire számítsanak, jövőhéten szombaton, 23-án pedig egy 5 órás selejtezőforduló dönt a döntőbe jutó 27 csapatról, ahol a tavalyi első három helyezett már biztos résztvevőként szerepel.

A korábbi évek feladatait itt találjátok: http://ch24.org/archive.html

Jelentkezni meg természetszerűleg itt lehet: http://ch24.org

Probléma egyszerünek hangzik:

Adott egy N-elemü halmaz (vektor). Hány különbözö eleme (komponense) van?

Ugye ha mind különbözik, akkor N. De általánosan nem mind különbözik - mondjuk legyen N=4, és a vektorom {1,2,1,3}-ekkor 3 egyenlöségi osztály van. Kérdés egy olyan algoritmus, amely:

1. megszámolja az osztályokat, legyen számuk K
2. nem elég, hogy megszámolja öket, de visszatér egy K-dimenziós tömbbel, melynek elemei az eredeti vektor egyes osztályokba tartozó komponenseiböl álló tömbök, tehát a példánál maradva K=3, és a visszatérö tömb {(1,3),2,4}.

Mostanában viszonylag sokat foglalkoztam parser generátorokkal, tulajdonképpen keresem a megfelelő eszközt.
Alapvetően kétféle értelmező algoritmuscsaláddal találkoztam eddig: az LL és az (LA)LR módszerekkel.

Úgy tűnik, szinte minden nagyobb, modern értelmező program (pl. antlr) LL nyelvtannal dolgozik, amit azért nem értek, mert az LL nyelvtan nem tűri a balrekurziót, ami viszont a legtöbb CF nyelvben megtalálható, külön macera kezelni.

Miért szeretik mégis annyira az LL értelmezőket? Eddig azt láttam, hogy a balrekurzió megszüntetéséhez teljesen át kell variálni a nyelvtant, ami nem a legkellemesebb dolog. Vagy én tudok valamit rosszul?

Szeretnék egy dobókockás "Játék a betűkkel" játékot csinálni. 14 kocka (84 oldal = 84 betű). Betűgyakoriság alapján megvan, hogy melyikből mennyi legyen - már csak az a kérdés, hogy egy kockára mely betűk kerüljenek?

(Arra gondolok, hogy pl. mivel egy P és egy C van, ha ezek egy kockára kerülnek, nem lehet kirakni a "pici" "pacsi" stb. szavakat.)

Csináltam egy olyan listát is, ahol a szavakban előforduló betűpárok gyakorisága szerepel ("alma" -> "al", "am", "aa", ...). Érdemes szerintetek ezzel szórakozni, algoritmizálni, vagy kb. érzésre, találomra?

szaszi

Sziasztok,

Egy olyan problémám lenne, hogy ki kellene számolnom egy téglalapban levő elforgatott másik téglalap oldalainak hosszát. A belső téglalap 2 csúcsa rajta van a külső téglalap 2 élén.
Kiinduló adat a külső téglalap oldalainak hossza es a köztük lévő elforgatás szöge( a szög 1-45 fok között változhat).
Eyen a képen látszik miről is beszélek:
http://i45.tinypic.com/1058o5v.jpg
A következő képen azt rajzoltam be, hogy is próbáltam megoldani a feladatot:
http://i45.tinypic.com/15mcl51.jpg

Probáltam volna a két berajzolt háromszöget használni mivel azoknak tudom néhány adatát.
Igazából nem sikerült megoldanom :-(

Az biztos, ha a nagyobbik téglalap 750X500-as és 45 fokkal forgatjuk el, akkor a kisebbik téglalapnak 424X282-esnek kell lennie.

Van valakinek valamilyen müködő ötlete?

Igen, kényszerfeltétel, hogy a kis téglalap 2 csúcsa a nagyobbiknak a 2 vizszintes élén legyen.
És a 2 téglalap oldalainak aránya megeggyező.

Sziasztok!

Biztos van sok megoldás a problémámra a neten, de én sajnos nem találtam. Az lenne a feladat, hogy megtaláljam sok minta közül azokat, amelyek az adott tételre illenek. A minták olyan reguláris kifejezések, ahol csak a '.'-ot lehet használni (tehát karakterenként megadható, hogy bármi vagy egy adott érték lehet).
Kb. 300 minta lesz, és 10 karakter. Van annál gyorsabb módszer, hogy végignézem mind a 300-at egyesével?

Köszi,
Gábor

Van egy sík sokszögem. Csak 90 vagy 270 fokos szögei vannak. Csúcsainak koordinátái adottak.
Le kellene fednem minél kevesebb téglalappal, amelyek lehetőleg ne fedjék egymást.

Minimalizáls oka. Több ilyen szabálytalan sokszög lesz. Weblaphoz jön a kérdés, adott pont benne van-e az adott alakzatban vagy sem.
Az egész adatbázisban lesz tárolva, a lefedésre szolgáló téglalapok bal felső és jobb alsó koordinátáival. Minél kevesebb téglalap, annál kevesebb adatbázis sor -> gyorsabb lekérdezés.

Tud valaki erre algoritmust ajánlani?