作者march20 ()
看板Prob_Solve
标题Re: [问题] 从二进位判断数字是否被5整除
时间Sat Oct 4 18:02:08 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整除。
: 请问有人能解决这个问题吗？
一个 5-state finite automaton 应该可以解决:
States : {s_i | 0 <= i < 5}: 目前输入 mod 5 余数为 i
Alphabet : {0, 1}
Start State : s_0
Accept States: {s_0 }
transition function :
| 0 | 1
---+---+----
s_0|s_0|s_1
s_1|s_2|s_3
s_2|s_4|s_0
s_3|s_1|s_2
s_4|s_3|s_4
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.136.255.51
※ 编辑: march20 来自: 71.136.255.51 (10/04 18:10)
1F：→ march20:嗯, 如果 digits 是从右到左输入会麻烦得多 @@ 10/04 18:13
2F：推 yauhh:原来是这样的处理法 10/04 20:20
3F：→ neverfly:搞懂了，非常感谢你的说明 10/06 14:48