Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Následující verze | Předchozí verze | ||
pitel:izu:uloha1 [03. 07. 2012, 11.53:43] – upraveno mimo DokuWiki 127.0.0.1 | pitel:izu:uloha1 [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1 | ||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
+ | ====== Úkol 1 ====== | ||
+ | Vyzkoušet si jednoduchou implementaci prohledávání stavového prostoru metodami [[wp> | ||
+ | Na jednom břehu řeky stojí tři misionáři a tři kanibalové. Mají k dispozici lodičku, do které se vejdou maximálně dvě osoby. Jak se všichni přepraví na druhou stranu tak, aby nikdy na žádném břehu nebyla přesila kanibalů nad misionáři? | ||
+ | |||
+ | <file c main.gcc> | ||
+ | /* Misionari a kanibalove -- prvni ukol z IZU LS2006 | ||
+ | * (C) Zdenek Mazal | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | */ | ||
+ | |||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | // konstanty -- pocet kanibalu a misionaru | ||
+ | #define CANNIBALS_CNT 5 | ||
+ | #define MISSIONARIES_CNT 6 | ||
+ | #define DEFAULT_BOAT_POSITION 1 | ||
+ | // pomocne definice pro implementaci -- kardinalita mnoziny operatoru | ||
+ | #define OPERATORS_CNT 10 | ||
+ | // fronta i zasobnik jsou pro jednoduchost implementovany staticky pomoci pole | ||
+ | #define MAX_STACK_SIZE 1000 | ||
+ | #define MAX_QUEUE_SIZE 1000 | ||
+ | |||
+ | // operatory ulohy, tedy vsechny mozne kombinace, ktere se daji vozit lodkou | ||
+ | // obemi smery | ||
+ | typedef enum operators { | ||
+ | TWO_CANNIBALS_FORW, | ||
+ | ONE_CANNIBAL_FORW, | ||
+ | ONE_CANN_ONE_MISS_FORW, | ||
+ | TWO_MISSIONARIES_FORW, | ||
+ | ONE_MISSIONARY_FORW, | ||
+ | TWO_CANNIBALS_BACK, | ||
+ | ONE_CANNIBAL_BACK, | ||
+ | ONE_CANN_ONE_MISS_BACK, | ||
+ | TWO_MISSIONARIES_BACK, | ||
+ | ONE_MISSIONARY_BACK, | ||
+ | } operators; | ||
+ | |||
+ | /* definice stavu ulohy -- vyjadrujeme jej v souladu s prednaskami jako trojici | ||
+ | * - pocet kanibalu a misionaru na prvnim brehu | ||
+ | * - poloha lodky (1 = prvni breh, 0 = cilovy breh) | ||
+ | * dale je k dispozici operator, kterym jsme se do stavu dostali kvuli vypisum | ||
+ | * cilovy stav tedy je (0,0,0) | ||
+ | */ | ||
+ | typedef struct status{ | ||
+ | int cannibals; | ||
+ | int missionaries; | ||
+ | int boat; | ||
+ | operators appliedOperator; | ||
+ | } status; | ||
+ | |||
+ | /* | ||
+ | pomocna struktura zasobnik - pro manipulaci pouzivejte vyhradne definovane | ||
+ | funkce | ||
+ | */ | ||
+ | typedef struct stack{ | ||
+ | int top; | ||
+ | status data[MAX_STACK_SIZE]; | ||
+ | } stack; | ||
+ | |||
+ | /* | ||
+ | pomocna struktura fronta - pro manipulaci pouzivejte vyhradne definovane | ||
+ | funkce | ||
+ | */ | ||
+ | typedef struct queue{ | ||
+ | int front; | ||
+ | int end; | ||
+ | status data[MAX_QUEUE_SIZE]; | ||
+ | } queue; | ||
+ | |||
+ | |||
+ | / | ||
+ | nasleduji funkce pro praci se zasobnikem, a to: | ||
+ | void stackPush(stack* s, status stat) - vlozi stav do zasobniku | ||
+ | status stackPop(stack* s) - vyjme a vrati stav ze zasobniku | ||
+ | void stackInit(stack* s) - inicializuje zasobnik | ||
+ | int stackEmpty(stack* s) - vraci 1 pokud je zasobnik prazdny | ||
+ | int stackIsPresent(stack* s, status stat) - vraci 1 pokud se stav nachazi v | ||
+ | zasobniku | ||
+ | void stackPrint(stack* s) - vypise obsah zasobniku | ||
+ | *******************************************************************************/ | ||
+ | |||
+ | void stackPush(stack* s, status stat){ | ||
+ | s->top ++; // vrchol bude dalsi prvek | ||
+ | if (s->top < MAX_STACK_SIZE){ // pokud neni plno | ||
+ | s-> | ||
+ | } | ||
+ | else{ // pokud je preplneno, exit | ||
+ | fprintf(stderr, | ||
+ | exit(1); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | status stackPop(stack* s){ | ||
+ | if (s->top >= 0){ // pokud neni prazdno | ||
+ | s-> | ||
+ | return s-> | ||
+ | } | ||
+ | else{ // pokus o vyber z prazdneho zasobniku | ||
+ | fprintf(stderr, | ||
+ | exit(2); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void stackInit(stack* s){ | ||
+ | s->top = -1; // na pocatku je index mimo pole | ||
+ | } | ||
+ | |||
+ | int stackEmpty(stack* s){ | ||
+ | return (s->top < 0); // pokud je index mimo pole... | ||
+ | } | ||
+ | |||
+ | int stackIsPresent(stack* s, status stat){ | ||
+ | int i; | ||
+ | for (i = 0; i <= s->top; i++){ // pro vsechny aktualni zaznamy | ||
+ | if (stat.cannibals == s-> | ||
+ | stat.missionaries == s-> | ||
+ | stat.boat == s-> | ||
+ | ){ | ||
+ | return 1; // pokud nastane shoda, vraci se uspech | ||
+ | } | ||
+ | } | ||
+ | return 0; // jinak neuspech | ||
+ | } | ||
+ | |||
+ | void stackPrint(stack* s){ | ||
+ | int i; | ||
+ | for (i = 0; i <= s->top; i++){ // pro vsechny aktualni zaznamy | ||
+ | printf(" | ||
+ | s-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | / | ||
+ | nasleduji funkce pro praci s frontou, a to: | ||
+ | void queueInsert(queue* q, status stat) - vlozi stav do fronty | ||
+ | status queueRemove(queue* q) - vyjme a vrati stav z konce fronty | ||
+ | void queueInit(queue* q) - inicializuje frontu | ||
+ | int queueEmpty(queue* q) - vraci 1 pokud je fronta prazdna | ||
+ | int queueIsPresent(queue* q, status stat) - vraci 1 pokud se stav nachazi ve | ||
+ | fronte | ||
+ | void queuePrint(queue* q) - vypise obsah fronty | ||
+ | *******************************************************************************/ | ||
+ | |||
+ | void queueInsert(queue* q, status stat){ | ||
+ | q->end ++; // posune se konec | ||
+ | q->end %= MAX_QUEUE_SIZE; | ||
+ | if (q->end != q-> | ||
+ | q-> | ||
+ | } | ||
+ | else{ // pokud je preplneno, exit | ||
+ | fprintf(stderr, | ||
+ | exit(3); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | status queueRemove(queue* q){ | ||
+ | if (q->end != q-> | ||
+ | q->front ++; // posune se zacatek | ||
+ | q->front %= MAX_QUEUE_SIZE; | ||
+ | return q-> | ||
+ | } | ||
+ | else{ // pokud je fronta prazdna | ||
+ | fprintf(stderr, | ||
+ | exit(4); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void queueInit(queue* q){ | ||
+ | q->front = -1; // inicializace mimo pole | ||
+ | q->end = -1; | ||
+ | } | ||
+ | |||
+ | int queueEmpty(queue* q){ | ||
+ | return (q-> | ||
+ | } | ||
+ | |||
+ | int queueIsPresent(queue* q, status stat){ | ||
+ | int i = q->front + 1; // zacne se od prvniho prvku | ||
+ | i %= MAX_QUEUE_SIZE; | ||
+ | while (i != q->end + 1){ // dokud nejsou projite vsechny platne zaznamy | ||
+ | if (stat.cannibals == q-> | ||
+ | stat.missionaries == q-> | ||
+ | stat.boat == q-> | ||
+ | ){ | ||
+ | return 1; // pripadne se vraci uspech | ||
+ | } | ||
+ | i++; // zvyseni citace | ||
+ | i %= MAX_QUEUE_SIZE; | ||
+ | } | ||
+ | return 0; // nenalezeno | ||
+ | } | ||
+ | |||
+ | void queuePrint(queue* q){ | ||
+ | int i = q->front + 1; // obdoba predchozi fce, jen se misto porovnani tiskne | ||
+ | i %= MAX_QUEUE_SIZE; | ||
+ | while (i != q->end + 1){ | ||
+ | printf(" | ||
+ | q-> | ||
+ | i++; | ||
+ | i %= MAX_QUEUE_SIZE; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | / | ||
+ | |||
+ | // vypise stav jako trojici (pocet kanibalu na brehu 1, pocet misionaru, lodka) | ||
+ | // + pouzity operator | ||
+ | void printStatus(status stat){ | ||
+ | printf(" | ||
+ | switch (stat.appliedOperator){ | ||
+ | case TWO_CANNIBALS_FORW: | ||
+ | case ONE_CANNIBAL_FORW: | ||
+ | case ONE_CANN_ONE_MISS_FORW: | ||
+ | case TWO_MISSIONARIES_FORW: | ||
+ | case ONE_MISSIONARY_FORW: | ||
+ | case TWO_CANNIBALS_BACK: | ||
+ | case ONE_CANNIBAL_BACK: | ||
+ | case ONE_CANN_ONE_MISS_BACK: | ||
+ | case TWO_MISSIONARIES_BACK: | ||
+ | case ONE_MISSIONARY_BACK: | ||
+ | } | ||
+ | printf(" | ||
+ | } | ||
+ | |||
+ | // otestuje, zda se operator da pouzit ve stavu zadanem parametrem | ||
+ | int isApplicable(operators oper, status stat){ | ||
+ | switch (oper) { | ||
+ | case TWO_CANNIBALS_FORW: | ||
+ | if (stat.boat == 1 && stat.cannibals >= 2 && (stat.missionaries == MISSIONARIES_CNT || stat.missionaries == 0)) { | ||
+ | return 1; | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_CANNIBAL_FORW: | ||
+ | if (stat.boat == 1 && stat.cannibals >= 1) { | ||
+ | if (stat.missionaries == MISSIONARIES_CNT || stat.missionaries == 0) { | ||
+ | return 1; | ||
+ | } | ||
+ | if ((stat.missionaries >= stat.cannibals - 1) && (MISSIONARIES_CNT - stat.missionaries >= CANNIBALS_CNT - stat.cannibals + 1)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_CANN_ONE_MISS_FORW: | ||
+ | if (stat.boat == 1 && stat.cannibals >= 1 && stat.missionaries >= 1) { | ||
+ | if ((stat.missionaries - 1 >= stat.cannibals - 1) && (MISSIONARIES_CNT - stat.missionaries + 1 >= CANNIBALS_CNT - stat.cannibals + 1)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case TWO_MISSIONARIES_FORW: | ||
+ | if (stat.boat == 1 && stat.missionaries >= 2) { | ||
+ | if (stat.missionaries - 2 == 0) { | ||
+ | return 1; | ||
+ | } | ||
+ | if ((stat.missionaries - 2 >= stat.cannibals) && (MISSIONARIES_CNT - stat.missionaries + 2 >= CANNIBALS_CNT - stat.cannibals)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_MISSIONARY_FORW: | ||
+ | if (stat.boat == 1 && stat.missionaries >= 1) { | ||
+ | if ((stat.missionaries - 1 >= stat.cannibals) && (MISSIONARIES_CNT - stat.missionaries + 1 >= CANNIBALS_CNT - stat.cannibals)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case TWO_CANNIBALS_BACK: | ||
+ | if (stat.boat == 0 && CANNIBALS_CNT - stat.cannibals >= 2 && (stat.missionaries == MISSIONARIES_CNT || stat.missionaries == 0)) { | ||
+ | return 1; | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_CANNIBAL_BACK: | ||
+ | if (stat.boat == 0 && CANNIBALS_CNT - stat.cannibals >= 1) { | ||
+ | if (stat.missionaries == MISSIONARIES_CNT || stat.missionaries == 0) { | ||
+ | return 1; | ||
+ | } | ||
+ | if ((stat.missionaries >= stat.cannibals + 1) && (MISSIONARIES_CNT - stat.missionaries >= CANNIBALS_CNT - stat.cannibals - 1)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_CANN_ONE_MISS_BACK: | ||
+ | if (stat.boat == 0 && CANNIBALS_CNT - stat.cannibals >= 1 && MISSIONARIES_CNT - stat.missionaries >= 1) { | ||
+ | if ((stat.missionaries + 1 >= stat.cannibals + 1) && (MISSIONARIES_CNT - stat.missionaries - 1 >= CANNIBALS_CNT - stat.cannibals - 1)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case TWO_MISSIONARIES_BACK: | ||
+ | if (stat.boat == 0 && MISSIONARIES_CNT - stat.missionaries >= 2) { | ||
+ | if (stat.missionaries + 2 == 0) { | ||
+ | return 1; | ||
+ | } | ||
+ | if ((stat.missionaries + 2 >= stat.cannibals) && (MISSIONARIES_CNT - stat.missionaries - 2 >= CANNIBALS_CNT - stat.cannibals)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | case ONE_MISSIONARY_BACK: | ||
+ | if (stat.boat == 0 && MISSIONARIES_CNT - stat.missionaries >= 1) { | ||
+ | if (stat.missionaries + 1 == MISSIONARIES_CNT) { | ||
+ | return 1; | ||
+ | } | ||
+ | if ((stat.missionaries + 1 >= stat.cannibals) && (MISSIONARIES_CNT - stat.missionaries - 1 >= CANNIBALS_CNT - stat.cannibals)) { | ||
+ | return 1; | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | break; | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | |||
+ | // aplikuje operator, vraci novy stav | ||
+ | status applyOperator(operators oper, status stat){ | ||
+ | switch (oper) { | ||
+ | case TWO_CANNIBALS_FORW: | ||
+ | stat.boat = 0; | ||
+ | stat.cannibals -= 2; | ||
+ | stat.appliedOperator = TWO_CANNIBALS_FORW; | ||
+ | break; | ||
+ | case ONE_CANNIBAL_FORW: | ||
+ | stat.boat = 0; | ||
+ | stat.cannibals--; | ||
+ | stat.appliedOperator = ONE_CANNIBAL_FORW; | ||
+ | break; | ||
+ | case ONE_CANN_ONE_MISS_FORW: | ||
+ | stat.boat = 0; | ||
+ | stat.cannibals--; | ||
+ | stat.missionaries--; | ||
+ | stat.appliedOperator = ONE_CANN_ONE_MISS_FORW; | ||
+ | break; | ||
+ | case TWO_MISSIONARIES_FORW: | ||
+ | stat.boat = 0; | ||
+ | stat.missionaries -= 2; | ||
+ | stat.appliedOperator = TWO_MISSIONARIES_FORW; | ||
+ | break; | ||
+ | case ONE_MISSIONARY_FORW: | ||
+ | stat.boat = 0; | ||
+ | stat.missionaries--; | ||
+ | stat.appliedOperator = ONE_MISSIONARY_FORW; | ||
+ | break; | ||
+ | case TWO_CANNIBALS_BACK: | ||
+ | stat.boat = 1; | ||
+ | stat.cannibals += 2; | ||
+ | stat.appliedOperator = TWO_CANNIBALS_BACK; | ||
+ | break; | ||
+ | case ONE_CANNIBAL_BACK: | ||
+ | stat.boat = 1; | ||
+ | stat.cannibals++; | ||
+ | stat.appliedOperator = ONE_CANNIBAL_BACK; | ||
+ | break; | ||
+ | case ONE_CANN_ONE_MISS_BACK: | ||
+ | stat.boat = 1; | ||
+ | stat.cannibals++; | ||
+ | stat.missionaries++; | ||
+ | stat.appliedOperator = ONE_CANN_ONE_MISS_BACK; | ||
+ | break; | ||
+ | case TWO_MISSIONARIES_BACK: | ||
+ | stat.boat = 1; | ||
+ | stat.missionaries += 2; | ||
+ | stat.appliedOperator = TWO_MISSIONARIES_BACK; | ||
+ | break; | ||
+ | case ONE_MISSIONARY_BACK: | ||
+ | stat.boat = 1; | ||
+ | stat.missionaries++; | ||
+ | stat.appliedOperator = ONE_MISSIONARY_BACK; | ||
+ | break; | ||
+ | } | ||
+ | return stat; | ||
+ | } | ||
+ | |||
+ | // vygeneruje stavy pro DFS, ktere jsou dosazitelne z daneho stavu | ||
+ | // a vlozi je do open | ||
+ | void generateDFS(status stat, stack* open, stack* closed){ | ||
+ | status currentStatus; | ||
+ | stackPush(closed, | ||
+ | for (int oper = TWO_CANNIBALS_FORW; | ||
+ | if (isApplicable(oper, | ||
+ | currentStatus = applyOperator(oper, | ||
+ | if (!stackIsPresent(closed, | ||
+ | printStatus(currentStatus); | ||
+ | stackPush(open, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | // vygeneruje stavy pro BFS, ktere jsou dosazitelne z daneho stavu | ||
+ | // a vlozi je do open | ||
+ | void generateBFS(status stat, queue* open, queue* closed){ | ||
+ | status currentStatus; | ||
+ | queueInsert(closed, | ||
+ | for (int oper = TWO_CANNIBALS_FORW; | ||
+ | if (isApplicable(oper, | ||
+ | currentStatus = applyOperator(oper, | ||
+ | if (!queueIsPresent(closed, | ||
+ | printStatus(currentStatus); | ||
+ | queueInsert(open, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | int main(int argc, char *argv[]){ | ||
+ | |||
+ | status s; // pocatecni stav | ||
+ | stack openDFS; // zasobnik open pro DFS | ||
+ | stack closedDFS; // zasobnik closed pro DFS | ||
+ | queue openBFS; // fronta open pro BFS | ||
+ | queue closedBFS; // fronta closed pro BFS | ||
+ | // status currentStatus; | ||
+ | // int i; // citac | ||
+ | |||
+ | s.cannibals = CANNIBALS_CNT; | ||
+ | s.missionaries = MISSIONARIES_CNT; | ||
+ | s.boat = DEFAULT_BOAT_POSITION; | ||
+ | |||
+ | / | ||
+ | stackInit(& | ||
+ | stackInit(& | ||
+ | stackPush(& | ||
+ | |||
+ | printf(" | ||
+ | while (1) { | ||
+ | if (stackEmpty(& | ||
+ | printf(" | ||
+ | break; | ||
+ | } | ||
+ | s = stackPop(& | ||
+ | if (s.cannibals == 0 && s.missionaries == 0 && s.boat == 0) { | ||
+ | break; | ||
+ | } | ||
+ | generateDFS(s, | ||
+ | |||
+ | printf(" | ||
+ | stackPrint(& | ||
+ | printf(" | ||
+ | stackPrint(& | ||
+ | printf(" | ||
+ | } | ||
+ | |||
+ | / | ||
+ | printf(" | ||
+ | | ||
+ | s.cannibals = CANNIBALS_CNT; | ||
+ | s.missionaries = MISSIONARIES_CNT; | ||
+ | s.boat = DEFAULT_BOAT_POSITION; | ||
+ | queueInit(& | ||
+ | queueInit(& | ||
+ | queueInsert(& | ||
+ | |||
+ | while (1) { | ||
+ | if (queueEmpty(& | ||
+ | printf(" | ||
+ | break; | ||
+ | } | ||
+ | s = queueRemove(& | ||
+ | if (s.cannibals == 0 && s.missionaries == 0 && s.boat == 0) { | ||
+ | break; | ||
+ | } | ||
+ | generateBFS(s, | ||
+ | |||
+ | printf(" | ||
+ | queuePrint(& | ||
+ | printf(" | ||
+ | queuePrint(& | ||
+ | printf(" | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | </ |