闲聊技术贴，关于状态机,该如何处理

闲聊技术贴，关于状态机
状态机很重要，相当的重要
至少我知道有两个比较好的库，架构的原理都是状态机的原理，OPENGL LUA
运动控制软件当中很多架构也都是基于状态机的架构，或者说在运动控制软件当中没有用到状态机的很少
或许仅仅是你没有意识到而已
而且很多支持脚本的系统也都是基于状态机的
=====================================================================
现在谈状态机，内容不限，随便
大家可以举例现实当中的应用，原理，感想，亦或是其它
======================================================
本人比较关心的是，到底什么才是状态机？
大家可以去看编译原理上讲的状态机，和最开始的纸带存储器的状态机是一样的，但是明显的OPENGL LUA所使用的
状态机的概念又有所不同，这个问题困扰我很久了
=====================================================
今天的话题，只要是基于状态机的，你想谈什么随便
理解最深最好的那个人100分相送，剩下100分给大家发，不知道我的级别是否还能加分（好像最多是200）如果可以我还会加

------解决方案--------------------
其实我以前想过写出这么一个东西来。
state<UserInfo> _s;
//define state mapping
s.setCondition(lambda, _otherState);

//use the states
Singleton<StateManager>::Instance()->getState(lambda);

其中lambda表示一个表达式，可以是简单的表达式，也可以是一个函数对象什么的。
StateManager帮你维护状态的变迁。
可以实现不？

------解决方案--------------------
有一道acm题:
http://acm.timus.ru/problem.aspx?space=1&num=1102

1102. Strange Dialog

One entity named "one" tells with his friend "puton" and their conversation is interesting. "One" can say words "out" and "output", besides he calls his friend by name. "Puton" can say words "in", "input" and "one". They understand each other perfect and even write dialogue in strings without spaces.
You have N strings. Find which of them are dialogues.

Input

In the first line of input there is one non-negative integer N ≤ 1000. Next N lines contain non-empty strings. Each string consists of small Latin letters. Total length of all strings is no more than 107 characters.

Output

Output consists of N lines. Line contains word "YES", if string is some dialogue of "one" and "puton", otherwise "NO".

如果使用状态机进行解答就相当简单:

C/C++ code

#include <stdio.h>

void main()
{
  const int a[] = {0,0,0,0,1,0,0,0,2,0,0,0,0,3,4,5,0,0,0,6,7,0,0,0,0,0};
  const int b[][8] =
  {
    //*  e  i  n  o  p  t  u
    {15,15, 7,15, 4,11,15,15}, //  0 
    {15,15, 7,15, 4, 8,15,15}, //  1 
    {15,15, 7,15,10,11,15,15}, //  2 
    {15, 0, 7,15, 4,11,15,15}, //  3 
    {15,15,15, 5,15,15,15, 6}, //  4 
    {15, 0,15,15,15,15,15,15}, //  5 
    {15,15,15,15,15,15, 1,15}, //  6 
    {15,15,15, 1,15,15,15,15}, //  7 
    {15,15,15,15,15,15,15, 9}, //  8 
    {15,15,15,15,15,15, 2,15}, //  9 
    {15,15,15, 3,15,15,15, 6}, // 10 
    {15,15,15,15,15,15,15,12}, // 11 
    {15,15,15,15,15,15,13,15}, // 12 
    {15,15,15,15,14,15,15,15}, // 13
    {15,15,15, 0,15,15,15,15}  // 14
  };                             
  int c, n, s;
  scanf("%d\n", &n);
  while (n--)
  {
    for (s = 0; (c = getchar()) != 10;) if (s < 15) s = b[s][a[c - 97]];
    printf(s < 4 ? "YES\n" : "NO\n");
  }
}

------解决方案--------------------

状态机是一个非常有意思的主题。他可以非常简单，也可以非常复杂。最简单的一个指示变量就可以叫做一个状态机，这也是我们最常用的。但是一旦遇到复杂的情况，这种方式就力不从心了，最终的结果就是到处是状态变量，到处是条件判断，导致程序难以维护，耦合度极高。
一般的应用用不到复杂的状态机，所以我们平时见到的复杂的状态机比较少。编译器算是我们最容易想到的复杂状态机应用。我经历过一个项目其中也用到了比较复杂的状态机，这是一个UI项目，使用WPF和MVVM架构设计。前端UI绑定到逻辑层上暴露的数据接口，逻辑层内部实现了一个状态机，是用Enterprise Architect先画出状态机，然后转化成代码。使用该状态机，实现了各种输入和输出之间的解耦。建议想熟悉状态机设计的人去参考一下Enterprise Architect的状态机设计，结合具体的项目，一定受益匪浅。

------解决方案--------------------

惭愧啊，对软件框架我没有了解，所以说不出什么来。

我只是在实际做题中用到了状态机，觉得这个例子不错，短小、精简、高效，所以拿出来献丑了，见笑。


另外，字符串匹配中著名的KMP(Knuth-Morris-Pratt)算法也是利用状态机的，这已经是相当成熟的算法了，用KMP做关键字在网上一搜一大堆，就不再多说了。


[英]罗杰·彭罗斯的《皇帝新脑》第二章 算法和图灵机，其中论述的“普适图灵机”也相当有意思，也涉及到状态机的概念。

闲聊技术贴，关于状态机,该如何处理

相关推荐