Comprobar si un número es divisible por 3 [cerrado]

https://stackoverflow.com/questions/844867

20-08-2019
|

Pregunta

Escribir código para determinar si un número es divisible por 3.La entrada a la función es un solo bit 0 o 1, y la salida debe ser de 1 si el número recibido hasta el momento es la representación binaria de un número divisible por 3, de lo contrario cero.

Ejemplos:

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

Esto se basa en una pregunta de la entrevista.Me pide un dibujo de las puertas de la lógica, pero ya que este es stackoverflow, voy a aceptar cualquier lenguaje de programación.Puntos de bonificación para una implementación de hardware (verilog etc).

La parte a (fácil): Primera entrada es el MSB.

La parte b (un poco más): Primera entrada es el LSB.

La parte c (difícil): Que es más rápido y más pequeño, (a) o (b)?(No teóricamente en el Big-O sentido, pero en la práctica más rápido/más pequeño.) Ahora toma el más lento/más grande y que sea tan rápido/pequeño como el más rápido/más pequeño.

Solución

En la tabla de estado para LSB:

Explicación:0 es divisible por tres. 0 << 1 + 0 = 0.Repita con S = (S << 1 + I) % 3 y O = 1 si S == 0.

En la tabla de estado para el MSB:

Explicación:0 es divisible por tres. 0 >> 1 + 0 = 0.Repita con S = (S >> 1 + I) % 3 y O = 1 si S == 0.

S' es diferente de la anterior, pero, Oh, funciona de la misma, ya que S' es 0 para los mismos casos (00 y 11).Ya que O es el mismo en ambos casos, O_LSB = O_MSB, así que para la MSB tan corto como LSB, o viceversa, sólo tiene que utilizar el menor de ambos.

Otros consejos

Hay un truco bastante conocido para determinar si un número es múltiplo de 11, al sumar y restar alternativamente sus dígitos decimales. Si el número que obtiene al final es un múltiplo de 11, entonces el número con el que comenzó también es un múltiplo de 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)

Podemos aplicar el mismo truco a los números binarios. Un número binario es un múltiplo de 3 si y solo si la suma alterna de sus bits también es un múltiplo de 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

No importa si comienza con MSB o LSB, por lo que la siguiente función de Python funciona igualmente bien en ambos casos. Se necesita un iterador que devuelva los bits de uno en uno. multiplier alterna entre 1 y 2 en lugar de 1 y -1 para evitar tomar el módulo de un número negativo.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

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

    return accumulator == 0

Aquí ... algo nuevo ... cómo verificar si un número binario de cualquier longitud (incluso miles de dígitos) es divisible por 3.

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

De la imagen.

Empiezas en el círculo doble.
Cuando obtienes un uno o un cero, si el dígito está dentro del círculo, entonces permaneces en ese círculo. Sin embargo, si el dígito está en una línea, entonces viaja a través de la línea.
Repita el paso dos hasta que se consuman todos los dígitos.
Si finalmente terminas en el círculo doble, entonces el número binario es divisible por 3.

También puede usar esto para generar números divisibles por 3. Y no me imagino que sería difícil convertir esto en un circuito.

1 ejemplo usando el gráfico ...

11000000000001011111111111101 es divisible por 3 (termina nuevamente en el círculo doble)

Pruébelo usted mismo.

También puede hacer trucos similares para realizar MOD 10, para convertir números binarios en números de base 10. (10 círculos, cada uno con un círculo doble y representan los valores 0 a 9 resultantes del módulo)

EDITAR: Esto es para dígitos que se ejecutan de izquierda a derecha, aunque no es difícil modificar la máquina de estados finitos para aceptar el idioma inverso.

NOTA: en la representación ASCII del gráfico () denota un círculo simple y (() denota un círculo doble. En máquinas de estados finitos, estos se denominan estados, y el círculo doble es el estado de aceptación (el estado que significa que eventualmente es divisible por 3)

Aquí hay una manera simple de hacerlo a mano. Dado que 1 = 2 ² mod 3, obtenemos 1 = 2 ²ⁿ mod 3 por cada entero positivo. Además 2 = 2 ^{2n + 1} mod 3. Por lo tanto, se puede determinar si un número entero es divisible por 3 contando los 1 bits en posiciones de bits impares, multiplique este número por 2, agregue el número de 1- bits en posiciones de bit pares los agregan al resultado y verifican si el resultado es divisible por 3.

Ejemplo: 57 ₁₀ = 111001 ₂. Hay 2 bits en posiciones impares y 2 bits en posiciones pares. 2 * 2 + 2 = 6 es divisible por 3. Por lo tanto, 57 es divisible por 3.

Aquí también hay un pensamiento para resolver la pregunta c). Si uno invierte el orden de bits de un entero binario, todos los bits permanecen en posiciones pares / impares o todos los bits cambian. Por lo tanto, invertir el orden de los bits de un número entero n es un número entero que es divisible por 3 si y solo si n es divisible por 3. Por lo tanto, cualquier solución para la pregunta a) funciona sin cambios para la pregunta b) y viceversa. Hmm, tal vez esto podría ayudar a determinar qué enfoque es más rápido ...

Debe hacer todos los cálculos con el módulo aritmético 3. Esta es la forma

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

Esta es una idea general ...

Ahora, su parte es comprender por qué esto es correcto.

Y sí, haga la tarea usted mismo;)

La idea es que el número puede crecer arbitrariamente, lo que significa que no puede usar mod 3 aquí, ya que su número crecerá más allá de la capacidad de su clase entera.

La idea es notar lo que le sucede al número. Si está agregando bits a la derecha, lo que realmente está haciendo es desplazarse hacia la izquierda un bit y agregar el nuevo bit.

Shift-left es lo mismo que multiplicar por 2, y agregar el nuevo bit es agregar 0 o 1. Suponiendo que comenzamos desde 0, podemos hacer esto de forma recursiva en función del módulo-3 del último número.

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)

Ahora veamos qué sucede cuando agrega un poco a la izquierda. Primero, observe que:

2 ²ⁿ mod 3 = 1

2 ^{2n + 1} mod 3 = 2

Entonces, ahora tenemos que agregar 1 o 2 al mod en función de si la iteración actual es impar o par.

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

¿No debería ser esta última entrada 12, o estoy malinterpretando la pregunta?

En realidad, el método LSB realmente lo haría más fácil. En C:

Método 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;
}

Método 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;
}

Personalmente, me cuesta creer que uno de estos sea significativamente diferente al otro.

Creo que Nathan Fellman está en el camino correcto para la parte a y b (excepto que b necesita un estado adicional: debe realizar un seguimiento de si su posición de dígitos es impar o par).

Creo creo que el truco para la parte C es negar el valor last en cada paso. Es decir. 0 va a 0, 1 va a 2 y 2 va a 1.

Un número es divisible por 3 si la suma de sus dígitos es divisible por 3.

Para que pueda agregar los dígitos y obtener la suma:

si la suma es mayor o igual a 10 use el mismo método
si es 3, 6, 9, entonces es divisible
si la suma es diferente de 3, 6, 9, entonces no es divisible

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow