Vérifier si un nombre est divisible par 3 [fermé]

https://stackoverflow.com/questions/844867

20-08-2019
|

Question

Écrivez un code pour déterminer si un nombre est divisible par 3. L'entrée de la fonction est un bit unique , 0 ou 1, et la sortie doit être égale à 1 si le nombre reçu jusqu'à présent est le représentation binaire d'un nombre divisible par 3, sinon zéro.

Exemples:

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

Ceci est basé sur une question d’entrevue. Je demande un dessin des portes logiques, mais comme il s'agit de stackoverflow, j'accepte n'importe quel langage de codage. Points bonus pour une implémentation matérielle (verilog, etc.).

Partie a (facile): La première entrée est le MSB.

Partie b (un peu plus difficile): La première entrée est le LSB.

Partie c (difficile): Lequel est le plus rapide et le plus petit, (a) ou (b)? (Pas théoriquement au sens Big-O, mais pratiquement plus rapide / plus petit.) Maintenant, prenez le plus lent / plus gros et rendez-le aussi petit / plus rapide que le plus rapide / plus petit.

La solution

Heh

Table d'état pour LSB:

Explication: 0 est divisible par trois. 0 << 1 + 0 = 0 Répétez avec S = (S << 1 + I) % 3 et O = 1 si S == 0.

Table d'état pour MSB:

Explication: 0 est divisible par trois. 0 >> 1 + 0 = 0 Répétez avec S = (S >> 1 + I) % 3 et S' si <=>.

<=> est différent de ce qui précède, mais O fonctionne de la même manière, car <=> vaut 0 pour les mêmes cas (00 et 11). Puisque O est le même dans les deux cas, O_LSB = O_MSB, utilisez donc le plus court des deux pour que MSB soit aussi petit que LSB.

Autres conseils

Il existe une astuce assez connue pour déterminer si un nombre est un multiple de 11, en additionnant et en soustrayant ses chiffres décimaux. Si le nombre que vous obtenez à la fin est un multiple de 11, le nombre avec lequel vous avez commencé est également un multiple 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)

Nous pouvons appliquer la même astuce aux nombres binaires. Un nombre binaire est un multiple de 3 si et seulement si la somme alternée de ses bits est également un multiple 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

Cela ne fait aucune différence que vous commenciez avec le MSB ou le LSB. La fonction Python suivante fonctionne donc aussi bien dans les deux cas. Il faut un itérateur qui renvoie les bits un à la fois. multiplier alterne entre 1 et 2 au lieu de 1 et -1 pour éviter de prendre le modulo d'un nombre négatif.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

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

    return accumulator == 0

Ici ... quelque chose de nouveau ... comment vérifier si un nombre binaire de longueur quelconque (même des milliers de chiffres) est divisible par 3.

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

À partir de l'image.

Vous commencez dans le double cercle.
Lorsque vous obtenez un ou zéro, si le chiffre est à l'intérieur du cercle, vous restez dans ce cercle. Toutefois, si le chiffre est sur une ligne, vous vous y retrouverez.
Répétez la deuxième étape jusqu'à ce que tous les chiffres soient compris.
Si vous vous retrouvez finalement dans le double cercle, le nombre binaire est divisible par 3.

Vous pouvez également l'utiliser pour générer des nombres divisibles par 3. Et je n'aurais pas imaginé qu'il serait difficile de convertir cela en un circuit.

1 exemple d'utilisation du graphique ...

1100000000000101011111111111101 est divisible par 3 (termine dans le double cercle à nouveau)

Essayez par vous-même.

Vous pouvez également utiliser des astuces similaires pour exécuter MOD 10, pour convertir des nombres binaires en nombres de base 10. (10 cercles, chacun doublé, représentent les valeurs 0 à 9 résultant du modulo)

EDIT: Il s’agit bien des chiffres de gauche à droite. Il n’est pas difficile de modifier la machine à états finis pour accepter le langage inversé.

REMARQUE: Dans la représentation ASCII du graphique, () désigne un cercle simple et (()) désigne un cercle double. Dans les machines à états finis, on les appelle états, et le double cercle est l'état d'acceptation (l'état qui signifie qu'il est finalement divisible par 3)

Voici un moyen simple de le faire à la main. Puisque 1 = 2 ² mod 3, nous obtenons 1 = 2 ²ⁿ mod 3 pour chaque entier positif. De plus, 2 = 2 ^{2n + 1} mod 3. On peut donc déterminer si un entier est divisible par 3 en comptant les 1 bits en positions de bits impairs, multiplier ce nombre par 2, additionner le nombre 1- les bits aux positions paires les ajoutent au résultat et vérifient si le résultat est divisible par 3.

Exemple: 57 ₁₀ = 111001 ₂. Il y a 2 bits aux positions impaires et 2 bits aux positions paires. 2 * 2 + 2 = 6 est divisible par 3. Par conséquent, 57 est divisible par 3.

Voici également une pensée pour résoudre la question c). Si l'on inverse l'ordre des bits d'un entier binaire, tous les bits restent à des positions paires / impaires ou tous les bits changent. Par conséquent, inverser l'ordre des bits d'un entier n résultats est un entier divisible par 3 si et seulement si n est divisible par 3. Toute solution de la question a) fonctionne donc sans modification pour la question b) et inversement. Hmm, peut-être que cela pourrait aider à déterminer quelle approche est la plus rapide ...

Vous devez effectuer tous les calculs à l'aide de l'arithmétique modulo 3. Voici comment procéder

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

C’est une idée générale ...

Votre rôle consiste maintenant à comprendre pourquoi ceci est correct.

Et oui, faites vos devoirs vous-même;)

L'idée est que le nombre peut devenir arbitrairement long, ce qui signifie que vous ne pouvez pas utiliser mod 3 ici, car votre nombre dépassera la capacité de votre classe d'entiers.

L'idée est de noter ce qu'il advient du nombre. Si vous ajoutez des bits à droite, vous effectuez un décalage d’un bit vers la gauche et l’ajout du nouveau.

Maj-gauche équivaut à multiplier par 2 et ajouter le nouveau bit revient à ajouter 0 ou 1. En supposant que nous partions de 0, nous pouvons le faire récursivement en fonction du modulo-3 du dernier nombre.

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)

Voyons maintenant ce qui se passe lorsque vous ajoutez un peu à gauche. Tout d’abord, remarquez que:

2 ²ⁿ mod 3 = 1

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

Nous devons donc maintenant ajouter 1 ou 2 au mod en fonction de l'itération actuelle impaire ou paire.

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

Cette dernière entrée ne devrait-elle pas être 12, ou est-ce que je comprends mal la question?

En fait, la méthode LSB rendrait cela plus facile. En C:

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

Personnellement, j'ai du mal à croire que l'un d'entre eux sera très différent de l'autre.

Je pense que Nathan Fellman est sur la bonne voie pour les parties a et b (sauf que b nécessite un état supplémentaire: vous devez suivre si votre position des chiffres est impair ou pair).

Je pense que le truc pour la partie C est d’annuler la valeur last à chaque étape. C'est à dire. 0 va à 0, 1 à 2 et 2 à 1.

Un nombre est divisible par 3 si la somme de ses chiffres est divisible par 3.

Vous pouvez donc ajouter les chiffres et obtenir la somme:

si la somme est supérieure ou égale à 10, utilisez la même méthode
si c'est 3, 6, 9 alors c'est divisible
si la somme est différente de 3, 6, 9 alors ce n'est pas divisible

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow