农夫过河问题课程设计报告

农夫过河

1.农夫要将狼菜羊全部由河东岸运送至河的西岸；

2.农夫只有一条船且每次渡河都只能带一件物品；

3.当农夫不在场狼会吃掉羊，羊会吃菜。问农夫顺利带这三件物品渡河的最短路径。

首先这是一个数据结构问题。我们要求出农夫渡河的最简路径我们应当采取队列的广度优先搜索，相对于深度优先的栈而言广度优先级可以优先选择出最短的路径。

创建新队列并完善队列有关的判断队满队空，入队出队等函数：

typedef int EntryType;

typedef struct queue
{
EntryType data[MAXSIZE];
int front,rear;
}SeqQueue, * SeqQueuePtr;

SeqQueuePtr create_sequeue(void)
{
SeqQueuePtr pque;
pque = (SeqQueuePtr)malloc(sizeof(SeqQueue));
if(pque){
pque->front = 0;
pque->rear = 0;
}
else{
printf("Error: malloc() failed, out of memory!\n");
}
return(pque);
}

int is_queEmpty(SeqQueuePtr pque)
{
return( pque->front == pque->rear );
}

int is_queFull(SeqQueuePtr pque)
{
return( (pque->rear+1)%MAXSIZE == pque->front);
}

int enqueue(SeqQueuePtr pque, EntryType x)//入队
{
if(is_queFull(pque)){
printf("队满入队异常\n");
return 1;
}
else{
pque->data[pque->rear] = x;
pque->rear = (pque->rear + 1) % MAXSIZE;
return 0;
}
}

int dequeue(SeqQueuePtr pque, EntryType * e)//出队
{
if(is_queEmpty(pque)){
printf("出队异常队空.\n");
return 0;
}
else{
*e = pque->data[pque->front];
pque->front = (pque->front + 1) % MAXSIZE;
return 1;
}
}
入队 队尾往后移动一位出队队头出遵循先进先出原则

表示当前各单位状态

16位编译器中一个int占16位。在此我们定义一个整型变量int state用state的后四位分别表示农夫、狼、菜和羊的状态（0表尚未渡河，1表示渡河用四位二进制数分别顺序表示农夫、狼、白菜和羊的状态）使用位运算符“&”筛选出所需表示位：
int is_farmer_crossed(int state)
{
return ((state & 0x08) != 0);
}

int is_wolf_crossed(int state)
{
return ((state & 0x04) != 0);
}

int is_cabbage_crossed(int state)
{
return ((state & 0x02) != 0);
}

int is_goat_crossed(int state)
{
return ((state & 0x01) != 0);
}
将运算结果与0做对比判断是否渡河状态。

判断安全性

将状态存入队列之前要判断该状态是否安全，及调用上述状态函数排查出不安全的状态
int is_safe(int state)
{
if((is_goat_crossed(state) == is_cabbage_crossed(state)) &&
(is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且农夫不在场
return(0);
if((is_goat_crossed(state) == is_wolf_crossed(state)) &&
(is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且农夫不在场
return(0);
return(1);
}
若状态相容（安全）则返回1，否则返回0。

整理可用的状态并将其输出（核心代码）

void river_crossing_problem()
{
int route[16]; // 记录已经考虑过的状态
int state; // 记录当前时刻的状态（状态编号的二进制形式即状态本身）
int aftercross; // 记录渔夫当前的选择（渡河对象）会导致的结果状态
int passenger; // 临时变量，用于表达农夫的选择（对应二进制位为1表示选中该乘客）

int results[16]={0};     // 输出结果
int counter, i;    

SeqQueuePtr states_que;  //

states_que = create_sequeue(); // 创建“状态”队列 
enqueue(states_que,0x00);      // 初始状态0000入队

for(int i = 0; i < 16; i++){
    route[i] = -1;
}
        
while(!is_queEmpty(states_que) && (route[15] == -1))
{
    if( !dequeue(states_que, &state) ){
        printf("Error: dequeue() - the queue is empty\n");
    }
    
    // 依次考虑农夫可能的选择：携带羊、白菜和狼，以及农夫只身渡河        
    for( passenger = 1; passenger<= 8; passenger <<= 1 )
    {        
        // 由于农夫总是在过河，随农夫过河的也只能是与农夫同侧的东西
        if(((state & 0x08) != 0) == ((state & passenger) != 0)){
            // 如果农夫与当前乘客在河岸的同一侧 
            aftercross = state^( 0x08|passenger ); // 渡河后的情况 
            if(is_safe(aftercross) && (route[aftercross] == -1)){
                // 如果渡河后状态安全，则将其状态入队
                route[aftercross] = state;  // 将当前状态的索引记录到路径数组中（下标索引为后续状态值）
                enqueue(states_que, aftercross);
                //printf("%d-%d\n",aftercross,state);
            }
        }
    }//end for()
}//end while()

route数组中每一个下标都是一个状态，整个数组保存当前下标状态的前一个状态（ps：下一个状态尚未发生故无法表示有多个可能逻辑混乱）后将route数组整理保存至result数组中输出。

输出过河策略

if(route[15] != -1)
{
//printf("The reverse path is:\n");
counter = 0;
for(state = 15; state != 0; state = route[state]){
//printf("The state is: %d \n",state);
results[counter] = state;
counter++;
//if(state == 0) return;
}

    for(i = 0; i< counter; i++){
        state= results[i];
        aftercross = results[i+1];
        if(state & 0x08){
            printf("农夫从东岸到西岸:");
        }
        else{
            printf("农夫从西岸到东岸:");
        }
        switch(state^aftercross ){
        case 12:    //1100
            printf("把狼带过河\n");
            break;
        case 10:    //1010
            printf("把菜带过河\n");
            break;
        case 9:     //1001
            printf("把羊带过河\n");
            break;
        default:    //1000
            printf("什么也不带\n");
            break;
        }
    }
}
else{
    printf("No solution for this problem.\n");
}

}

主函数

int main(void)
{
river_crossing_problem();
system("pause");
return 0;
}

心得体会

通过此次解决农夫过河问题让我更深入了解了数据结构这门课程。且通过二进制表示农夫狼菜羊的状态让我熟悉了对位的了解和操作。将问题所有情况考虑完全后逐一排除排序，锻炼了我们的逻辑思维能力，激发了我对这门课程的兴趣。