作者zzzzzz413 (纬~~~~zzz)
看板Prob_Solve
标题Re: [问题] 从二进位判断数字是否被5整除
时间Tue Feb 14 05:55:27 2017
★【交易方式】:面交为主
【保存状况】:全新未拆为主
【地 区】:新竹市或园区可面交
【附 注】:希望能提供发票或是保固注册的资讯(如还未注册之类),谢谢※ 引述《march20 ()》之铭言:
: ※ 引述《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), 来自: 62.110.192.134
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1487022929.A.850.html
1F:推 pinner: wtf 02/14 21:04
2F:→ JameC: 三小 02/22 16:11
3F:→ pttworld: 末三位是101或000 02/25 10:10
4F:→ pttworld: 楼上解法不行,再想过。 02/25 10:12
5F:推 longlongint: 32bit暴力尻逻辑匝吧 03/01 00:01
6F:→ longlongint: 但是bit变多就没用了 呵呵 03/01 00:01
7F:→ longlongint: 比较好的解 你原文里面就有了 03/01 00:03