Vérifier si un nombre est divisible par 3
je dois trouver si un nombre est divisible par 3 sans utiliser % , / ou * . L'indication donnée était d'utiliser la fonction atoi() . Aucune idée de comment le faire?
17 réponses
soustrayez 3 jusqu'à ce que vous
a) a frappé 0 - nombre est divisible par 3
b) obtenir un nombre moins de 0-Nombre n'était pas divisible
-- version modifiée pour corriger les problèmes notés
while n > 0:
n -= 3
while n < 0:
n += 3
return n == 0
les réponses actuelles se concentrent toutes sur les chiffres décimaux, en appliquant le"Ajouter tous les chiffres et voir si cela divise par 3". Cette astuce fonctionne en fait dans hex aussi bien; par exemple 0x12 peut être divisé par 3 parce que 0x1 + 0x2 = 0x3. Et "convertir" en hex est beaucoup plus facile que de convertir 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é par R, une version plus rapide (o 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;
}
divise le numéro en chiffres. Ajouter les chiffres ensemble. Répétez jusqu'à ce qu'il ne vous reste qu'un chiffre. Si ce chiffre est de 3, 6 ou 9, le nombre est divisible par 3. (Et n'oubliez pas de traiter 0 comme un cas spécial).
bien que la technique de conversion en chaîne et d'addition des décimales soit élégante, elle nécessite la division ou est inefficace dans l'étape de conversion en chaîne. Est-il un moyen d'appliquer l'idée directement à un nombre binaire, sans d'abord la conversion d'une chaîne de chiffres après la virgule?
il s'avère qu'il y a:
étant donné un nombre binaire, la somme de ses bits impairs moins la somme de ses bits pairs est divisible par 3 iff le nombre original était divisible par 3.
par exemple: prenez le numéro 3726, qui est divisible par 3. En binaire, c'est 111010001110 . Donc nous prenons les nombres impairs, en commençant par la droite et en se déplaçant à gauche, qui sont [1, 1, 0, 1, 1, 1]; la somme de ces derniers est 5 . Les parties égales sont [0, 1, 0, 0, 0, 1]; la somme de ces derniers est 2 . 5-2 = 3, dont nous pouvons conclure que le nombre original est divisible par 3.
un nombre divisible par 3, iirc a une caractéristique que la somme de son chiffre est divisible par 3. Par exemple,
12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
la question de l'entrevue vous demande essentiellement de trouver (ou d'avoir déjà connu) la règle de divisibilité raccourci avec 3 comme diviseur.
L'une des règles de divisibilité pour 3 est la suivante:
prendre n'importe quel numéro et additionner chaque chiffre du numéro. Ensuite, prenez cette somme et déterminez si elle est divisible par 3 (répétant la même procédure que nécessaire). Si le nombre final est divisible par 3, alors le nombre original 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
- Wikipedia/règle de divisibilité - a beaucoup de règles pour beaucoup de diviseurs
étant donné un nombre X. Convertissez x en chaîne. Analyser la chaîne caractère par caractère. Convertissez chaque caractère analysé en un nombre (en utilisant atoi ()) et additionnez tous ces nombres en un nouveau nombre Y. Répétez le processus jusqu'à ce que votre résultante finale nombre est un chiffre. Si ce chiffre est soit 3,6 soit 9, le nombre d'origine x est divisible par 3.
Ma solution en Java ne fonctionne que pour la version 32 bits unsigned int .
static boolean isDivisibleBy3(int n) {
int x = n;
x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
return ((011111111111 >> x) & 1) != 0;
}
d'abord réduit le nombre à un nombre inférieur à 32. La dernière étape vérifie la divisibilité en déplaçant le masque le nombre approprié de fois vers la droite.
vous n'avez pas étiqueté CE C, mais puisque vous avez mentionné atoi , je vais donner une solution de C:
int isdiv3(int x)
{
div_t d = div(x, 3);
return !d.rem;
}
bool isDiv3(unsigned int n)
{
unsigned int n_div_3 =
n * (unsigned int) 0xaaaaaaab;
return (n_div_3 < 0x55555556);//<=>n_div_3 <= 0x55555555
/*
because 3 * 0xaaaaaaab == 0x200000001 and
(uint32_t) 0x200000001 == 1
*/
}
bool isDiv5(unsigned int n)
{
unsigned int n_div_5 =
i * (unsigned int) 0xcccccccd;
return (n_div_5 < 0x33333334);//<=>n_div_5 <= 0x33333333
/*
because 5 * 0xcccccccd == 0x4 0000 0001 and
(uint32_t) 0x400000001 == 1
*/
}
suivant la même règle, pour obtenir le résultat du test de divisibilité par 'n', Nous pouvons : multiplier le nombre par 0x1 0000 0000 - (1 / n)*0xffffff comparer à (1 / n) * 0xffffffff
la contrepartie est que pour certaines valeurs, le test ne sera pas en mesure de retourner un résultat correct pour tous les 32bit nombres que vous voulez tester, par exemple, avec Divisibilité par 7 :
we got 0x100000000 - (1 / n)*0xffff = 0xDB6DB6DC et 7 * 0xDB6DB6DC = 0x6 0000 0004, Nous ne testerons qu'un quart des valeurs, mais nous pouvons certainement éviter cela avec des soustractions.
autres exemples:
11 * 0xE8BA2E8C = A0000 0004, un quart des valeurs
17 * 0xF0F0F0F1 = 10 0000 0000 1 comparer à 0xf0f0f0f0f Toutes les valeurs !
etc., nous pouvons même tester chaque nombre en combinant des nombres naturels entre eux.
un nombre est divisible par 3 si tous les chiffres du nombre lorsqu'ils sont ajoutés donnent un résultat 3, 6 ou 9. Par exemple 3693 est divisible par 3 3+6+9+3 = 21 et 2+1=3 et 3 est divisible par 3.
bien un nombre est divisible par 3 si toute la somme des chiffres du nombre est divisible par 3. vous pouvez donc obtenir chaque chiffre comme une sous-couche du numéro d'entrée et ensuite les additionner. vous serait alors répétez ce processus jusqu'à ce qu'il n'y a qu'un seul chiffre résultat.
si c'est 3, 6 ou 9 le nombre est divisable par 3.
inline bool divisible3(uint32_t x) //inline is not a must, because latest compilers always optimize it as inline.
{
//1431655765 = (2^32 - 1) / 3
//2863311531 = (2^32) - 1431655765
return x * 2863311531u <= 1431655765u;
}
sur certains compilateurs c'est encore plus rapide que la voie régulière: x % 3 . Lire la suite ici .
C# Solution pour vérifier si un nombre est divisible par 3
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int num = 33;
bool flag = false;
while (true)
{
num = num - 7;
if (num == 0)
{
flag = true;
break;
}
else if (num < 0)
{
break;
}
else
{
flag = false;
}
}
if (flag)
Console.WriteLine("Divisible by 3");
else
Console.WriteLine("Not Divisible by 3");
Console.ReadLine();
}
}
}
Voici votre solution optimisée que chacun doit savoir.................
Source: http://www.geeksforgeeks.org/archives/511
programme:
#include<stdio.h>
int isMultiple(int n)
{
int o_count = 0;
int e_count = 0;
if(n < 0)
n = -n;
if(n == 0)
return 1;
if(n == 1)
return 0;
while(n)
{
if(n & 1)
o_count++;
n = n>>1;
if(n & 1)
e_count++;
n = n>>1;
}
return isMultiple(abs(o_count - e_count));
}
int main()
{
int num = 23;
if (isMultiple(num))
printf("multiple of 3");
else
printf(" not multiple of 3");
return 0;
}
Un nombre est divisible par 3 ssi la somme de ses chiffres est divisible par 3. Vous pouvez utiliser cette définition de façon récursive jusqu'à ce qu'il vous reste un seul chiffre. Si le résultat est 3, 6 ou 9, le nombre original est divisible par 3 sinon ce n'est pas le cas.
Exaple: 33333 => 15 (3+3+3+3+3) => 6 (1+5) donc 33333 est divisible par 3.
- voici un pseudo-algol que j'ai inventé .
suivons la progression binaire de multiples de 3
000 011
000 110
001 001
001 100
001 111
010 010
010 101
011 000
011 011
011 110
100 001
100 100
100 111
101 010
101 101
juste une remarque que, pour un binaire multiple de 3 x=abcdef en suivant les couples abc =(000,011),(001,100),(010,101) cde fais le changement , donc, ma proposition de algorithme :
divisible(x):
y = x&7
z = x>>3
if number_of_bits(z)<4
if z=000 or 011 or 110 , return (y==000 or 011 or 110) end
if z=001 or 100 or 111 , return (y==001 or 100 or 111) end
if z=010 or 101 , return (y==010 or 101) end
end
if divisible(z) , return (y==000 or 011 or 110) end
if divisible(z-1) , return (y==001 or 100 or 111) end
if divisible(z-2) , return (y==010 or 101) end
end