农夫过河【数据结构实验报告】

柔情只为你懂 2022-06-06 09:14 321阅读 0赞

**数据结构实验报告**

**实验名称**：实验三 农夫过河

学号：\*\*\*

姓名：gnosed

实验日期：2017.10.30

**一、实验目的**

1、进一步掌握队列的使用

2、会使用队列进行农夫过河解的搜索

**二、实验具体内容**

**1、实验题目1：**

**（1）题目**

经典的农夫过河问题

一个农夫带着一只狼，一只羊和一颗白菜过河，从西岸到东岸。船太小，他每次过河只能携带一样东西，船只有农夫能撑。问题是狼会吃羊，羊会吃白菜，所以不能单独让狼和羊或者羊和白菜单独在河的一边，但狼不吃白菜。请问农夫采取什么方案，才能将所有东西安全运过河？

要求：使用广度优先搜索农夫过河解，并输出结果。

提示：可以使用STL中的队列进行代码编写。

**（2）分析**

首先对每件东西的位置进行描述，用4位二进制数顺序分别表示农夫、狼、羊和白菜的位置，0表示在东西河的西岸，1表示在东岸。例如1001表示农夫和白菜在东岸，狼和羊在西岸。

**数据结构：**

1. int location：用整型location表示位置状态，从初始化状态0（二进制为0000）到终结状态15（二进制为1111）。

2. queue<int> moves：用整型队列moves保存每一步所有可能达到的状态，队列每个元素表示一个安全的状态。按照队列先进先出的原则，只有在前一步的所有状态都处理完后，才开始处理后一步的各状态。

3. int route\[16\]：数组route有16种状态（0000~1111），用来记录已经被访问的各个状态，以及达到这些状态的前驱状态。做法是初始化元素值为-1，当往队列move入队一种安全状态时，将 以这个状态值作为下标的数组元素值（-1）改为达到这个状态的前驱状态的下标值。因此，当模拟完成时，利用route数组元素的值生成一个正确的状态路径。

**状态判断**：

1. 个体位置：根据 按位与&运算的性质，可使location与一个十六进制数相与，计算结果用来取某东西当前的位置。例如location & 0x08 ,结果为1表示农夫在西岸，否则在东岸。狼羊白菜的这个十六进制数分别为 0x04,0x02,0x01。

2. 安全：由四个东西的位置关系，判断该状态是否安全。不安全的状态只有两种，狼和羊，或者羊和白菜单独在河一侧。

**状态翻转：**

要从一种安全状态转换到另一种状态（过河），首先考虑各种物品的移动（通过左移<<运算），对于某些物品和农夫在同一侧的状态，就翻转状态判断其是否安全。因为农夫都必须改变状态，所以只有农夫被移动的东西（movers所表示）在同一岸时，农夫才可能将它带走。当然可以什么都不带，农夫可以直接过河。首先将movers和二进制0x00进行 按位或运算，确定需要翻转的位，再将这个结果与原来的状态location进行 异或运算，从而实现翻转，得到一个新的状态newlocation。具体细节看code。

**模拟过程：**

首先使初始状态0x00入队。

1）当队列不空且route\[15\]==-1（未被访问）时，取队头的状态location（出队），否则如果route\[15\]已被访问，输出方案，否则没有方案。

2）对于每个物品，判断其是否与农夫在河一侧，如全部物品都已判断，返回1）。

3）若是，则翻转当前状态location得到新的状态newlocation。

4）若newlocation安全而且新状态route\[newlocation\]没有被访问，将新状态入队，并记录新状态的前驱。返回2）。

**（3）实验代码**

源代码：

#include <iostream>
    #include <queue>
    
    using namespace std;
    
    //判断各物品的位置
    int famer(int location){
        return ((0x08 & location)!=0);
    }
    int wolf(int location){
        return ((0x04 & location)!=0);
    }
    int goat(int location){
        return ((0x02 & location)!=0);
    }
    int cabbage(int location){
        return ((0x01 & location)!=0);
    }
    //判断状态安全
    int safe(int location){
        if(wolf(location)==goat(location)&&famer(location)!=wolf(location))
            return 0;
        if(goat(location)==cabbage(location)&&famer(location)!=goat(location))
            return 0;
        return 1;
    }
    void farmerProblem(){
        queue<int> moves;
        int route[16],location,newlocation;
        for(int i=0;i<16;i++)   route[i]=-1;//赋初值
        moves.push(0x00);//初始状态入队
        route[0]=0;//记录
        while(!moves.empty()&&route[15]==-1){
            location=moves.front(); moves.pop();//取队头状态为当前状态
            for(int movers=1;movers<=8;movers<<=1){//考虑各种物品
                if(((location & movers)!=0)==((location & 0x08)!=0)){//农夫和物品在同一侧
                    newlocation=location ^ (0x08 | movers);//到新状态
                    if(safe(newlocation)&&route[newlocation]==-1){//新状态安全且其为处理
                        moves.push(newlocation);//新状态入队
                        route[newlocation]=location;//记录新状态的前驱
                    }
                }
            }
        }
        if(route[15]!=-1){//到达最终状态
            cout<<"Path:\n";
            for(int i=15;i>=0;i=route[i]){
                cout<<i<<" ";
                if(!i)  break;
            }
        }
        else    cout<<"No solution\n";//问题无解
    }
    int main()
    {
        farmerProblem();
        return 0;
    }

测试结果：

Path:

15 5 13 1 11 2 10 0

**三、实验小结**

1. 实验中一个巧妙的方法是用位数来模拟物品的位置以及位置的处理，这涉及到位运算，自己重新总结了一下。[http://blog.csdn.net/gnosed/article/details/78442571][http_blog.csdn.net_gnosed_article_details_78442571]

2. 对BFS有更深一步理解，基本掌握队列的使用。

[http_blog.csdn.net_gnosed_article_details_78442571]: http://blog.csdn.net/gnosed/article/details/78442571