作者neverfly (neverfly)
站内Prob_Solve
标题[问题] 从二进位判断数字是否被5整除
时间Wed Oct 1 14:08:26 2008
我想要建一个automata，可以输入二进位的值，
如果该值能被5整除就接受。
但是我想了很久，实在想不出来二进位下，能被5整除的数有什麽特性。
列了前几个出来
101 1010 1111 10100 11001 11110 100011 101000
101101 110010 110111 111100 1000001 1000110 1001011 1010000
1010101 1011010 1011111 1100100 ……
只发现了有每八个，末三码会重覆这个特性，
不过似乎还是不能直接检查出来一串二进位的值是否被5整除。
请问有人能解决这个问题吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.169.80.216
1F：推 ledia:被五除余一, 後面多一个 0 就会变余二, 多一个 1 则是余三 10/01 14:21
2F：→ ledia:利用 2n 或 2n+1 mod 5 去设计你的 transition 10/01 14:22
3F：推 Pash77:每 2 bits 分开，对 5 的余数分别是 -1,+1,-1,+1 10/01 19:43
4F：→ Pash77:把 +1 / -1 分别加总，看差值是不是 5 的倍数 10/01 19:43