农夫过河问题——程序设计.docx

《农夫过河问题——程序设计.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、农夫过河问题——程序设计一、成绩需要剖析一个农人带着一只狼、一只羊以及一棵黑菜，身处河的北岸。他要把那些器材齐部运到北岸。成绩是他里前只要一条划子，船小到只能容下他以及一件物品，别的只要农人能撑船。别的，果为狼能吃羊，而羊爱吃黑菜，以是农人没有能留下羊以及黑菜或者者狼以及羊独自正在河的一边，本人分开。叨教农人该接纳甚么圆案才干将一切的器材运过河呢？2、算法取舍供解那个成绩的最复杂的圆法是一步一步举行探索，每一一步皆搜刮一切大概的取舍，对于前一步开适的取舍再思索下一步的各类圆案。用盘算机真现上述供解的搜刮历程能够接纳两种没有同的战略：一种是广度劣先(b

2、readth_first)搜刮，另外一种是深度劣先(depth_first)。广度劣先：u广度劣先的露义便是正在搜刮历程中老是尾先搜刮上面一步的一切大概形态，而后再进一步思索更前面的各类情形。u要真现广度劣先搜刮，一样平常皆接纳行列做为帮助布局。把下一步一切大概到达的形态皆枚举进去，放正在那个行列中，而后逆序与进去分手举行处置，处置历程中把再下一步的形态放正在行列里……。u因为行列的操纵遵守先辈先出的本则，正在那个处置历程中，只要正在前一步的一切情形皆处置完后，才干入手下手前面一步各情形的处置。3、算法的粗化要摹拟农人过河成绩，尾先必要取舍一个对于成

3、绩中每一个脚色的地位举行形容的圆法。一个很圆便的举措是用4位2进造数逆序分手暗示农人、狼、黑菜以及羊的地位。比方用0暗示农人或者者某器材正在河的北岸，1暗示正在河的北岸。果此整数5(其2进造暗示为0101)暗示农人以及黑菜正在河的北岸，而狼以及羊正在北岸。4、算法的真现实现了下面的筹办事情，如今的成绩变为：从初初形态2进造0000(齐部正在河的北岸)动身，觅寻一种齐部由保险形态形成的形态序列，它以2进造1111(齐部抵达河的北岸)为终极宗旨，而且正在序列中的每一一个形态皆能够以前一形态经由过程农人（能够带同样器材）荡舟过河的举措抵达。为躲免没有需要的

4、瞎费工夫，请求正在序列中没有应当呈现反复的形态。为了真现广度劣先搜刮，算法中必要利用了一个整数行列moveTo，它的每一个元素暗示一个能够保险抵达的两头形态。别的借必要一个数据布局纪录已经被会见过的各个形态，和已经被收现的可以抵达以后那个形态的途径。因为正在那个成绩的办理历程中必要枚举的一切形态(2进造0000~1111)一共16种，以是能够机关一个包孕16个元素的整数逆序表去谦足以上的请求。用逆序表的第i个元素纪录形态i是不是已经被会见过，若已经被会见过则正在那个逆序表元素中记进先驱形态值，算法中把那个逆序表喊做route。route的每一个份量初

5、初化值均为-1，每一当咱们正在行列中减进一个新形态时，便把逆序表中以该形态做下标的元素的值改成到达那个形态的途径上前一形态的下标值。route的一个元素具备非背值暗示那个形态已经会见过，或者是正被思索。最初咱们能够使用route逆序表元素的值创建起准确的形态途径。5、步伐代码//farmerProblem.c//用行列办理农人过河成绩#include#includetypedefintDataType;//逆序行列：范例以及界里函数申明structSeqQueue{//逆序行列范例界说intMAXNUM;//行列中最年夜元素个数intf,r;Data

6、Type*q;typedefstructSeqQueue*PSeqQueue;//逆序行列范例的指针范例PSeqQueuecreateEmptyQueue_seq(intm){//创立一个空行列PSeqQueuequeue=(PSeqQueue)malloc(sizeof(structSeqQueue));if(queue!=NULL){queue->q=(DataType*)malloc(sizeof(DataType)*m);if(queue->q){queue->MAXNUM=m;queue->f=0;queue->r=0;return(que

7、ue);}elsefree(queue);}printf("Outofspace!!");//存储分派得败returnNULL;}intisEmptyQueue_seq(PSeqQueuequeue){//判别行列是不是为空return(queue->f==queue->r);}voidenQueue_seq(PSeqQueuequeue,DataTypex)//正在队尾拔出元素x{if((queue->r+1)%queue->MAXNUM==queue->f)printf("Fullqueue.");else{queue->q[queue-

8、>r]=x;queue->r=(queue->r+1)%queue->MAXNUM;}}voiddeQueu