MyException - 我的异常网
当前位置:我的异常网» VC/MFC » 闲聊技术贴,关于状态机,该如何处理

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

www.myexceptions.net  网友分享于:2013-01-14  浏览:60次
闲聊技术贴,关于状态机
状态机很重要,相当的重要
至少我知道有两个比较好的库,架构的原理都是状态机的原理,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做关键字在网上一搜一大堆,就不再多说了。


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

文章评论

漫画:程序员的工作
漫画:程序员的工作
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
10个调试和排错的小建议
10个调试和排错的小建议
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
中美印日四国程序员比较
中美印日四国程序员比较
那些争议最大的编程观点
那些争议最大的编程观点
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
为什么程序员都是夜猫子
为什么程序员都是夜猫子
我是如何打败拖延症的
我是如何打败拖延症的
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员都该阅读的书
程序员都该阅读的书
鲜为人知的编程真相
鲜为人知的编程真相
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
旅行,写作,编程
旅行,写作,编程
代码女神横空出世
代码女神横空出世
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
编程语言是女人
编程语言是女人
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员的鄙视链
程序员的鄙视链
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员必看的十大电影
程序员必看的十大电影
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
我的丈夫是个程序员
我的丈夫是个程序员
每天工作4小时的程序员
每天工作4小时的程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有