Verificar se um número é divisível por 3 [fechado]
https://stackoverflow.com/questions/844867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Escrever código para determinar se um número é divisível por 3. A entrada para a função é um única bit, 0 ou 1, e a saída deve ser 1 se o número recebido até agora é o representação binária de um divisível número por 3, caso contrário, zero.
Exemplos:
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
Isto é baseado em uma pergunta da entrevista. I pedir um desenho de portas lógicas, mas uma vez que este é stackoverflow eu vou aceitar qualquer linguagem de codificação. Os pontos de bónus para uma implementação de hardware (verilog etc).
Parte A (fácil):. Primeiro de entrada é o MSB
Parte b (um pouco mais difícil.): Primeiro de entrada é o LSB
Parte c (difícil): Qual deles é mais rápido e menor, (a) ou (b)? (Não teoricamente, no sentido de Big-O, mas praticamente mais rápido / mais pequeno.) Agora pegue o mais lento / maior e torná-lo o mais rápido / pequeno como o mais rápido / menor.
Solução
Heh
mesa 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
Explicação: 0 é divisível por três. 0 << 1 + 0 = 0. Repita usando S = (S << 1 + I) % 3 e O = 1 se S == 0.
mesa 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
Explicação: 0 é divisível por três. 0 >> 1 + 0 = 0. Repita usando S = (S >> 1 + I) % 3 e O = 1 se S == 0.
S' é diferente do anterior, mas O funciona da mesma, uma vez S' é 0 para os mesmos casos (00 e 11). Desde O é o mesmo em ambos os casos, O_LSB = O_MSB, de modo a tornar MSB tão curto quanto LSB, ou vice-versa, é só usar o mais curto dos dois.
Outras dicas
Há um truque bastante conhecido para determinar se um número é um múltiplo de 11, por alternadamente somando e subtraindo seus dígitos decimais. Se o número que você começa no final é um múltiplo de 11, então o número que você começou com também é um 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 o mesmo truque para números binários. Um número binário é um múltiplo de 3, se e somente se a soma alternada de seus bits também é um 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
Não faz diferença se você começar com o MSB ou LSB, por isso, a seguinte função Python funciona igualmente bem em ambos os casos. Leva um iterador que retorna os bits de um de cada vez. suplentes multiplier entre 1 e 2, em vez de 1 e -1 para evitar tomar o modulo de um 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
Aqui ... algo novo ... como verificar se um número binário de qualquer comprimento (até milhares de dígitos) é divisível por 3.
-->((0))<---1--->()<---0--->(1) ASCII representation of graph
A partir da imagem.
- Você começa no círculo duplo.
- Quando você começa um um ou um zero, se o dígito está dentro do círculo, então você ficar naquele círculo. No entanto, se o dígito está em uma linha, então você viajar em toda a linha.
- Repita o passo dois até que todos os dígitos são consumida.
- Se você finalmente acabar no círculo duplo, em seguida, o número binário é divisível por 3.
Você também pode usar isso para gerar números divisíveis por 3. E eu não iria imagem que seria difícil para converter isso em um circuito.
1 exemplo, usando o gráfico ...
11000000000001011111111111101 é divisível por 3 (acaba no duplo círculo de novo)
Tente você mesmo.
Você também pode fazer truques semelhantes para a realização de MOD 10, para quando a conversão de números binários em base de 10 números. (10 círculos, cada duplicou circulado e representam os valores 0 a 9, resultante do módulo)
EDIT:. Isto é para dígitos correndo da esquerda para a direita, não é difícil de modificar a máquina de estados finitos para aceitar o idioma reversa embora
Aqui está uma maneira simples de fazê-lo com a mão. Desde 1 = 2 2 mod 3, obtemos 1 = 2 2 n mod 3 para cada inteiro positivo. Além disso 2 = 2 2n + 1 mod 3. Daí pode-se determinar se um inteiro é divisível por três, contando os bits 1 em posições de bit ímpares, multiplicar este número por dois, adicionar o número de 1- bits de posistions bit até mesmo adicioná-los ao resultado e verificar se o resultado for divisível por 3.
Exemplo: 57 10 = 111001 2 . Há 2 bits em posições ímpares, e 2 bits em posições mesmo. 2 * 2 + 2 = 6 é divisível por 3. Daí 57 é divisível por três.
Aqui também é um pensamento para resolver questão c). Se um inverte a ordem de um inteiro binário bit, em seguida, todos os bits permanecem em posições mesmo / ímpares ou todos os bits mudança. Daí invertendo a ordem dos bits de um nero inteiro n resultados é um número inteiro que é divisível por três, se e somente se n é divisível por 3. Assim, qualquer solução para a questão a) funciona sem alterações para questão b), e vice-versa. Hmm, talvez isso poderia ajudar a descobrir qual abordagem é mais rápido ...
Você precisa fazer todos os cálculos usando módulo aritmética 3. Esta é a maneira
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 é a idéia geral ...
Agora, sua parte é entender por isso é correto.
E sim, fazer lição de casa mesmo;)
A idéia é que o número pode crescer arbitrariamente longo, que significa que você não pode usar mod 3 aqui, já que o seu número vai crescer além da capacidade de sua classe inteiro.
A idéia é observar o que acontece com o número. Se você está adicionando bits para a direita, o que você está fazendo realmente está mudando deixou um pouco e adicionar o novo bit.
Shift-esquerda é o mesmo que multiplicar por 2, e adicionando o novo bit é ou adicionando 0 ou 1. Assumindo que começou a partir de 0, podemos fazer isso de forma recursiva baseado no modulo-3 do ú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)
Agora vamos ver o que acontece quando você adiciona um pouco para a esquerda. Primeiro, observe que:
2 2n mod 3 = 1
e
2 2n + 1 mod 3 = 2
Então, agora temos que quer adicionar 1 ou 2 para o mod baseado em se a iteração atual é par ou ímpar.
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
não deve esta última entrada ser 12, ou estou mal-entendido a pergunta?
Na verdade, a LSB método seria realmente tornar isso mais fácil. Em 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;
}
LSB método:
/*
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;
}
Pessoalmente, tenho dificuldade em acreditar um deles será significativamente diferente para o outro.
Eu acho que Nathan Fellman está no caminho certo para a Parte A e b (exceto b precisa de um pedaço extra de estado: você precisa manter o controle de se a sua posição dígito é par ou ímpar).
I pensar o truque para a parte C está negando o valor last em cada etapa. Ou seja, 0 vai para 0, 1 vai para 2 e 2 vai para 1.
Um número é divisível por 3, se a soma de TI de dígitos é divisível por 3.
Assim, você pode adicionar os dígitos e obter a soma:
- Se a soma é maior ou igual a 10 utilização do mesmo método
- se é 3, 6, 9, então é divisível
- Se a soma é diferente de 3, 6, 9 então não é divisível
