Controlla se un numero è divisibile per 3 [chiuso]

Question

Scrivi il codice per determinare se un numero è divisibile per 3.L'input per la funzione è a separare bit, 0 o 1, e l'uscita dovrebbe essere 1 se il numero ricevuto finora è la rappresentazione binaria di un numero divisibile per 3, altrimenti zero.

Esempi:

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

Questo si basa su una domanda di intervista.Chiedo un disegno delle porte logiche ma poiché si tratta di StackOverflow accetterò qualsiasi linguaggio di codifica.Punti bonus per un'implementazione hardware (verilog ecc.).

Parte a (facile): Il primo input è l'MSB.

Parte b (un po' più difficile): Il primo input è l'LSB.

Parte c (difficile): Quale è più veloce e più piccolo, (a) o (b)?(Non teoricamente nel senso della O grande, ma praticamente più veloce/più piccolo.) Ora prendi quello più lento/più grande e rendilo veloce/piccolo quanto quello più veloce/più piccolo.

Answer 1

Eh

Tabella di stato per 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

Spiegazione: 0 è divisibile per tre. 0 << 1 + 0 = 0. Ripeti usando S = (S << 1 + I) % 3 e O = 1 se S == 0.

Tabella di stato per 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

Spiegazione: 0 è divisibile per tre. 0 >> 1 + 0 = 0. Ripeti usando S = (S >> 1 + I) % 3 e S' se <=>.

<=> è diverso da sopra, ma O funziona allo stesso modo, poiché <=> è 0 per gli stessi casi (00 e 11). Poiché O è lo stesso in entrambi i casi, O_LSB = O_MSB, quindi per rendere MSB più corto di LSB, o viceversa, usa solo il più corto di entrambi.

Answer 2

Esiste un trucco abbastanza noto per determinare se un numero è un multiplo di 11, aggiungendo e sottraendo alternativamente le sue cifre decimali. Se il numero che ottieni alla fine è un multiplo di 11, allora anche il numero con cui hai iniziato è un multiplo di 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)

Possiamo applicare lo stesso trucco ai numeri binari. Un numero binario è un multiplo di 3 se e solo se la somma alternata dei suoi bit è anche un multiplo di 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

Non fa differenza se inizi con MSB o LSB, quindi la seguente funzione Python funziona ugualmente bene in entrambi i casi. Prende un iteratore che restituisce i bit uno alla volta. multiplier alterna tra 1 e 2 invece di 1 e -1 per evitare di prendere il modulo di un numero negativo.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

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

    return accumulator == 0

Answer 3

Qui...qualcosa di nuovo...come verificare se un numero binario di qualsiasi lunghezza (anche migliaia di cifre) è divisibile per 3.

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

Dalla foto.

1. Inizi nel doppio cerchio.
2. Quando ottieni uno o uno zero, se la cifra è all'interno del cerchio, rimani in quel cerchio.Tuttavia, se la cifra si trova su una linea, viaggi attraverso la linea.
3. Ripetere il passaggio due fino al completamento di tutte le cifre.
4. Se alla fine finisci nel doppio cerchio, il numero binario è divisibile per 3.

Puoi anche usarlo per generare numeri divisibili per 3.E non immagino che sarebbe difficile convertirlo in un circuito.

1 esempio utilizzando il grafico...

110000000000010111111111111101 è divisibile per 3 (finisce di nuovo nel doppio cerchio)

Provalo tu stesso.

Puoi anche eseguire trucchi simili per eseguire il MOD 10, per convertire i numeri binari in numeri in base 10.(10 cerchi, ciascuno raddoppiato e rappresentano i valori da 0 a 9 risultanti dal modulo)

MODIFICARE: Questo è per le cifre che vanno da sinistra a destra, non è difficile modificare la macchina a stati finiti per accettare il linguaggio inverso.

NOTA: Nella rappresentazione ASCII del grafico () denota un singolo cerchio e (()) denota un doppio cerchio.Nelle macchine a stati finiti questi sono chiamati stati e il doppio cerchio è lo stato accettato (lo stato che significa che è eventualmente divisibile per 3)

Answer 4

Ecco un modo semplice per farlo a mano. Poiché 1 = 2 ² mod 3, otteniamo 1 = 2 ²ⁿ mod 3 per ogni numero intero positivo. Inoltre 2 = 2 ^{2n + 1} mod 3. Quindi si può determinare se un numero intero è divisibile per 3 contando i 1 bit in posizioni dispari, moltiplicare questo numero per 2, aggiungere il numero di 1- bit con posizioni di bit pari li aggiungono al risultato e controllano se il risultato è divisibile per 3.

Esempio: 57 ₁₀ = 111001 ₂ . Vi sono 2 bit in posizioni dispari e 2 bit in posizioni pari. 2 * 2 + 2 = 6 è divisibile per 3. Quindi 57 è divisibile per 3.

Ecco anche un pensiero per risolvere la domanda c). Se si inverte l'ordine dei bit di un intero binario, tutti i bit rimangono in posizioni pari / dispari o tutti i bit cambiano. Quindi invertire l'ordine dei bit di un numero intero n risultati è un numero intero che è divisibile per 3 se e solo se n è divisibile per 3. Quindi qualsiasi soluzione per la domanda a) funziona senza modifiche per la domanda b) e viceversa. Forse questo potrebbe aiutare a capire quale approccio è più veloce ...

Answer 5

Devi fare tutti i calcoli usando l'aritmetica modulo 3. Questo è il modo

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

Questa è un'idea generale ...

Ora, la tua parte è capire perché questo è corretto.

E sì, fai i compiti da solo;)

Answer 6

L'idea è che il numero possa crescere in modo arbitrario, il che significa che non puoi usare mod 3 qui, poiché il tuo numero crescerà oltre la capacità della tua classe intera.

L'idea è di notare cosa succede al numero. Se stai aggiungendo bit a destra, quello che stai effettivamente facendo è spostare un bit a sinistra e aggiungere il nuovo bit.

Maiusc-sinistra equivale a moltiplicare per 2 e l'aggiunta del nuovo bit aggiunge 0 o 1. Supponendo che siamo partiti da 0, possiamo farlo ricorsivamente sulla base del modulo 3 dell'ultimo numero.

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)

---

Ora vediamo cosa succede quando aggiungi un po 'a sinistra. Innanzitutto, nota che:

2 ²ⁿ mod 3 = 1

e

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

Quindi ora dobbiamo aggiungere 1 o 2 alla mod in base se l'attuale iterazione è pari o dispari.

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 7

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

Questo ultimo input non dovrebbe essere 12, o sto fraintendendo la domanda?

Answer 8

In realtà il metodo LSB renderebbe questo più semplice. In C:

Metodo 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;
}

Metodo 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 faccio fatica a credere che uno di questi sarà significativamente diverso dall'altro.

Answer 9

Penso che Nathan Fellman sia sulla buona strada per la parte aeb (tranne che per b ha bisogno di un ulteriore stato: devi tenere traccia di se la posizione della tua cifra è pari o dispari).

I penso il trucco per la parte C sta negando il valore last ad ogni passo. Cioè 0 va a 0, 1 va a 2 e 2 va a 1.

Answer 10

Un numero è divisibile per 3 se la somma delle sue cifre è divisibile per 3.

Quindi puoi aggiungere le cifre e ottenere la somma:

• se la somma è maggiore o uguale a 10 usa lo stesso metodo
• se è 3, 6, 9 allora è divisibile
• se la somma è diversa da 3, 6, 9, allora non è divisibile