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

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

www.MyException.Cn  网友分享于:2013-01-14  浏览:60次

------解决方案--------------------
复杂状态机的设计大体有两种方法,一种是表格映射,即把状态抽象为一个表格,表格中的每个元素定义了状态的跃迁规则。另一种是面向对象方法,即把所有状态抽象为一个个的对象,内部定义了状态的跃迁规则,并有事件触发规则等等来跟外界交互,上面说的Enterprise Architect设计的状态机就属于这种。这里只能这样简单介绍了,具体的要自己做一些具体的项目来体会。
------解决方案--------------------
这话题还真大!

状态机的应用太广了,
个人觉得编译和人工智能领域用的最多。

去年看了些关于抽象状态机(Abstract State Machines,ASM)的东西。主要应用于软件规约。可以看看微软的AsmL,可以在Word中直接使用。ASM应该算是软件领域比较前沿的东西。


抽象状态机的基本思想可以追溯到上个世纪80年代.ASM的发明者Yuri Gurevich从数学领域转到计算机领域发现这样的现象:一个程序语言在不同的编译器下有着不同的编译.这就存在一个问题:究竟一个程序语言的确切语义是什么?

为了上面的问题,Yuri Gurevich进行研究的初衷是:(1)为Church.Turing论题引入资源边界的限制;(2)采用动态结构(Dynamic structures)定义更为抽象的计算设备.Yuri Gurevich从数学中得到了启迪,任何静态的数学实体,都可以表示为一阶结构,因而算法的每个状态为一阶结构.计算(Computation)就是状态的进化(Evolving).可以容易的用一个函数来表示一个关系,使得一阶结构中可以只含有函数,而只有函数运算的结构在泛代数(Universal Algebras)中称为代数.因此这种模型最初被分别称为动态结构(Dynamic Structures),动态代数(Dynamic Algebras),以及进化代数(=Evolving Algebras).最终,通过多年的研究,人们发现进化代数实际上是Dj.jl(stra的抽象机(Abstract Machine)的基本概念和利用Tarski的结构作为一般的抽象状态(Abstract States)的基本思想的完美结合,最终称为抽象状态机.所以ASM=Abstract State+Abstract Machine.

目前,ASM已经从一种思想发展成一种成熟的模型,一种语言,一种被国际标准化组织承认的、在软件和硬件规约中广泛使用的工具.同时ASM的工业用软件开发环境已经初露端倪,并且已经得到成功的运用.值得一提的是,在Microsoft的大力支持和推动下,已经产生了ASM Language(即AsmL并整合到了.Net开发环境中.
------解决方案--------------------
ASML主要用于软件开发前的模型测试
http://research.microsoft.com/en-us/projects/asml/
------解决方案--------------------
我以前写过一篇文章,讨论状态机在IVR设计中的应用,当然,我是否定它的,拙文在这里,“从历史角度再论‘状态机’”:
http://blog.csdn.net/bluesen/archive/2006/05/18/744749.aspx
------解决方案--------------------
状态机属于计算理论的范畴,lz可以去看看相关的书籍,从最简单的DFA到TM,状态机总是与它的输入及语言相关,这都是在一块儿的,关于这方面的知识我推荐一本书《计算理论导引》,翻译的很好,习题也很好。
------解决方案--------------------
状态机(FSM)在通信系统协议方面应用最为广泛
------解决方案--------------------
我也来一个用DFA解决一个ACM中的计数问题的代码
在只有一个数字和有两个数字的情况下用了不同的算法
后者是用DFA
Description

A positive number M contains another number N, when N is a substring of M in decimal.
Such as 12 contains 12; 121 contains 12; 213 contains 13; but 102 doesn't contain 12.

Now given a positive N, just calculate the number of all the numbers that contain N in [a,b].

Input

There are several test cases,each contains three numbers:N,a,b( 1 ≤ N < 100,1 ≤ a < b ≤ 2^30).

Output

The number of the numbers.

Sample Input

13 13 1350

Sample Output

84

Source

htam60@joj

C/C++ code
#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;


#define    FILL(a, v) memset(a, v, sizeof(a))
#define    FILLN(a, v, n) memset(a, v, sizeof(a[0]) * n)

#define    INPUT1(x) int x;scanf("%d", &x)
#define    INPUT2(x, y) int x, y;scanf("%d%d", &x, &y)
#define    INPUT3(x, y, z) int x, y, z;scanf("%d%d%d", &x, &y, &z)
#define    INPUTARRAY(arr, begin, end) for (int i = begin; i < end; ++i) scanf("%d", arr+i);

#define    FOR(v, begin, end) for (int v = begin; v < end; ++v)
#define    FORTO(v, begin, last) for (int v = beign; v <= last; ++v)
#define    FORDOWNTO(v, begin, last) for (int v = begin; v >= last; --v)
#define    FOREVER for (;;)

#define    TWO(i) (1<<i)

typedef long long int64;

inline int ExistSingle(int n, int x)
{
    int dig[15], curr = 0, last = 0;
    int t = n;
    for (; n; n /= 10)
    {
        int d = n % 10;
        if (d < x) dig[curr++] = d;
        else if (d > x) dig[curr++] = d-1;
        else
        {
            dig[curr] = d-1;
            for (; last < curr; ++last) dig[last] = 8;
            ++curr;
        }
    }
    int ans = 0, b = 1;
    for (int i = 0; i < curr; ++i)
    {
        ans += dig[i] * b;
        b *= 9;
    }
    return t - ans;
}

int solve_single(int n, int beg, int end)
{
    return ExistSingle(end, n) - ExistSingle(beg-1, n);
}

inline int ExistDouble(int n, int (*dfa)[10], int (*cnt)[3])
{
    if (n < 10) return 0;
    int dig[15], len = 0;
    for (; n; n /= 10) dig[len++] = n % 10;
    --len;
    int ans = 0;
    int state = 0;
    for (; len >= 0; --len)
    {
        FOR (j, 0, dig[len]) ans += cnt[len][dfa[state][j]];
        state = dfa[state][dig[len]];
    }
    return ans + cnt[state][0];
}
int solve_double(int n, int beg, int end)
{
    int first = n / 10, second = n % 10;
    int dfa[3][10] = {0};
    for (int i = 0; i < 10; ++i) dfa[2][i] = 2;
    dfa[0][first] = 1, dfa[1][second] = 2;
    if (first != second) dfa[1][first] = 1;
    int cnt[13][3] = {0};
    cnt[0][2] = 1;
    FOR (i, 1, 12) FOR (j, 0, 3) FOR (k, 0, 10) cnt[i][j] += cnt[i-1][dfa[j][k]];
    return ExistDouble(end, dfa, cnt) - ExistDouble(beg-1, dfa, cnt);
}
int main()
{
    int n, i, j;
    while (scanf("%d%d%d", &n, &i, &j) == 3)
    {
        if (n < 10) printf("%d\n", solve_single(n, i, j));
        else printf("%d\n", solve_double(n, i, j));
    }
    return 0;
}

文章评论

漫画:程序员的工作
漫画:程序员的工作
程序员最害怕的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 版权所有