Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web

Historie:
pitel:izu:uloha1

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
pitel:izu:uloha1 [02. 04. 2013, 08.58:06] – file pitelpitel: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>Depth-first search|DFS]] a [[wp>Breadth-first search|BFS]] (případně dalšími) na problému misionářů a kanibalů.
  
 +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
 + *  Ukolem je implementovat reseni zname hadanky o 3 kanibalech a 3 misionarich
 + *  kteri maji za ukol dostat se na druhou stranu brehu za pomoci lodky o 2 mis-
 + *  tech. Na zadnem brehu nesmi byt kanibalu vice nez misionaru, jinak by byli
 + *  sezrani.
 + */
 +
 +#include <stdio.h>
 +#include <stdlib.h>
 +
 +// 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->data[s->top] = stat; // ulozi se
 +  }
 +  else{ // pokud je preplneno, exit
 +    fprintf(stderr, "ERROR: Stack full.");
 +    exit(1);
 +  }
 +}
 +
 +status stackPop(stack* s){
 +  if (s->top >= 0){ // pokud neni prazdno
 +    s->top--; // vrchol bude predchozi prvek
 +    return s->data[s->top + 1]; // a puvodni vrchol se vrati
 +  }
 +  else{ // pokus o vyber z prazdneho zasobniku
 +    fprintf(stderr, "ERROR: Stack empty.");
 +    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->data[i].cannibals &&  // se provede porovnani stavu
 +        stat.missionaries == s->data[i].missionaries &&
 +        stat.boat == s->data[i].boat
 +    ){
 +      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("(%d %d %d) ", s->data[i].cannibals, s->data[i].missionaries, 
 +    s->data[i].boat); // provedeme tisk     
 +  }
 +}
 +
 +/*******************************************************************************
 +  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; // provede se pripadna rotace
 +  if (q->end != q->front){ // pokud neni plno
 +    q->data[q->end] = stat; // vlozi se stav  
 +  }
 +  else{ // pokud je preplneno, exit
 +    fprintf(stderr, "ERROR: Queue full.");
 +    exit(3);
 +  }
 +}
 +
 +status queueRemove(queue* q){
 +  if (q->end != q->front){ // pokud neni fronta prazdna    
 +    q->front ++; // posune se zacatek
 +    q->front %= MAX_QUEUE_SIZE; // provede se pripadna rotace
 +    return q->data[q->front]; // a vrati se prislusny prvek
 +  }
 +  else{ // pokud je fronta prazdna
 +    fprintf(stderr, "ERROR: Queue empty.");
 +    exit(4);
 +  }
 +}
 +
 +void queueInit(queue* q){
 +  q->front = -1; // inicializace mimo pole
 +  q->end = -1;
 +}
 +
 +int queueEmpty(queue* q){
 +  return (q->front == q->end); // prazdno je pri rovnosti indexu
 +}
 +
 +int queueIsPresent(queue* q, status stat){
 +  int i = q->front + 1; // zacne se od prvniho prvku 
 +  i %= MAX_QUEUE_SIZE; // provede se pripadna rotace
 +  while (i != q->end + 1){ // dokud nejsou projite vsechny platne zaznamy 
 +    if (stat.cannibals == q->data[i].cannibals && // porovnava se
 +        stat.missionaries == q->data[i].missionaries &&
 +        stat.boat == q->data[i].boat
 +    ){ 
 +      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("(%d %d %d) ", q->data[i].cannibals, q->data[i].missionaries, 
 +                          q->data[i].boat);      
 +    i++;
 +    i %= MAX_QUEUE_SIZE;    
 +  }
 +}
 +
 +/******************************************************************************/
 +
 +// vypise stav jako trojici (pocet kanibalu na brehu 1, pocet misionaru, lodka)
 +// + pouzity operator
 +void printStatus(status stat){
 +  printf("(st: %d %d %d, op: ", stat.cannibals, stat.missionaries, stat.boat);
 +  switch (stat.appliedOperator){
 +    case TWO_CANNIBALS_FORW: printf("2CAN->"); break;
 +    case ONE_CANNIBAL_FORW: printf("1CAN->");  break;
 +    case ONE_CANN_ONE_MISS_FORW: printf("1CAN+1MIS->");  break;
 +    case TWO_MISSIONARIES_FORW: printf("2MIS->");  break;
 +    case ONE_MISSIONARY_FORW: printf("1MIS->");  break;
 +    case TWO_CANNIBALS_BACK: printf("2CAN<-");  break;
 +    case ONE_CANNIBAL_BACK: printf("1CAN<-");  break;
 +    case ONE_CANN_ONE_MISS_BACK: printf("1CAN+1MIS<-");  break;
 +    case TWO_MISSIONARIES_BACK: printf("2MIS<-");  break;
 +    case ONE_MISSIONARY_BACK: printf("1MIS<-");  break;
 +  }
 +  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, stat);
 + for (int oper = TWO_CANNIBALS_FORW; oper <= ONE_MISSIONARY_BACK; oper++) {
 + if (isApplicable(oper, stat)) {
 + currentStatus = applyOperator(oper, stat);
 + if (!stackIsPresent(closed, currentStatus) && !stackIsPresent(open, currentStatus)) {
 + printStatus(currentStatus);
 + stackPush(open, currentStatus);
 + }
 + }
 + }
 +}
 +
 +// 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, stat);
 + for (int oper = TWO_CANNIBALS_FORW; oper <= ONE_MISSIONARY_BACK; oper++) {
 + if (isApplicable(oper, stat)) {
 + currentStatus = applyOperator(oper, stat);
 + if (!queueIsPresent(closed, currentStatus) && !queueIsPresent(open, currentStatus)) {
 + printStatus(currentStatus);
 + queueInsert(open, currentStatus);
 + }
 + }
 + }
 +}
 +
 +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; // pomocny stav
 +//  int i; // citac
 +
 +  s.cannibals = CANNIBALS_CNT; // nastaveni pocatecniho stavu
 +  s.missionaries = MISSIONARIES_CNT;
 +  s.boat = DEFAULT_BOAT_POSITION;
 +
 +  /********************* DFS ********************/
 +  stackInit(&openDFS); // inicializace zasobniku
 +  stackInit(&closedDFS); 
 +  stackPush(&openDFS,s); // vlozeni startovaciho stavu
 +
 + printf("DFS:\n===\n");
 + while (1) {
 + if (stackEmpty(&openDFS)) {
 + printf("Unsolvable!\n");
 + break;
 + }
 + s = stackPop(&openDFS);
 + if (s.cannibals == 0 && s.missionaries == 0 && s.boat == 0) {
 + break;
 + }
 + generateDFS(s, &openDFS, &closedDFS);
 +
 + printf("\nOPEN:");
 + stackPrint(&openDFS);
 + printf("\nCLOSED:");
 + stackPrint(&closedDFS);
 + printf("\n");
 + }
 +
 +  /*****************************************/
 +  printf("\n\n\nBFS:\n===\n");
 +    
 +  s.cannibals = CANNIBALS_CNT; // nastaveni pocatecniho stavu
 +  s.missionaries = MISSIONARIES_CNT;
 +  s.boat = DEFAULT_BOAT_POSITION;
 +  queueInit(&openBFS); // inicilizace fronty
 +  queueInit(&closedBFS);
 +  queueInsert(&openBFS,s); // vlozeni pocatecniho stavu
 +
 + while (1) {
 + if (queueEmpty(&openBFS)) {
 + printf("Unsolvable!\n");
 + break;
 + }
 + s = queueRemove(&openBFS);
 + if (s.cannibals == 0 && s.missionaries == 0 && s.boat == 0) {
 + break;
 + }
 + generateBFS(s, &openBFS, &closedBFS);
 +
 + printf("\nOPEN:");
 + queuePrint(&openBFS);
 + printf("\nCLOSED:");
 + queuePrint(&closedBFS);
 + printf("\n");
 + }
 +  return 0;
 +}
 +</file>
/var/www/wiki/data/attic/pitel/izu/uloha1.1364893086.txt.bz2 · Poslední úprava: 30. 12. 2022, 13.43:01 (upraveno mimo DokuWiki)

Nástroje pro stránku

Kromě míst, kde je explicitně uvedeno jinak, je obsah této wiki licencován pod následující licencí: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki