Neprocedurálne programovanie – zápočtová úloha

Dnes mi konečne prišlo vyhodnotenie riešenia mojej zápočtovej úlohy z neprocedurálneho programovania, ktoré som odovzdával približne pred dvomi týždňami. A zápočet som zaň dostal.

Zadanie úlohy bolo nasledovné: napíšte program, ktorý pre zvolený binárny strom a číslo N zistí, či je daný strom vnoriteľný do hyperkocky dimenzie N. Nebudem tu zabiehať do podrobností – len poviem, že je to celkom zaujímavá úloha, ktorú sme mali vyriešiť v jazyku Prolog.

Základnou myšlienkou úlohy je fakt, že ľubovoľný graf je vnoriteľný do hyperkocky, ak sa dajú jeho vrcholy ohodnotiť tak, aby spĺňali isté podmienky (všetku potrebnú teóriu nájdete v dokumentácii riešnia).

Ja som sa rozhodol riešiť úlohu priamočiaro – spoľahol som sa na vlastnosť Prologu zvanú backtracking, pomocou ktorej som si veľmi ľahko mohol generovať všetky možné ohodnotenia vrcholov stromu a skúšať, či spĺňajú potrebné podmienky. Ak áno, strom som označil za vnoriteľný, ak nie, vyskúšal som iné ohodnotenie vrcholov. A keď už som všetky ohodnotenia vyčerpal a žiadne nebolo vhodné, strom vnoriteľný nebol.

Súčasťou programu je aj metóda na generovanie stromov, ktorá vygeneruje všetky stromy s istými vlastnosťami (opäť viď dokumentácia).

Riešenie úlohy spolu s dokumentáciou si môžete stiahnuť z môjho účtu na Box.net.

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s