问检查一个数字是否能被3整除

EN

嘿嘿

LSB的状态表：

S I S' O
0 0 0  1
0 1 1  0
1 0 2  0
1 1 0  1
2 0 1  0
2 1 2  0

说明:0可以被3整除。0 << 1 + 0 = 0。如果是S == 0，请重复使用S = (S << 1 + I) % 3和O = 1。

MSB的状态表：

S I S' O
0 0 0  1
0 1 2  0
1 0 1  0
1 1 0  1
2 0 2  0
2 1 1  0

说明:0可以被3整除。0 >> 1 + 0 = 0。如果是S == 0，请重复使用S = (S >> 1 + I) % 3和O = 1。

S'与上面不同，但O的工作原理相同，因为对于相同的情况(00和11)，S'是0。由于O在两种情况下是相同的，O_LSB = O_MSB，所以要使MSB与LSB一样短，或者反之亦然，只需使用两者中最短的一个即可。

这里..。一些新的东西。如何检查任意长度的二进制数(即使是数千位数)是否能被3整除。

​

​

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

从照片上看。

当你得到一个1或0的时候，如果数字在这个圆圈内，你就会留在那个圆圈里。，，

1. ，

，

1. ，当你得到一个1或一个零时，如果数字在这个圆圈内，你就会留在那个圆圈里。但是，如果数字在一条线上，那么您将穿过这条线。
2. 重复步骤2，直到所有数字都被占用为止。
3. 如果您最终到达双圆圈，则二进制数可以被3整除。

你也可以用它来生成被3整除的数字，我不认为它很难转换成一个电路。

1个使用图表的示例...

1100000000000101111111111111101可被3整除(再次以双圆结束)

你自己试试吧。

在将二进制数转换为以10为基数的数字时，您也可以使用类似的技巧执行MOD 10。(10个圆圈，每个圆圈双圈，表示模0到9的值)

EDIT:这是用于从左到右的数字，修改有限状态机以接受相反的语言并不难。

注意:图的ASCII码表示中的 ()表示单个圆，而(())表示双圆。在有限状态机中，这些状态称为状态，双圆是接受状态(表示最终可被3整除的状态)。

你需要使用算术模3来做所有的计算。

MSB：

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

LSB：

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

这是大体的想法。

现在，你要做的就是理解，为什么，，这是正确的。

是的，你自己做作业;)