`
liss
  • 浏览: 844326 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

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

阅读更多

一、实验题目

       使用有限自动机编程解决如下问题有一个人带着狼、羊和草来到河的左岸。左岸只有一条无人摆渡的船,这个人要从左岸过河到右岸。可是这条船最多只能装一个人和其他三者之一,否则便会沉没。如果没有人看管,狼会吃掉羊,或者羊吃掉草。问如何过河才能保证羊和草的安全?
二、题目分析
     W代表狼,G代表草,S代表羊,M代表人。初始状态”WSGM_”,结束状态”_WSGM”。人单独过河用字符m 表示,人带狼过河用字符w表示,人带羊过河用字符s 表示,人带草过河用字符g 表示。
 

三、程序代码
1、源文件head.h内容
Code:
  1. #include <cstdlib>   
  2. #include <iostream>   
  3. #include <string.h>   
  4.   
  5. using namespace std;   
  6.   
  7. class State;   
  8. class List{   
  9.     List *next;   
  10.     char input;   
  11.     State *output;   
  12.     List(char in,State *out);   
  13.     ~List();   
  14.     friend class State;   
  15. };   
  16.   
  17. class State{   
  18.     char *name;   
  19.     List *list;   
  20.     static State *error;   
  21. public:   
  22.     void enList(char in,State *out);   
  23.     const State *next(char in)const;   
  24.     const State *start(char *)const;   
  25.     State(char *name);   
  26.     ~State();   
  27. };   

 

  1.  
  2.     if(name==0){ error=thisreturn; }   
  3.     State::name=new char[strlen(name)+1];   
  4.     strcpy(State::name, name);   
  5. }   
  6.   
  7. void State::enList(char in, State *out){ //插入list   
  8.     List *temp;   
  9.     if(list==0){   
  10.         list=new List(in, out);   
  11.         return;   
  12.     }   
  13.     temp=new List(in, out);   
  14.     temp->next = list;   
  15.     list=temp;   
  16. }   
  17.   
  18. const State *State::next(char in)const//输入in 转移到下一个状态   
  19.     List *temp=list;   
  20.     if(this==error) return error;   
  21.     while(temp)   
  22.         if(temp->input==in) return temp->output;   
  23.         else temp=temp->next;   
  24.     return error;   
  25. }   
  26.   
  27. const State *State::start(char *s)const//启动有限自动机   
  28.     const State *temp = this;   
  29.     while(*s) temp=temp->next(*s++);   
  30.     return temp;   
  31. }   
  32.   
  33. State::~State( ){   
  34.     if(name) { delete name; name=0; }   
  35.     if(list) {delete list; list=0; }   
  36. }   

 

 

 
3、源文件List.cpp内容
Code:
  1. #include"head.h"   
  2. List::List(char in, State *out){   
  3.     input=in;   
  4.     output=out;   
  5.     next=0;   
  6. }   
  7. List::~List( ){   
  8.     if(this->next){ delete this->next;}   
  9. }   

 

 

 4、源文件lab1.cpp内容

Code:
  1. #include"head.h"    
  2. int main( ){   
  3.     State start("WSGM_");   
  4.     State stop("_WSGM");   
  5.     State error(0);   
  6.     State WG_SM("WG_SM");   
  7.     State WGM_S("WGM_S");   
  8.     State G_WSM("G_WSM");   
  9.     State SGM_W("SGM_W");   
  10.     State W_SGM("W_SGM");   
  11.     State WSM_G("WSM_G");   
  12.     State S_WGM("S_WGM");   
  13.     State SM_WG("SM_WG");   
  14.     start.enList('S', &WG_SM);   
  15.     WG_SM.enList('S', &start);   
  16.     WG_SM.enList('M', &WGM_S);   
  17.     WGM_S.enList('M', &WG_SM);   
  18.     WGM_S.enList('W', &G_WSM);   
  19.     WGM_S.enList('G', &W_SGM);   
  20.     G_WSM.enList('W', &WGM_S);   
  21.     W_SGM.enList('G', &WGM_S);   
  22.     G_WSM.enList('S', &SGM_W);   
  23.     SGM_W.enList('S', &G_WSM);   
  24.     SGM_W.enList('G', &S_WGM);   
  25.     S_WGM.enList('G', &SGM_W);   
  26.     W_SGM.enList('S', &WSM_G);   
  27.     WSM_G.enList('S', &W_SGM);   
  28.     WSM_G.enList('W', &S_WGM);   
  29.     S_WGM.enList('W', &WSM_G);   
  30.     S_WGM.enList('M', &SM_WG);   
  31.     SM_WG.enList('M', &S_WGM);   
  32.     SM_WG.enList('S', &stop);   
  33.     stop.enList('S', &SM_WG);   
  34.     if(start.start("SMWSGMSSS")==&stop) cout<<"过河成功!\n";   
  35.     else cout<<"过河失败!\n";   
  36.     getchar();   
  37.     return 1;   
  38.  }   

四、实验结果

Code:
  1. #include"head.h"   
  2. // 用M 表示人 用W 表示野人 B代表船    
  3. // 初始状态为"BMMMYYY_" 终止状态为 "_BMMMYYY"    
  4. //过河动作可以有五种:人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b    
  5. int main( ){   
  6.     char m[80];   
  7.     State error(0);   
  8.     State start("start");//BMMMYYY_   
  9.     State MMMY_BYY("MMMY_BYY");//1   
  10.     State MMYY_BMY("MMYY_BMY");//2   
  11.     State BMMMYY_Y("BMMMYY_Y");//3   
  12.     State MMM_BYYY("MMM_BYYY");//4   
  13.     State BMMMY_YY("BMMMY_YY");//5   
  14.     State MY_BMMYY("MY_BMMYY");//6   
  15.     State BMMYY_MY("BMMYY_MY");//7   
  16.     State YY_BMMMY("YY_BMMMY");//8   
  17.     State BYYY_MMM("BYYY_MMM");//9   
  18.     State Y_BMMMYY("Y_BMMMYY");//10   
  19.     State BMY_MMYY("BMY_MMYY");//11   
  20.     State BYY_MMMY("BYY_MMMY");//12   
  21.     State stop("stop");//_BMMMYYY   
  22.        
  23.     start.enList('t',&MMMY_BYY);   
  24.     start.enList('b',&MMYY_BMY);   
  25.   
  26.     MMMY_BYY.enList('t',&start);   
  27.     MMMY_BYY.enList('w',&BMMMYY_Y);   
  28.   
  29.     MMYY_BMY.enList('b',&start);   
  30.     MMYY_BMY.enList('s',&BMMMYY_Y);   
  31.        
  32.     BMMMYY_Y.enList('w',&MMMY_BYY);   
  33.     BMMMYY_Y.enList('s',&MMYY_BMY);   
  34.     BMMMYY_Y.enList('t',&MMM_BYYY);   
  35.   
  36.     MMM_BYYY.enList('t',&BMMMYY_Y);   
  37.     MMM_BYYY.enList('w',&BMMMY_YY);   
  38.        
  39.     BMMMY_YY.enList('w',&MMM_BYYY);   
  40.     BMMMY_YY.enList('d',&MY_BMMYY);   
  41.        
  42.     MY_BMMYY.enList('d',&BMMMY_YY);   
  43.     MY_BMMYY.enList('b',&BMMYY_MY);   
  44.        
  45.     BMMYY_MY.enList('b',&MY_BMMYY);   
  46.     BMMYY_MY.enList('d',&YY_BMMMY);   
  47.        
  48.     YY_BMMMY.enList('d',&BMMYY_MY);   
  49.     YY_BMMMY.enList('w',&BYYY_MMM);   
  50.        
  51.     BYYY_MMM.enList('w',&YY_BMMMY);   
  52.     BYYY_MMM.enList('t',&Y_BMMMYY);   
  53.        
  54.     Y_BMMMYY.enList('t',&BYYY_MMM);   
  55.     Y_BMMMYY.enList('s',&BMY_MMYY);   
  56.     Y_BMMMYY.enList('w',&BYY_MMMY);   
  57.     BMY_MMYY.enList('s',&Y_BMMMYY);   
  58.     BMY_MMYY.enList('b',&stop);   
  59.        
  60.     BYY_MMMY.enList('w',&Y_BMMMYY);   
  61.     BYY_MMMY.enList('t',&stop);   
  62.        
  63.     cout<<"人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b\n";   
  64.     cout<<"请输入:\n";    
  65.     cin>>m;   
  66.     getchar();   
  67.     if(start.start(m)==&stop) cout<<"过河成功!\n";   
  68.     else cout<<"过河失败!\n";   
  69.     getchar();   
  70.     return 1;   
  71. }   

 

 

四、实验结果

 

实验二

 

 

一、实验题目

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

二、问题分析

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

 

 

 

 

三、程序代码

源文件lab2.cpp内容

Code:
  1. #include"head.h"   
  2. // 用M 表示人 用W 表示野人 B代表船    
  3. // 初始状态为"BMMMYYY_" 终止状态为 "_BMMMYYY"    
  4. //过河动作可以有五种:人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b    
  5. int main_10( ){   
  6.     char m[80];   
  7.     State error(0);   
  8.     State start("start");//BMMMYYY_   
  9.     State MMMY_BYY("MMMY_BYY");//1   
  10.     State MMYY_BMY("MMYY_BMY");//2   
  11.     State BMMMYY_Y("BMMMYY_Y");//3   
  12.     State MMM_BYYY("MMM_BYYY");//4   
  13.     State BMMMY_YY("BMMMY_YY");//5   
  14.     State MY_BMMYY("MY_BMMYY");//6   
  15.     State BMMYY_MY("BMMYY_MY");//7   
  16.     State YY_BMMMY("YY_BMMMY");//8   
  17.     State BYYY_MMM("BYYY_MMM");//9   
  18.     State Y_BMMMYY("Y_BMMMYY");//10   
  19.     State BMY_MMYY("BMY_MMYY");//11   
  20.     State BYY_MMMY("BYY_MMMY");//12   
  21.     State stop("stop");//_BMMMYYY   
  22.        
  23.     start.enList('t',&MMMY_BYY);   
  24.     start.enList('b',&MMYY_BMY);   
  25.   
  26.     MMMY_BYY.enList('t',&start);   
  27.     MMMY_BYY.enList('w',&BMMMYY_Y);   
  28.   
  29.     MMYY_BMY.enList('b',&start);   
  30.     MMYY_BMY.enList('s',&BMMMYY_Y);   
  31.        
  32.     BMMMYY_Y.enList('w',&MMMY_BYY);   
  33.     BMMMYY_Y.enList('s',&MMYY_BMY);   
  34.     BMMMYY_Y.enList('t',&MMM_BYYY);   
  35.   
  36.     MMM_BYYY.enList('t',&BMMMYY_Y);   
  37.     MMM_BYYY.enList('w',&BMMMY_YY);   
  38.        
  39.     BMMMY_YY.enList('w',&MMM_BYYY);   
  40.     BMMMY_YY.enList('d',&MY_BMMYY);   
  41.        
  42.     MY_BMMYY.enList('d',&BMMMY_YY);   
  43.     MY_BMMYY.enList('b',&BMMYY_MY);   
  44.        
  45.     BMMYY_MY.enList('b',&MY_BMMYY);   
  46.     BMMYY_MY.enList('d',&YY_BMMMY);   
  47.        
  48.     YY_BMMMY.enList('d',&BMMYY_MY);   
  49.     YY_BMMMY.enList('w',&BYYY_MMM);   
  50.        
  51.     BYYY_MMM.enList('w',&YY_BMMMY);   
  52.     BYYY_MMM.enList('t',&Y_BMMMYY);   
  53.        
  54.     Y_BMMMYY.enList('t',&BYYY_MMM);   
  55.     Y_BMMMYY.enList('s',&BMY_MMYY);   
  56.     Y_BMMMYY.enList('w',&BYY_MMMY);   
  57.        
  58.     BMY_MMYY.enList('s',&Y_BMMMYY);   
  59.     BMY_MMYY.enList('b',&stop);   
  60.        
  61.     BYY_MMMY.enList('w',&Y_BMMMYY);   
  62.     BYY_MMMY.enList('t',&stop);   
  63.        
  64.     cout<<"人单独过河s 两个人过河d 野人单独过河w 两个野人过河t人带着野人过河b\n";   
  65.     cout<<"请输入:\n";    
  66.     cin>>m;   
  67.     getchar();   
  68.     if(start.start(m)==&stop) cout<<"过河成功!\n";   
  69.     else cout<<"过河失败!\n";   
  70.        
  71. //  if(start.start("twtwdbdwtwt")==&stop) cout<<"ok\n";   
  72. //  else cout<<"error\n";   
  73. //   
  74. //  if(start.start("bstwdbdwtsb")==&stop) cout<<"ok\n";   
  75. //  else cout<<"error\n";   
  76.   
  77.     getchar();   
  78.     return 1;   
  79. }
分享到:
评论

相关推荐

    eda课设 过河游戏

    【EDA课设 过河游戏】是一个以经典数字游戏“过河”为主题的课程设计项目,主要涉及EDA(电子设计自动化)技术,使用FPGA(Field-Programmable Gate Array,现场可编程门阵列)作为核心硬件平台。在这个设计中,学生...

    商人过河模型代码

    这个代码项目对于理解面向对象编程、事件驱动编程、状态机设计模式以及如何利用图形库进行界面开发都有很好的实践价值。通过分析和修改这段代码,学习者可以深入理解Qt框架,并提高问题解决和算法设计的能力。同时,...

    第十五届“蓝桥杯”STEMA真题(scratch-青蛙过河、巡逻的直升机、栽花 ).pdf

    - **直升机水平移动**:利用循环结构,逐步调整直升机的x坐标实现水平移动。 - **螺旋桨转动效果**:使用循环结合旋转指令,模拟螺旋桨转动。 - **直升机大小变化**:通过循环递减直升机的大小值,使其在移动过程中...

    基于QT_C++中国象棋算法设计与实现源码论文答辩ppt.rar

    7. **深度优先搜索(DFS)或最小最大搜索(Minimax)**:为了实现计算机自动下棋,可以使用这些搜索算法结合Alpha-Beta剪枝,以评估棋局的优劣和预测对手的可能动作。 8. **局面评估函数**:在搜索算法中,需要一个...

    人工智能实验

    实验目的:这是经典的过河方案规划问题,通过本实验的设计与编程实现让学生掌握基于状态空间知识表示方法的一般搜索策略。 实验内容:选择 c、c++、java 等编程语言设计并实现 3 个传教士和 3 个野人的过河方案。 ...

    c语言实现的象棋源码.rar

    在本压缩包“c语言实现的象棋源码.rar”中,包含了一个使用C语言编写的中国象棋程序。这个程序展示了如何用低级编程语言来实现一个复杂的逻辑游戏,如象棋。以下是对该源码中涉及的关键知识点的详细说明: 1. **...

    用C++编写的中国象棋源代码

    在编程领域,用C++实现中国象棋是一项挑战性的任务,它不仅涉及到基础的编程技术,还涉及到算法设计、对象模型构建以及人机交互等多个方面。这篇内容将深度解析这份由教师指导编写的C++中国象棋源代码,帮助读者理解...

    网络安全—期末考题.doc

    - **案例2**:农夫过河问题 - 使用状态图表示不同状态,并通过图搜索找到从初始状态到目标状态的有效路径。 以上是对网络安全期末考试题中的知识点的详细总结,希望能帮助大家更好地理解和掌握相关概念和技术。

    各种EXCEl内置vba制作的游戏

    1. **gmexcopter.txt**:这可能是一个基于直升机飞行的小游戏,通过VBA编程实现游戏逻辑。玩家可能需要控制直升机避开障碍物,同时收集奖励。VBA在这里用于处理游戏的计分系统、碰撞检测、游戏循环和用户输入。 2. ...

    2023最新面试合集大厂篇-百度篇

    32. **警察囚徒过河问题**:典型的约束问题,需要考虑各种组合可能性。 33. **找出热门URL**:可以使用布隆过滤器快速排除不在集合中的URL,然后用哈希表统计频率。 34. **兄弟单词**:使用回溯或动态规划,交换...

    基于QT的象棋游戏

    通过套接字(socket)技术,客户端和服务器可以交换游戏状态,实现远程对战。玩家可以在各自的设备上操作,游戏状态实时同步。 四、算法 在象棋游戏中,算法起着至关重要的作用,主要包括以下几点: 1. 棋盘逻辑:...

Global site tag (gtag.js) - Google Analytics