Fórum: Lejárt határidejű informatika feladatokról

Sziasztok!

Arra lennék kíváncsi, hogy a KöMaLban megjelenő Excel-feladatokat szimplán képletekkel kell megoldani, vagy Visual Basic Scriptekkel is lehet?

Szia gd!

Nem hinném, hogy lenne nem exponenciális algoritmus erre a feladatra. Mert, ha nem nézzük végig az eseteket, akkor szerintem hipergráf színezett hiperéleinek kellene megfeleltetni az állításokat, akkor viszont egyfajta "legrövidebb út" keresése a probléma adott állításnál, hogy ez következik-e korábbiakból, illetve adott tulajdonság létezik-e, itt viszont ez a "legrövidebb út" probléma egyáltalán nem látszik könnyűnek. Igencsak meglepődnék 64 tulajdonságra müködő program esetén.

Egy javaslat: Ha az adott feladatot megoldó beleegyezik és csak ekkor, fel lehetne tenni a komal.hu-ra a megoldásokat, a hivatalos megoldás mellett ( bár legtöbbször ez sem jelenik meg ). Mindenki megnézhetné, hogy ki hogy oldotta meg vagy próbálta megoldani a feladatot. Így is tanulva a programozást. Nem haszontalan, mert bár jónéhány webhelyen lehet találni c++ forrásokat, azok a legtöbb esetben teljesen triviálisak és az ember semmit nem tanul belőlük. Én is kb. 3 darab c++ forrásból ( ezek elég hosszúak voltak ) tanultam meg a legalapvetőbb dolgokat c++ban.

Az S. 2. feladatot én csak (szerintem) "brutális" módszerrel tudtam megcsinálni: végignéztem az összes különböző esetet a megadott tulajdonságok szempontjából. Ez max. 8 tulajdonság esetén még jó (remélem, hogy 10000 sor esetén is le fog futni), de mondjuk 16 (pláne 32) tulajdonság esetén már túl lassú lenne. Először visszafelé gondolkodással próbálkoztam (miből tudnánk bebizonyítani a keresett állítást?), de a bonyolultabb eseteket nem tudtam kezelni. Van, akinek van jó ilyen, vagy más, a tulajdonságok számától nem exponenciálisan függő idejű algoritmusa? (Persze a brutális típusú lehet, hogy az adott esetben mindenképpen sokkal egyszerűbb volt.)

Kedves informatikafeladat-megoldók!

Ezt a témát a Lejárt határidejű KöMaL feladatok nevű fórum mintájára hoztam létre. (Bár az informatika feladatok is a KöMalhoz tartornak, ott nem láttam ilyen témájú hozzászólásokat. Szerintem jobb is külön témát csinálni, mert így jobban áttekinthető.)

Itt meg lehet beszélni, hogy ki hogy közelítette meg a feladatokat - így sokat lehetne tanulni egymástól. Itt főleg az S programozási feladatokra gondolok, mert azoknál nagyon bonyolultabbak az algoritmusok.