使用正则判断n能否被3整除
根据整除性构建DFA(确定有限自动状态机),再根据DFA构建正则(Kleen算法)
我们从高位读取字符串,并将余数作为状态,有如下状态转移表: X |'0''1' 0 | 0 1 1 | 2 0 2 | 1 2 (X表示 状态\当前字符) 比如说状态是2,说明当前数字除3余2,那么当前字符是'0'时,余数自然是1,应该转移到1状态
DFA如下:
初始状态是0,我们只要判断终结状态是否为0即可
观察图中的一个自环和一个0-1-2-1-0的大环,我们可以写出两种正则
0*
1(01*0)*1
故得到 (0 | 1(01*0)*1)*
for(var i=1;i<100;i++)
if(!/^(0|1(01*0)*1)*$/.test(Number(3*i).toString(2))) console.log(i)//undefined
https://en.wikipedia.org/wiki/Kleene%27s_algorithm https://zhidao.baidu.com/question/1383837207982172220.html Algorithm 4th P518