自动状态机实现经典过河问题

一、实验题目

       使用有限自动机编程解决如下问题：有一个人带着狼、羊和草来到河的左岸。左岸只有一条无人摆渡的船，这个人要从左岸过河到右岸。可是这条船最多只能装一个人和其他三者之一，否则便会沉没。如果没有人看管，狼会吃掉羊，或者羊吃掉草。问如何过河才能保证羊和草的安全?

二、题目分析

     W代表狼，G代表草，S代表羊，M代表人。初始状态”WSGM_”，结束状态”_WSGM”。人单独过河用字符m 表示，人带狼过河用字符w表示，人带羊过河用字符s 表示，人带草过河用字符g 表示。

 

三、程序代码

1、源文件head.h内容

#include <cstdlib>
#include <iostream>
#include <string.h>

using namespace std;

class State;
class List{
    List *next;
    char input;
    State *output;
    List(char in,State *out);
    ~List();
    friend class State;
};

class State{
    char *name;
    List *list;
    static State *error;
public:
    void enList(char in,State *out);
    const State *next(char in)const;
    const State *start(char *)const;
    State(char *name);
    ~State();
};

 

    if(name==0){ error=this; return; }
    State::name=new char[strlen(name)+1];
    strcpy(State::name, name);
}

void State::enList(char in, State *out){ //插入list
    List *temp;
    if(list==0){
        list=new List(in, out);
        return;
    }
    temp=new List(in, out);
    temp->next = list;
    list=temp;
}

const State *State::next(char in)const{ //输入in 转移到下一个状态
    List *temp=list;
    if(this==error) return error;
    while(temp)
        if(temp->input==in) return temp->output;
        else temp=temp->next;
    return error;
}

const State *State::start(char *s)const{ //启动有限自动机
    const State *temp = this;
    while(*s) temp=temp->next(*s++);
    return temp;
}

State::~State( ){
    if(name) { delete name; name=0; }
    if(list) {delete list; list=0; }
}

 

3、源文件List.cpp内容

#include"head.h"
List::List(char in, State *out){
    input=in;
    output=out;
    next=0;
}
List::~List( ){
    if(this->next){ delete this->next;}
}

 4、源文件lab1.cpp内容

#include"head.h"
int main( ){
    State start("WSGM_");
    State stop("_WSGM");
    State error(0);
    State WG_SM("WG_SM");
    State WGM_S("WGM_S");
    State G_WSM("G_WSM");
    State SGM_W("SGM_W");
    State W_SGM("W_SGM");
    State WSM_G("WSM_G");
    State S_WGM("S_WGM");
    State SM_WG("SM_WG");
    start.enList('S', &WG_SM);
    WG_SM.enList('S', &start);
    WG_SM.enList('M', &WGM_S);
    WGM_S.enList('M', &WG_SM);
    WGM_S.enList('W', &G_WSM);
    WGM_S.enList('G', &W_SGM);
    G_WSM.enList('W', &WGM_S);
    W_SGM.enList('G', &WGM_S);
    G_WSM.enList('S', &SGM_W);
    SGM_W.enList('S', &G_WSM);
    SGM_W.enList('G', &S_WGM);
    S_WGM.enList('G', &SGM_W);
    W_SGM.enList('S', &WSM_G);
    WSM_G.enList('S', &W_SGM);
    WSM_G.enList('W', &S_WGM);
    S_WGM.enList('W', &WSM_G);
    S_WGM.enList('M', &SM_WG);
    SM_WG.enList('M', &S_WGM);
    SM_WG.enList('S', &stop);
    stop.enList('S', &SM_WG);
    if(start.start("SMWSGMSSS")==&stop) cout<<"过河成功！\n";
    else cout<<"过河失败！\n";
    getchar();
    return 1;
 }

四、实验结果

#include"head.h"
// 用M 表示人 用W 表示野人 B代表船
// 初始状态为"BMMMYYY_" 终止状态为 "_BMMMYYY"
//过河动作可以有五种：人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b
int main( ){
    char m[80];
    State error(0);
    State start("start");//BMMMYYY_
    State MMMY_BYY("MMMY_BYY");//1
    State MMYY_BMY("MMYY_BMY");//2
    State BMMMYY_Y("BMMMYY_Y");//3
    State MMM_BYYY("MMM_BYYY");//4
    State BMMMY_YY("BMMMY_YY");//5
    State MY_BMMYY("MY_BMMYY");//6
    State BMMYY_MY("BMMYY_MY");//7
    State YY_BMMMY("YY_BMMMY");//8
    State BYYY_MMM("BYYY_MMM");//9
    State Y_BMMMYY("Y_BMMMYY");//10
    State BMY_MMYY("BMY_MMYY");//11
    State BYY_MMMY("BYY_MMMY");//12
    State stop("stop");//_BMMMYYY

    start.enList('t',&MMMY_BYY);
    start.enList('b',&MMYY_BMY);

    MMMY_BYY.enList('t',&start);
    MMMY_BYY.enList('w',&BMMMYY_Y);

    MMYY_BMY.enList('b',&start);
    MMYY_BMY.enList('s',&BMMMYY_Y);

    BMMMYY_Y.enList('w',&MMMY_BYY);
    BMMMYY_Y.enList('s',&MMYY_BMY);
    BMMMYY_Y.enList('t',&MMM_BYYY);

    MMM_BYYY.enList('t',&BMMMYY_Y);
    MMM_BYYY.enList('w',&BMMMY_YY);

    BMMMY_YY.enList('w',&MMM_BYYY);
    BMMMY_YY.enList('d',&MY_BMMYY);

    MY_BMMYY.enList('d',&BMMMY_YY);
    MY_BMMYY.enList('b',&BMMYY_MY);

    BMMYY_MY.enList('b',&MY_BMMYY);
    BMMYY_MY.enList('d',&YY_BMMMY);

    YY_BMMMY.enList('d',&BMMYY_MY);
    YY_BMMMY.enList('w',&BYYY_MMM);

    BYYY_MMM.enList('w',&YY_BMMMY);
    BYYY_MMM.enList('t',&Y_BMMMYY);

    Y_BMMMYY.enList('t',&BYYY_MMM);
    Y_BMMMYY.enList('s',&BMY_MMYY);
    Y_BMMMYY.enList('w',&BYY_MMMY);
    BMY_MMYY.enList('s',&Y_BMMMYY);
    BMY_MMYY.enList('b',&stop);

    BYY_MMMY.enList('w',&Y_BMMMYY);
    BYY_MMMY.enList('t',&stop);

    cout<<"人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b\n";
    cout<<"请输入:\n";
    cin>>m;
    getchar();
    if(start.start(m)==&stop) cout<<"过河成功！\n";
    else cout<<"过河失败！\n";
    getchar();
    return 1;
}

四、实验结果

 

实验二

 

 

一、实验题目

       有限自动机也可以解决三个修道士与三个野人的过河问题。假定船最多只能载两个修道士或者野人，野人服从修道士的指挥。 无论何时， 只要野人多于修道士， 野人就会吃掉修道士。 以有限自动机为基础， 编程解决三个修道士与三个野人的过河的问题。

二、问题分析

       用M 表示人， 用W 表示野人，初始状态为"BMMMYYY_"，结束状态” _BMMMYYY”。 过河动作可以有五种：人单独过河S， 两个人过河D， 野人单独过河W， 两个野人过河T， 人带着野人过河B。

 

 

 

 

三、程序代码

源文件lab2.cpp内容

#include"head.h"
// 用M 表示人 用W 表示野人 B代表船
// 初始状态为"BMMMYYY_" 终止状态为 "_BMMMYYY"
//过河动作可以有五种：人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b
int main_10( ){
    char m[80];
    State error(0);
    State start("start");//BMMMYYY_
    State MMMY_BYY("MMMY_BYY");//1
    State MMYY_BMY("MMYY_BMY");//2
    State BMMMYY_Y("BMMMYY_Y");//3
    State MMM_BYYY("MMM_BYYY");//4
    State BMMMY_YY("BMMMY_YY");//5
    State MY_BMMYY("MY_BMMYY");//6
    State BMMYY_MY("BMMYY_MY");//7
    State YY_BMMMY("YY_BMMMY");//8
    State BYYY_MMM("BYYY_MMM");//9
    State Y_BMMMYY("Y_BMMMYY");//10
    State BMY_MMYY("BMY_MMYY");//11
    State BYY_MMMY("BYY_MMMY");//12
    State stop("stop");//_BMMMYYY

    start.enList('t',&MMMY_BYY);
    start.enList('b',&MMYY_BMY);

    MMMY_BYY.enList('t',&start);
    MMMY_BYY.enList('w',&BMMMYY_Y);

    MMYY_BMY.enList('b',&start);
    MMYY_BMY.enList('s',&BMMMYY_Y);

    BMMMYY_Y.enList('w',&MMMY_BYY);
    BMMMYY_Y.enList('s',&MMYY_BMY);
    BMMMYY_Y.enList('t',&MMM_BYYY);

    MMM_BYYY.enList('t',&BMMMYY_Y);
    MMM_BYYY.enList('w',&BMMMY_YY);

    BMMMY_YY.enList('w',&MMM_BYYY);
    BMMMY_YY.enList('d',&MY_BMMYY);

    MY_BMMYY.enList('d',&BMMMY_YY);
    MY_BMMYY.enList('b',&BMMYY_MY);

    BMMYY_MY.enList('b',&MY_BMMYY);
    BMMYY_MY.enList('d',&YY_BMMMY);

    YY_BMMMY.enList('d',&BMMYY_MY);
    YY_BMMMY.enList('w',&BYYY_MMM);

    BYYY_MMM.enList('w',&YY_BMMMY);
    BYYY_MMM.enList('t',&Y_BMMMYY);

    Y_BMMMYY.enList('t',&BYYY_MMM);
    Y_BMMMYY.enList('s',&BMY_MMYY);
    Y_BMMMYY.enList('w',&BYY_MMMY);

    BMY_MMYY.enList('s',&Y_BMMMYY);
    BMY_MMYY.enList('b',&stop);

    BYY_MMMY.enList('w',&Y_BMMMYY);
    BYY_MMMY.enList('t',&stop);

    cout<<"人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b\n";
    cout<<"请输入:\n";
    cin>>m;
    getchar();
    if(start.start(m)==&stop) cout<<"过河成功！\n";
    else cout<<"过河失败！\n";

//  if(start.start("twtwdbdwtwt")==&stop) cout<<"ok\n";
//  else cout<<"error\n";
//
//  if(start.start("bstwdbdwtsb")==&stop) cout<<"ok\n";
//  else cout<<"error\n";

    getchar();
    return 1;
}