J'ai essayé de le résoudre moi-même mais je ne pouvais pas obtenir d'indice.
Aidez-moi s'il vous plaît à résoudre ce problème.
18 Réponses :
sonne comme des devoirs :)
I Image Vous pouvez écrire une fonction qui divise itérativement un numéro. Par exemple. Vous pouvez modéliser ce que vous faites avec un stylo et un morceau de papier pour diviser les nombres. Ou vous pouvez utiliser des opérateurs de décalage et + pour déterminer si vos résultats intermédiaires sont trop petits / gros et appliquent de manière itérative corrections. Je ne vais pas écrire le code si ...
lent et naïf, mais cela devrait fonctionner, si un diviseur exact existe. L'ajout est autorisé, non?
for number from 1 to input
if number == input+input+input
return number
Non, cela renvoie toujours l'entrée (MULT au lieu de diviser et de mauvaise portée de boucle) et suppose une entrée> 0
UHM, cela ne fait pas de division du tout et ne reviendra jamais rien. "Numéro" peut être au plus "entrée", donc "numéro == entrée + entrée + entrée" ne sera jamais vrai.
Vous devez remplacer l'entrée "numéro == + entrée + entrée" par "entrée == numéro + numéro + numéro"
pour la division entière positive
Seule la division entière. Ne gère pas les nombres négatifs. Si l'entrée est importante, de nombreux ajouts non spécifiques sont faits.
YEP mais cela fonctionne réellement avec ces contraintes contrairement à une autre réponse similaire
Oui, c'est beaucoup mieux à cet égard :)
On dirait-il, dans une sorte de python comme pseudo-code. Il divise la réponse dans une partie entière et une partie de fraction. Si vous voulez le convertir en une représentation à point flottant, je ne suis pas sûr de la meilleure façon de le faire. Notez que cela ne fonctionnera pas pour des nombres négatifs. Pour résoudre ce problème, vous devez modifier l'algorithme: P> total = abs(x)
is_neg = abs(x) != x
....
if is_neg
print "%d / 3 = -(%d + %d/3)" % (x, intpart, fracpart)
if(number<0){ // Edited after comments
number = -(number);
}
quotient = 0;
while (number-3 >= 0){ //Edited after comments..
number = number-3;
quotient++;
}//after loop exits value in number will give you reminder
EDIT: Tested and working perfectly fine :(Hope this helped. :-)
Ne gère pas les nombres négatifs
Il sera préférable que la condition soit numéro> = 3 car vous pouvez obtenir ceci: 5: 3 = 2
Ne fonctionne toujours pas. Cela en retournera un trop. Essayez le numéro = 3, vous remarquerez comment il retournera quotient = 2 au lieu de quotient = 1
@kigurai: il ne reviendrait pas quotient = 2 pour Number = 3 .. Vérifiez à nouveau :( ..elle mes yeux et mon cerveau devraient me tromper .. J'ai même testé la même chose .. Vérifiez bien le code avant de mettre des commentaires et de la baisse vote .. pls
@Fortega 5/3 est 1.66666..J'ai d'accord ... ici 1 est quotient .. Si vous vérifiez mon code, cela vous donne un quotient comme 1 et vous rappelez que 2. 2/3 est 0.66666 ... donc les deux ensemble donneront vous 1.6666 ..
la solution consiste à multiplier par un nombre magique, puis à extraire les 32 bits les plus à gauche: p> Diviser par 3 est équivalent à multiplier par 1431655766, puis à passer de 32, dans C: P>
int divideBy3(int n)
{
return (n * 1431655766) >> 32;
}
Lisez le titre: "Sans utiliser / , % et * ".
@Aim: Oui, je viens de mal interpréter le titre. J'avais monté ma réponse pendant que vous écrivez votre commentaire
Je pitié le fou que ça doive la choisir pour la maintenance ... :)
@Paolo: avec code commenté, ce n'est peut-être pas un problème. Il est bon de l'avoir dans votre sac d'optimisation des astuces et des parties du code qui ne sont pas vraiment critiques ne doivent pas l'utiliser évidemment
J'aime cette réponse. La multiplication peut être réécrite comme A pour (int i = 0; i <1431655766) n + = n; Que la réponse est conforme aux exigences.
@Fortegn: x + = n; . n + = n entraînera n * 2 ^ 1431655766 :)
@Fortegna, il faut être une bonne façon d'utiliser >> et + pour multiplier rapidement par gros chiffres. Par exemple, 5 * x == (x << 2) + x . Une expression longue, avec de nombreux <<< / code>, doit pouvoir faire * 1431655766
J'ai suscité cela parce que j'ai remarqué la multiplication par 1431655766 dans la sortie du compilateur, a fait une recherche Google du numéro et a appris grâce à cette réponse que ce qui se passait était divisée par 3. (Désolé.)
Ceci est très facile, si facile, je ne vais pas laisser allusion à la réponse -
Les portes de base de la logique booléenne de base (et, non pas, xor, ...) ne font pas la division. En dépit de ce handicap, les processeurs peuvent faire la division. Votre solution est évidente: trouvez une référence qui vous indique comment créer un diviseur avec une logique booléenne et écrire du code pour mettre en œuvre cela.
J'aurais dû ajouter que si vous voulez que vous puissiez mettre en œuvre un circuit qui divise seulement 3, mais pourquoi ne pas mettre en œuvre un circuit pour la division générale.
Bien diviser par une constante va utiliser moins de portes - souvent une optimisation importante dans la conception matérielle (suppose que cela dépend de la classe ceci pour)
Utilisation de la relation mathématique: Nous avons p> si vous ne pouvez utiliser que des entiers 32 bits, P> int div3 (int x) {
int two_third = 0, four_third = 0;
for (int power = 0; power < 31; power += 2) {
four_third += x >> power;
two_third += x >> (power + 1);
}
return (four_third - two_third) >> 2;
}
La version "64 bits" fait travaille. La version "32 bits" sera au plus éteinte de 1 ou -1.
Ceci est juste une représentation binaire de 1/3
Êtes-vous supposé utiliser ITOA () pour cette affectation? Parce que vous pouvez utiliser cela pour convertir une chaîne de base 3, déposez le dernier caractère, puis restaurez-vous à la base 10.
Voici une solution implémentée en C ++: ; -)
unsigned int div3(unsigned int m) {
unsigned long long n = m;
n += n << 2;
n += n << 4;
n += n << 8;
n += n << 16;
return (n+m) >> 32;
}
Cela fonctionne et a l'air si simple ... mais quelle était votre logique?
x / 3 = e ^ (ln (x) - ln (3))
convertir 1/3 en binaire
SO 1/3 = 0.01010101010101010101010101
et ensuite "multiplier" whit ce numéro à l'aide de ShiftS and Sum
long divByThree(int x)
{
char buf[100];
itoa(x, buf, 3);
buf[ strlen(buf) - 1] = 0;
char* tmp;
long res = strtol(buf, &tmp, 3);
return res;
}
int divideby3(int n)
{
int x=0;
if(n<3) { return 0; }
while(n>=3)
{
n=n-3;
x++;
}
return x;
}
Vous pouvez utiliser une propriété à partir des numéros: un nombre est divisible par 3 si sa somme est divisible by3. Prenez les chiffres individuels de ITOA (), puis utilisez la fonction de commutation pour eux de manière récursive avec des ajouts et ITOA ()
J'espère que cela aide
Il y a une solution postée sur http: // bbs .chinaunix.net / forum.php? Mod = Viewthread & Tid = 3776384 & Page = 1 & Extra = # # PID22323016
int DividedBy3(int A) {
int p = 0;
for (int i = 2; i <= 32; i += 2)
p += A << i;
return (-p);
}
voici un (style C Code) Il utilise la récursion, mais notez que le nombre tombe de taille exponentielle à chaque itération, la complexité de temps (TC) est vraiment: Nous notons que le nombre à chaque récursivité diminue strictement (D'au moins 1): SO implique: implique: Nous notons pour iff: implique: iff: donc Soit maintenant implique: et donné: implique: O (journal (n)) moyen de le faire sans décalage de bit, il peut donc gérer les nombres à la haine et y compris votre plus grande taille de registre.
O (TC) = O (journal (n) + journal (journal (n)) + journal (journal (journal (n))) + ... + z)
où z <6 .
la preuve que c'est O (log (n)):
Série = [Journal (journal (n))] + [Journal (journal (journal (n)))] + [...] + [ z]) a au plus journal (journal (n)) SUMS. Série <= journal (n)) * journal (journal (n)) O (tc) = O (log (n) + log ( journal (n)) * journal (journal (n))) n suffisamment grand:
sqrt (x)> journal (x) x / sqrt (x)> journal (x) x / journal (x)> journal (x) x> journal (x) * journal (x) o (x)> o (log (x) * log (x)) x = journal (n) O (log (n))> o (journal (journal (n)) * journal (journal (n)))
O (TC) = O (journal (n) + journal (journal (n)) * journal (journal (n))) O (tc) = O (journal (n))
Si vous autorisez + et - il n'y a aucun sentiment d'empêcher /, * et% de l'utilisation. on peut conduire la fonction. Ou + et - devrait aussi être banni .. :)