《农夫过河程序.doc》由会员分享，可在线阅读，更多相关《农夫过河程序.doc（4页珍藏版）》请在金锄头文库上搜索。
1、#include#include#define MAXNUM 20 typedef struct /顺序队列类型定义 int f, r; /f表示头，r 表示尾int qMAXNUM;/顺序队SeqQueue ,*PSeqQueue;PSeqQueue createEmptyQueue_seq( ) /创建队列 PSeqQueue paqu = new SeqQueue; if (paqu = NULL) coutOut of space!f=paqu-r=0; return (paqu); int isEmptyQueue_seq( PSeqQueue paqu ) /判断 paqu 所指是
2、否是空队列 return paqu-f=paqu-r; void enQueue_seq(PSeqQueue paqu,int x) /出队if (paqu-r+1)%MAXNUM=paqu-f) cout队列已满.qpaqu-r=x;paqu-r=(paqu-r+1)%MAXNUM; void deQueue_seq(PSeqQueue paqu) /删除队列头部元素 if( paqu-f=paqu-r) cout队列为空f=(paqu-f+1)%MAXNUM; int frontQueue_seq( PSeqQueue paqu ) /对非空队列,求队列头部元素 return (paqu-
3、qpaqu-f); int farmer(int location) /判断农夫位置对0做与运算，还是原来的数字，用来判断位置return 0 != (location & 0x08); int wolf(int location) /判断狼位置 return 0 != (location & 0x04); int cabbage(int location) /判断白菜位置 return 0 != (location & 0x02); int goat(int location) /判断羊的位置return 0 !=(location & 0x01); int safe(int locatio
4、n) / 若状态安全则返回 true if (goat(location) = cabbage(location) & (goat(location) != farmer(location) ) return 0; if (goat(location) = wolf(location) & (goat(location) != farmer(location) return 0;return 1; /其他状态是安全的 void farmerProblem( ) int movers, i, location, newlocation; int route16; /记录已考虑的状态路径 int
5、printMAXNUM; PSeqQueue moveTo; moveTo = createEmptyQueue_seq( );/新的队列判断路径 enQueue_seq(moveTo, 0x00); /初始状态为0 for (i = 0; i 16; i+) routei = -1; /-1表示没有记录过路径 route0=0; while (!isEmptyQueue_seq(moveTo)&(route15 = -1)/队列不为空，路径未满时循环 location = frontQueue_seq(moveTo); /从队头出队 deQueue_seq(moveTo); for (mov
6、ers = 1; movers = 8; movers= 1) if (0 != (location & 0x08) = (0 != (location & movers) newlocation = location(0x08|movers);/或运算 if (safe(newlocation) & (routenewlocation = -1)/判断是否安全，以及路径是否可用 routenewlocation = location; enQueue_seq(moveTo, newlocation); /* 打印出路径 */ if(route15 != -1) cout过河步骤是 : = 0
7、; location = routelocation) printi=location; i+; if (location = 0) break; int num=i-1; int temp204; int j; for(i=num;i=0;i-) for(j=3;j=0;j-) tempnum-ij=printi%2; printi/=2; temp0j=0; tempnum+1j=1; for(i=1;i=num;i+) couttttNO . it; if(i%2=1) if(tempi3!=tempi-13) cout农夫带羊过岸; if(tempi2!=tempi-12) cout农
8、夫带白菜过岸; if(tempi1!=tempi-11) cout农夫带狼过岸; if(tempi3=tempi-13&tempi2=tempi-12&tempi1=tempi-11) cout农夫自己过岸; else if(i%2=0) if(tempi3!=tempi-13) cout农夫带羊回岸; if(tempi2!=tempi-12) cout农夫带白菜回岸; if(tempi1!=tempi-11) cout农夫带狼回岸; if(tempi3=tempi-13&tempi2=tempi-12&tempi1=tempi-11) cout农夫自己回岸; coutendl; else coutNo solution.endl; int main() /*主函数*/ farmerProblem(); return 0;
