作者yauhh (举杯邀鼠长 共饮长江奶)
看板Prob_Solve
标题Re: [问题] 从二进位判断数字是否被5整除
时间Fri Oct 3 22:10:13 2008
※ 引述《neverfly (neverfly)》之铭言：
: 我想要建一个automata，可以输入二进位的值，
: 如果该值能被5整除就接受。
: 但是我想了很久，实在想不出来二进位下，能被5整除的数有什麽特性。
: 列了前几个出来
: 101 1010 1111 10100 11001 11110 100011 101000
: 101101 110010 110111 111100 1000001 1000110 1001011 1010000
: 1010101 1011010 1011111 1100100 ……
: 只发现了有每八个，末三码会重覆这个特性，
: 不过似乎还是不能直接检查出来一串二进位的值是否被5整除。
: 请问有人能解决这个问题吗？
我的想法:
由高位往低位方向读资料,例如 11001 = 25, 读 1 -> 1 -> 0 -> 0 -> 1 顺序.
状态分为接受与不接受,
此外,状态附带一个 n 值代表根据已经读入的部份二进位数值决定的十进位数值,
例如, 对 11001 已读入 110 时, 状态的 n 值是 6.
输入的意义是,遇到 0, 代表 n*2; 遇到 1, 代表 n*2+1
Transition 有三个项目要关心: 1) 读入的二进位数字, 2) 状态 n 的求值,
3) 结果接受或不接受, 以下用 (t1, t2, t3) 表达三个项目.
Automata为:
(1, n, F)
[unacceptable] <------(1)-------- S:[accepted]
|^ |^ | | ^ ^ |^
|| || +-----------(0)-------------+ | ||
|| || | (0, n*2, (n*2)%5 = 0) | ||
Ｕ || +-------------(1)-----------+ ||
(0, n*2, (n*2)%5 /= 0) (1, n*2+1, (n*2+1)%5 = 0)
|| ||
Ｕ Ｕ
(1, n*2+1, (n*2+1)%5 /= 0) (0, n, T)
S是起动状态, 起动时 n = 0.
这个automata有下列特性:
1. 0 整除 5.
2. 任一unacceptable状态遇到下一个 0 一定是unacceptable. (不确定)
也就是,任一unacceptable状态只有遇到下一个 1 才可能accepted.
3. 任一accepted状态遇到下一个 0 一定是accepted.
4. 任一accepted状态遇到下一个 1 一定是unacceptable.
(以上特性是画出具体的 0,1,2,...,25 状态机而观察到的)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.111.154
※ 编辑: yauhh 来自: 218.160.111.154 (10/03 22:18)
1F：推 FRAXIS:用5个state 分别代表现在读入的字串除5的余数为 0~4 就好啦 10/04 07:00
2F：→ yauhh:不同的概念会画出不同的automata 10/04 10:45
3F：→ yauhh:重点是你要说明一套automata能不能讲得完整,而不必考虑是否 10/04 10:46
4F：→ yauhh:符合别人的概念 10/04 10:46
※ 编辑: yauhh 来自: 218.160.111.154 (10/04 10:55)
5F：→ yauhh:用5个状态的麻烦是,你一个状态可能连到其他四个状态,传递线 10/04 11:15
6F：→ yauhh:要画很多; 而我的只判断留在原地或跳别的状态,传递线很少. 10/04 11:17
※ 编辑: yauhh 来自: 218.160.111.154 (10/04 11:21)
7F：推 ledia:这不是 automata 了吧, 多了 n 10/04 21:51
8F：→ yauhh:就当作side-effect好了,本来没多严谨去想这东西 10/04 22:34