用顺序队列解决农夫过河问题的算法

ID:13437107

大小:36.50 KB

页数:3页

时间:2018-07-22

用顺序队列解决农夫过河问题的算法_第1页
用顺序队列解决农夫过河问题的算法_第2页
用顺序队列解决农夫过河问题的算法_第3页
资源描述:

《用顺序队列解决农夫过河问题的算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、/*用队列解决农夫过河问题的算法*/#include#include#defineMAXNUM20typedefintDataType;structSeqQueue{/*顺序队列类型定义*/intf,r;DataTypeq[MAXNUM];};typedefstructSeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/PSeqQueuecreateEmptyQueue_seq(void){PSeqQueuepaqu=(PSeqQueue)malloc(sizeof(structSeqQueue));if(

2、paqu==NULL)printf("Outofspace!!");elsepaqu->f=paqu->r=0;return(paqu);}intisEmptyQueue_seq(PSeqQueuepaqu){returnpaqu->f==paqu->r;}/*在队列中插入一元素x*/voidenQueue_seq(PSeqQueuepaqu,DataTypex){if((paqu->r+1)%MAXNUM==paqu->f)printf("Fullqueue.");else{paqu->q[paqu->r]=x;paqu->r=(paqu->r+1)

3、%MAXNUM;}}/*删除队列头部元素*/voiddeQueue_seq(PSeqQueuepaqu){if(paqu->f==paqu->r)printf("EmptyQueue.");elsepaqu->f=(paqu->f+1)%MAXNUM;}/*对非空队列,求队列头部元素*/DataTypefrontQueue_seq(PSeqQueuepaqu){return(paqu->q[paqu->f]);}intfarmer(intlocation){return0!=(location&0x08);}intwolf(intlocation){ret

4、urn0!=(location&0x04);}intcabbage(intlocation){return0!=(location&0x02);}intgoat(intlocation){return0!=(location&0x01);}/*若状态安全则返回true*/intsafe(intlocation){/*羊吃白菜*/if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;/*狼吃羊*/if((goat(location)==wolf(loc

5、ation))&&(goat(location)!=farmer(location)))return0;return1;/*其他状态是安全的*/}voidfarmerProblem(){intmovers,i,location,newlocation;introute[16];/*记录已考虑的状态路径*/PSeqQueuemoveTo;/*准备初值*/moveTo=createEmptyQueue_seq();enQueue_seq(moveTo,0x00);for(i=0;i<16;i++)route[i]=-1;route[0]=0;/*开始移动*/whi

6、le(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)){/*得到现在的状态*/location=frontQueue_seq(moveTo);deQueue_seq(moveTo);for(movers=1;movers<=8;movers<<=1){/*农夫总是在移动,随农夫移动的也只能是在农夫同侧的东西*/if((0!=(location&0x08))==(0!=(location&movers))){newlocation=location^(0x08

7、movers);if(safe(newlocation)&&(r

8、oute[newlocation]==-1)){route[newlocation]=location;enQueue_seq(moveTo,newlocation);}}}}/*打印出路径*/if(route[15]!=-1){printf("Thereversepathis:");for(location=15;location>=0;location=route[location]){printf("Thelocationis:%d",location);if(location==0)return;}}elseprintf("Nosolution

9、.");}intmain(){fa

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《用顺序队列解决农夫过河问题的算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、/*用队列解决农夫过河问题的算法*/#include#include#defineMAXNUM20typedefintDataType;structSeqQueue{/*顺序队列类型定义*/intf,r;DataTypeq[MAXNUM];};typedefstructSeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/PSeqQueuecreateEmptyQueue_seq(void){PSeqQueuepaqu=(PSeqQueue)malloc(sizeof(structSeqQueue));if(

2、paqu==NULL)printf("Outofspace!!");elsepaqu->f=paqu->r=0;return(paqu);}intisEmptyQueue_seq(PSeqQueuepaqu){returnpaqu->f==paqu->r;}/*在队列中插入一元素x*/voidenQueue_seq(PSeqQueuepaqu,DataTypex){if((paqu->r+1)%MAXNUM==paqu->f)printf("Fullqueue.");else{paqu->q[paqu->r]=x;paqu->r=(paqu->r+1)

3、%MAXNUM;}}/*删除队列头部元素*/voiddeQueue_seq(PSeqQueuepaqu){if(paqu->f==paqu->r)printf("EmptyQueue.");elsepaqu->f=(paqu->f+1)%MAXNUM;}/*对非空队列,求队列头部元素*/DataTypefrontQueue_seq(PSeqQueuepaqu){return(paqu->q[paqu->f]);}intfarmer(intlocation){return0!=(location&0x08);}intwolf(intlocation){ret

4、urn0!=(location&0x04);}intcabbage(intlocation){return0!=(location&0x02);}intgoat(intlocation){return0!=(location&0x01);}/*若状态安全则返回true*/intsafe(intlocation){/*羊吃白菜*/if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;/*狼吃羊*/if((goat(location)==wolf(loc

5、ation))&&(goat(location)!=farmer(location)))return0;return1;/*其他状态是安全的*/}voidfarmerProblem(){intmovers,i,location,newlocation;introute[16];/*记录已考虑的状态路径*/PSeqQueuemoveTo;/*准备初值*/moveTo=createEmptyQueue_seq();enQueue_seq(moveTo,0x00);for(i=0;i<16;i++)route[i]=-1;route[0]=0;/*开始移动*/whi

6、le(!isEmptyQueue_seq(moveTo)&&(route[15]==-1)){/*得到现在的状态*/location=frontQueue_seq(moveTo);deQueue_seq(moveTo);for(movers=1;movers<=8;movers<<=1){/*农夫总是在移动,随农夫移动的也只能是在农夫同侧的东西*/if((0!=(location&0x08))==(0!=(location&movers))){newlocation=location^(0x08

7、movers);if(safe(newlocation)&&(r

8、oute[newlocation]==-1)){route[newlocation]=location;enQueue_seq(moveTo,newlocation);}}}}/*打印出路径*/if(route[15]!=-1){printf("Thereversepathis:");for(location=15;location>=0;location=route[location]){printf("Thelocationis:%d",location);if(location==0)return;}}elseprintf("Nosolution

9、.");}intmain(){fa

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭