Vérifiez si un nombre est divisible par 3

Question

J'ai besoin de trouver si un nombre est divisible par 3 sans utiliser % , / o * . Le conseil donné était d'utiliser atoi() fonction. Une idée de comment faire ?

Answer 1

Les réponses actuelles se concentrent toutes sur les chiffres décimaux, en appliquant la méthode "additionner tous les chiffres et voir si cela divise par 3". Cette astuce fonctionne également en hexadécimal ; par exemple, 0x12 peut être divisé par 3 car 0x1 + 0x2 = 0x3. Et la "conversion" en hexadécimal est beaucoup plus facile que la conversion en décimal.

Pseudo-code :

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

[modifier] Inspiré de R, une version plus rapide (O log log N) :

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}

Answer 2

Soustrayez 3 jusqu'à ce que vous ayez

a) le résultat 0 - le nombre était divisible par 3

b) obtenir un nombre inférieur à 0 - le nombre n'était pas divisible

-- version éditée pour corriger les problèmes notés

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0

Answer 3

Divisez le nombre en chiffres. Additionnez les chiffres. Répétez jusqu'à ce qu'il ne reste qu'un seul chiffre. Si ce chiffre est 3, 6 ou 9, le nombre est divisible par 3 (et n'oubliez pas de traiter le 0 comme un cas particulier).

Answer 4

Bien que la technique consistant à convertir en une chaîne de caractères puis à additionner les chiffres décimaux soit élégante, elle nécessite une division ou est inefficace dans l'étape de conversion en une chaîne de caractères. Existe-t-il un moyen d'appliquer l'idée directement à un nombre binaire, sans avoir à le convertir d'abord en une chaîne de chiffres décimaux ?

Il s'avère que oui :

Étant donné un nombre binaire, la somme de ses bits impairs moins la somme de ses bits pairs est divisible par 3 si le nombre original était divisible par 3.

Par exemple, prenons le nombre 3726, qui est divisible par 3. En binaire, cela donne 111010001110 . Nous prenons donc les chiffres impairs, en commençant par la droite et en allant vers la gauche, qui sont [1, 1, 0, 1, 1, 1] ; la somme de ceux-ci est de 5 . Les bits pairs sont [0, 1, 0, 0, 0, 1] ; la somme de ceux-ci est 2 . 5 - 2 = 3, ce qui nous permet de conclure que le nombre original est divisible par 3.

Answer 5

La question de l'entretien vous demande essentiellement de trouver (ou d'avoir déjà connu) la règle de divisibilité en abrégé avec 3 comme diviseur.

L'une des règles de divisibilité pour 3 est la suivante :

Prenez n'importe quel nombre et additionnez chaque chiffre du nombre. Prenez ensuite cette somme et déterminez si elle est divisible par 3 (en répétant la même procédure si nécessaire). Si le nombre final est divisible par 3, alors le nombre initial est divisible par 3.

Exemple :

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

Voir aussi

• Wikipédia/Règle de divisibilité - a de nombreuses règles pour de nombreux diviseurs