农夫过河问题.docx

《农夫过河问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*这道题要用c语言解决农夫带狼、白菜、羊过河的经典问题，*用到了队列及广度优先的算法，并且用到了一些位操作……*还把问题的描述转换成了数学模型，用数学符号表示问题的解*例如：15(二进制1111)表示：农夫、狼、白菜、羊都在*11(二进制1011)表示：农夫、白菜、羊都在*详细的解释是在《算法与数据结构——c语言描述(第三版)》P112*我在理解后多加了中文的操作描述,并输出*/#include#include#includetypedefintDataType;structNode;typedefstructNod

2、e*PNode;structNode{DataTypeinfo;PNodelink;};structLinkQueue{PNodef;PNoder;};typedefLinkQueue*PLinkQueue;//链接队列类型的指针PLinkQueuecreaEmptyQueue_link(void)//创建空队列{PLinkQueueplqu;plqu=(PLinkQueue)malloc(sizeof(structLinkQueue));if(plqu!=NULL){plqu->f=NULL;//头元素的结点指针plqu->r=NULL;//尾元素的结点指针}returnp

3、lqu;}intisEmptyQueue_link(PLinkQueueplqu){return(plqu->f==NULL);}intenQueue_link(PLinkQueueplqu,DataTypex)//入队操作{PNodep;p=(PNode)malloc(sizeof(structNode));if(p==NULL)return0;else{p->info=x;p->link=NULL;if(plqu->f==NULL)//插入前是空队列plqu->f=p;elseplqu->r->link=p;plqu->r=p;//修改队尾指针return1;}}intd

4、eQueue_link(PLinkQueueplqu)//出队操作{PNodep;if(plqu->f==NULL)return0;else{p=plqu->f;plqu->f=p->link;free(p);}return1;}DataTypefrontQueue_link(PLinkQueueplqu)//取出队列头部结点的数值{if(plqu->f==NULL)return-1;//注意这里返回的数值不严谨，请根据具体情况做出改变elsereturn(plqu->f->info);}/*判断农夫、狼。白菜、羊是否在*/intfarmer(intlocation){ret

5、urn((location&0x08)!=0);}intwolf(intlocation){return((location&0x04)!=0);}intcabbage(intlocation){return((location&0x02)!=0);}intsheep(intlocation){return((location&0x01)!=0);}voidgetNorth(intloca){if(farmer(loca)){printf("农夫");}if(wolf(loca)){printf("狼");}if(cabbage(loca)){printf("白菜");}if

6、(sheep(loca)){printf("羊");}}voidgetSouth(intloca){getNorth(~loca);//对数值以二进制取反}voidtranslate(intloca[],intlen){//开始时全部都在南岸//loca[]存放的是北岸的状态，并以倒叙的方式储存inti,v;intoperate;//负号表示往回运charobject[8][10]={"独自","羊","白菜","","狼"};charverb[4][10]={"把","带"};charverbObject[4][10]={"带到北岸","回到南岸","到北岸","回到南岸"

7、};printf("开始状态：");printf("南岸：");getSouth(loca[len-1]);printf("");printf("北岸：");getNorth(loca[len-1]);printf("");for(i=len-1;i>0;i--){printf("操作：");operate=loca[i-1]-loca[i];if(operate>0){if((operate-8)==0)v=4;elsev=0;}else{if((operate+8)==0)v=3;els