puzzle - números - Compruebe si un número es divisible por 3

divisibilidad por 4

Question

Escriba el código para determinar si un número es divisible por 3. La entrada a la función es un bit único , 0 o 1, y la salida debería ser 1 si el número recibido hasta ahora 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. Solicito un dibujo de compuertas lógicas, pero como esto es un flujo de apilamiento, aceptaré cualquier lenguaje de codificación. Puntos de bonificación para una implementación de hardware (verilog, etc).

Parte a (fácil): La primera entrada es la MSB.

Parte b (un poco más difícil): la primera entrada es la LSB.

Parte c (difícil): ¿Cuál es más rápido y más pequeño, (a) o (b)? (No teóricamente en el sentido de Big-O, pero prácticamente más rápido / más pequeño). Ahora tome el más lento / grande y hágalo tan rápido / pequeño como el más rápido / pequeño.

Answer 1

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 foto.

1. Comienzas en el doble círculo.
2. 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 usted viaja a través de la línea.
3. Repita el paso dos hasta que todos los dígitos estén consumidos.
4. Si finalmente terminas en el círculo doble, entonces el número binario es divisible por 3.

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

1 ejemplo usando la gráfica ...

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

Pruébalo por ti mismo.

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

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

NOTA: En la representación ASCII de la gráfica () denota un solo círculo y (()) denota un doble círculo. En las máquinas de estados finitos, estos se llaman estados, y el círculo doble es el estado de aceptación (el estado que significa su eventual divisible por 3)

Answer 2

Aquí hay una forma sencilla de hacerlo a mano. Como 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 entre 3 contando los 1 bits en las posiciones de bits impares, multiplique este número por 2, agregue el número de 1 bits en las posiciones de bits pares y agregue al resultado y compruebe 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, entonces todos los bits permanecen en posiciones pares / impares o todos los bits cambian. Por lo tanto, invertir el orden de los bits de los resultados de un entero n es un 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 averiguar qué enfoque es más rápido ...

Answer 3

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

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

Answer 4

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

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.

Answer 5

Hay un truco bastante conocido para determinar si un número es un múltiplo de 11, al sumar y restar alternativamente sus dígitos decimales. Si el número que obtienes al final es un múltiplo de 11, entonces el número con el que comenzaste 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 alternativa 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 comienzas con MSB o LSB, por lo que la siguiente función de Python funciona igual de bien en ambos casos. Se necesita un iterador que devuelve los bits uno a la vez. 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

Answer 6

Heh

Tabla de estado para 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

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

Tabla de estado para 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

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

S'' es diferente a la anterior, pero O funciona de la misma manera, ya que S'' es 0 para los mismos casos (00 y 11). Dado que O es el mismo en ambos casos, O_LSB = O_MSB, así que para hacer MSB tan corto como LSB, o viceversa, solo use el más corto de ambos.

Answer 7

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

La idea es darse cuenta de lo que pasa con el número. Si está agregando bits a la derecha, lo que realmente está haciendo es desplazarse un bit hacia la izquierda 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 hacerlo de forma recursiva según el 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 que pasa cuando agregas un poco a la izquierda. Primero, note que:

2 ²ⁿ mod 3 = 1

y

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

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

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

Answer 8

Necesitas hacer todos los cálculos usando el módulo aritmético 3. Este es el camino

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, tu parte es entender por qué esto es correcto.

Y sí, haz la tarea tú mismo;)

Answer 9

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

Así que puedes sumar los dígitos y obtener la suma:

• si la suma es mayor o igual a 10 usa 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

Answer 10

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

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