有限状态机

有限状态机 在计算机中是一份可以运动的代码。

这份代码有 有限个状态，里面的变量只能有 有限个状态，比如：

// 定义枚举类型，共 9 种状态
typedef enum{
	S1,	
	S2,		
	S3,		
	S4,		
	S5,		
	S6,
	S7,
	S8,
	S9,
}STATE;

STATE cur_s = S1;
// 枚举类型的变量 cur_s 就只有 有限个状态(9个)。

另外有限状态机能从外部接受信号和信息输入，接受后会综合考虑当前自己的状态和用户输入的信息跳转到另一个状态。

有限状态机分为 Moore 和 Mealy 型。

Moore：输出只与当前状态有关(与输入无关)。

Mealy：输出结合了当前状态、输入信号，状态机接收到一个输入信号需要跳转为下一个状态，下一个状态具体是 哪个状态 ，取决于 当前状态 和 输入值。

常用的有限状态机考虑的：当前状态、外部输入、下一个状态，也就是 Mealy 型。

用 C 实现一个简单的有限状态机，最好的取材是地址。

XX省 XX市 XX区 XX街道 XX号

如果在 输入省前 先输入 市 ，状态机就归零，在输入街道前 输入号也是如此。

简单起见，重在理解。

把上面的地址 换为 一串数字，要按照顺序输入 41739364 才能到达状态 S9，结束程序。

看一下代码吧，思想实现大概就是这样。

#include<stdio.h>
// 俩个宏定义，想少写点代码，为了可读性您可以补上。
#define S(n) { cur_s = S##n, print(cur_s); }    // 如果输入匹配，状态加一
#define Than else{ cur_s = S1; }                // 否则，状态回到 S1

typedef enum{
	S1,	
	S2,		
	S3,		
	S4,		
	S5,		
	S6,
	S7,
	S8,
	S9,
}STATE;

void print(STATE str)                            // 打印函数，提示也可以不用
{
 	if(  str == S1 )
	    puts("等级归零，重新输入");
	 else 
	    puts("等级+1");
}

int main(int argc, const char *argv[])
{
	puts("input num: ");
	STATE cur_s = S1;                        // 起始状态
	int n;
	while(1){	
		scanf("%d", &n);
		
		switch(cur_s)                    // 有限状态机的代码实现一般采用 switch 语句 
		{
			case S1:    if( n == 4 ) S(2) Than break;
			case S2:    if( n == 1 ) S(3) Than break;
			case S3:    if( n == 7 ) S(4) Than break;
			case S4:    if( n == 3 ) S(5) Than break;
			case S5:    if( n == 9 ) S(6) Than break;
			case S6:    if( n == 3 ) S(7) Than break;
			case S7:    if( n == 6 ) S(8) Than break;
			case S8:    if( n == 4 ) S(9) Than break;
			default:	S(0)
		}
		
		
	}

	return 0;
}

如果只使用 第一个宏 S(n) ，输入数字不对应时，还可以在原状态一直输入下一个状态；如果俩个宏一起使用，那么中途只要有一个数字匹配不上，状态机的状态初始化，需要又从头开始输入。