谈谈状态机

正文

请到「今天看啥」查看全文

对于这个简单的问题，大家一眼都能看出，可能存在四种状态。二进制串包含：

1. 偶数个 0 和偶数个 1（记作 EE）

2. 偶数个 0 和奇数个 1（记作 EO）

3. 奇数个 0 和偶数个 1（记作 OE）

4. 奇数个 0 和奇数个 1（记作 OO）

FSM 初始化的状态是 EE，一个 bit 都没处理，0 和 1 都是偶数个。FSM 的接受状态是 EO。如果最终到达这个状态，那么处理成功。

我们很容易能画出这样的状态机：

手起刀落，马到功成。简单地有点侮辱你的智商。

来个难的吧 —— 难到那种可能你抓破头皮喊破喉咙也找不到优雅的解法的问题。

请听题：判断一个 binary string 是否能被 3 整除。

这个问题合法的输入有：11，110，1001，1100，1111，...

不合法的输入一大堆，光看输入似乎看不出什么规律。所以你不可能用两个状态（可以整除/不可以整除）来描述。

这里要注意，FSM 很傻，对于输入，只能一个单元一个单元处理（在这里一个单元是一个 bit），你既不能吃着碗里的去看锅里的（偷看后面输入），也不能吃着碗里的，把胃里的吐出来重新咀嚼（回溯处理过的输入）。你能依赖的，只有当前所处的状态，以及当前的输入。

光说不练假把式，我们来搞点输入试一试。

如果第一个输入是 1，那么它不能被 3 整除。商 0 余 1。一个数能不能被整除，关键看余数是否为 0。除了 0 之外，这里余数可能的取值还有 1 和 2。我们试试把状态应该设置为 0，1，2，看看是否有解。这里 0 是接受状态，也是初始状态。OK，从初始状态 0 起，输入是 1，那么状态迁移到 1。

如果第二个输入是 0，也就是说现在看到的串是 10，10 和 1 的关系是什么？ 进位 ！二进制逢二进一，所以相当于 被除数 乘了 2。被除数乘 2，相当于余数乘 2 再模除数（这个我就不证明了）。

请到「今天看啥」查看全文