如果检查一数字是可分割的，由3[封闭]

StackOverflow https://stackoverflow.com/questions/844867

  •  20-08-2019
  •  | 
  •  

题

编写代码，以确定如果一个数字是可分割的，由3.输入到的函数是一个 单 比特,0或1，输出应在1如果数迄今为止收到的二元表示的数除以3，否则为零。

实例：

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

这是根据采访的问题。我问一个关于绘制的逻辑门，但由于这是计算器，我会接受任何编码语言。加分的硬件执行(电气电子工程师学会等)。

A部分(简单): 首先输入MSB。

B部分(有点困难): 首先输入低位.

C部分(困难): 哪一个是较快和较小，(a)或(b)?(未从理论上讲，在大-O意义的，但实际上更快的/小。) 现在慢/更大的之一，并把它作为快速少作为更快的/小的一个。

有帮助吗？

解决方案

嘿

有关国家表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是由三个整除。 0 << 1 + 0 = 0。重复使用如果S = (S << 1 + I) % 3。O = 1和S == 0

有关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是由三个整除。 0 >> 1 + 0 = 0。重复使用如果S = (S >> 1 + I) % 3。O = 1和S == 0

S'是与上述不同，但是，输出工作是相同的，因为S'是0对于相同的情况下（00和11）。由于O为在两种情况下是相同的，O_LSB = O_MSB，所以使MSB短LSB，或反之亦然，只是用最短两者。

其他提示

有用于确定一个数是否是11的倍数，通过交替地加和减其十进制数字的相当知名的特技。如果你在最后的数字是11的倍数，那么你开始走出数也是11的倍数：

47278    4 - 7 + 2 - 7 + 8 = 0, multiple of 11     (47278 = 11 * 4298)
52214    5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)

我们可以使用同样的伎俩二进制数。二进制数是3的倍数，当且仅当它的比特的交替总和也为3的倍数：

4   = 100       1 - 0 + 0 = 1, not multiple of 3
6   = 110       1 - 1 + 0 = 0, multiple of 3
78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3
109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

这没有什么区别，你是否开始与MSB或者LSB，所以下面的Python功能同样适用于这两种情况。它需要返回在时间位一个迭代器。图1和2，而不是1和-1之间交替multiplier避免采取负数的模

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

    for bit in iterator:
        accumulator = (accumulator + bit * multiplier) % 3
        multiplier = 3 - multiplier

    return accumulator == 0

这里...新的东西...如何检查，如果一个二进制数量的任何长度(即使成千上万的数字)是可分割的，由3.

divisible-by-3 state machine

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

从图片。

  1. 你开始在双圆。
  2. 当你获得一个或一个零，如果该数字是圈子里面，然后你留在那个圈子。但是，如果该数字是在一条线，然后你旅行跨线。
  3. 重复步骤二中，直至所有数字是力消耗.
  4. 如果你终于结束了在双圆随后的二进制数字是可分割的，由3.

你也可以使用这个用于产生数字可分割的，由3.我不会像这将是难以将其转换成电路。

1例如使用图表...

11000000000001011111111111101是可分割的，由3(结束了在双再次圆)

自己试试看。

你也可以做类似的技巧，用于执行国防部10个，因为当的二进制转换的数字为基10号码。(10圈，每增加一倍上空盘旋，并表示值的0至9造成的模)

编辑： 这是对数字运行的左右，它不是硬要修改的有限状态机的接受相反的语言虽然。

注： 在ASCII表示图()表示一个单一的圈子，(())表示双圆。在有限国家机器，这些被称为国家和双圆圈是接受国(中国家，这意味着其最终可分割的，由3)

下面是一个简单的方法通过手去做。 由于1 = 2 2 MOD 3，我们得到1 = 2 2n个 MOD 3对于每个正整数。 此外2 = 2 2n + 1个 MOD 3.因此，人们可确定的整数是被3整除通过在奇数位位置计数为1点的位，乘以2这个号码，添加1-数在偶数位posistions位将它们添加到结果，并检查结果是被3整除。

实施例：57 <子> 10 = 111001 <子> 2 。 有2位在奇数位置，并且在偶数位置2位。 2 * 2 + 2 = 6由3整除。因此57是被3整除。

下面还对解决问题℃的思想）。如果一个反相的二进制整数的位顺序，那么所有的位保持在偶/奇数位置或所有位改变。因此反相整数n结果的比特的顺序被一个整数，它是被3整除当且仅当n为被3整除因此，对于问题的任何解决方案）的工作原理，而不用于问题B的变化），并且反之亦然。嗯，也许这可以帮助找出哪种方法更快...

您需要使用算术模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

这是一般的想法...

现在，你的一部分是理解的为什么这是正确的。

和是的，做作业自己;）

我们的想法是，该数量可能会任意长，这意味着你不能在这里使用mod 3，因为你的数字将增长超出你的整数类的能力。

我们的想法是要注意发生了什么号码。如果您要添加位的权利，你实际上做的是左移一位并添加新的位。

左移位相同乘以2，并加入新的比特要么加入0或1。假设我们从0开始，我们可以这样做递归基于所述模3的最后一个数字的。

last | input || next | example
------------------------------------
0    | 0     || 0    | 0 * 2 + 0 = 0
0    | 1     || 1    | 0 * 2 + 1 = 1
1    | 0     || 2    | 1 * 2 + 0 = 2
1    | 1     || 0    | 1 * 2 + 1 = 0 (= 3 mod 3)
2    | 0     || 1    | 2 * 2 + 0 = 1 (= 4 mod 3)
2    | 1     || 2    | 2 * 2 + 1 = 2 (= 5 mod 3)

现在让我们来看看，当你增添几分向左发生了什么。首先，请注意：

2 2n个 MOD 3 = 1

和

2 2n + 1个 MOD 3 = 2

现在我们必须要么添加1或2基于该模如果当前迭代是奇数还是偶数。

last | n is even? | input || next | example
-------------------------------------------
d/c  | don't care | 0     || last | last + 0*2^n = last
0    | yes        | 1     || 0    | 0 + 1*2^n = 1 (= 2^n mod 3)
0    | no         | 1     || 0    | 0 + 1*2^n = 2 (= 2^n mod 3)
1    | yes        | 1     || 0    | 1 + 1*2^n = 2
1    | no         | 1     || 0    | 1 + 1*2^n = 0 (= 3 mod 3)
1    | yes        | 1     || 0    | 2 + 1*2^n = 0
1    | no         | 1     || 0    | 2 + 1*2^n = 1

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

不应该最后输入来12，或我误解的问题？

其实LSB方法实际上使这个容易。在C：

MSB方法：

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
  unsigned value = 0;
  char *p = input;
  if (*p == '1') {
    value &= 1;
  }
  p++;
  while (*p) {
    if (*p != ',') {
      value <<= 1;
      if (*p == '1') {
        ret &= 1;
      }
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

LSB方法：

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
  unsigned value = 0;
  unsigned mask = 1;
  char *p = input;
  while (*p) {
    if (*p != ',') {
      if (*p == '1') {
        value &= mask;
      }
      mask <<= 1;
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

我个人有很难相信这些中的一个将是显著不同的其他

我觉得弥敦道费尔曼是在正确的轨道上部分和B部分（除B需要一个额外的一块状态：你需要跟踪，如果你的数位是奇数还是偶数的）。

我认为对于C部分诀窍是否定在每一步last值。即0变为0，1前进到2和2变为1。

一个数字是可分割的，由3如果这个数字是可分割的，由3.

所以你可以添加的数字，并得到的总和：

  • 如果总和大于或等于10使用同样的方法
  • 如果这是3、第6、第9然后它可分割的，
  • 如果总是不同于3、6、第9那么它的不可分割的，
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top