class Solution
{
public:
bool isPowerOfThree (int n)
{
double temp = log10 (n) / log10 (3);
return !(temp - (int) temp);
}
};
dans le problème leetcode 326: Power of Three Étant donné un entier, écrivez une fonction pour déterminer si c'est une puissance de trois.
Je ne comprends pas comment elle renvoie le résultat booléen.
Je pense que quelqu'un peut me dire comment pour comprendre ce code suivant: return! (temp - (int) temp);
3 Réponses :
temp est un double , et (int) temp le tronque en un int . Disons que temp est 1.5 , temp - (int) temp est 0.5 . puisque le type de retour est bool , la fonction convertira le 0.5 résultant en un bool ! (0.5) qui devrait être false .
Les mots de @Nautatava "tout sauf ! (0) , ! (false) et ! (null) donne false. Ainsi < code>! (tout autre que 0) est false . "
Ajoutant à l'explication, tout sauf! (0),! (False) et! (Null) donne false. Ainsi! (Tout autre chose que 0) est faux.
Ce code utilise simplement la troncature entière pour tester si le nombre temp est un nombre entier. Si c'est le cas, alors temp - (int) temp sera égal à zéro. Puisque cela signifierait alors que le nombre est une puissance de trois, alors l'opérateur unaire "non" ! retournera vrai. Et bien sûr, ! utilisé sur toute valeur différente de zéro (vrai) sera faux.
La solution repose sur le fait que temp est un nombre entier lorsque n est une puissance de 3 et temp étant un nombre avec une valeur fractionnaire lorsque n n'est pas une puissance de 3 .
Disons que n est 9 code >.
Ensuite, temp sera 2.0 .
Ensuite, (temp- (int) temp) sera 0 et ! (Temp- (int) temp) sera true .
Disons que n vaut 10 .
Ensuite, temp sera 2.0959 .
Ensuite, (temp- (int) temp) sera 0.0959 et ! (Temp- (int) temp) sera false .
Malheureusement, les calculs en virgule flottante ne sont pas si précis. Il vaudra mieux utiliser:
double temp = log10 (n) / log10 (3); double diff = (temp - (int) temp);` return (std::abs(diff) < tolerance);
où tolérance peut être un petit nombre, tel que 1.0E-6 .
Mon expérience avec cygwin / g ++ sur mon ordinateur et sur ideone.com suggère que la tolérance peut être 1.0e-6 pour un grand ensemble de nombres mais il doit être presque 1.0e-11 ou plus petit pour INT_MAX. Voir https://ideone.com/BgnQxV .
Juste par curiosité, une idée qui serait le plus grand epsilon qui correspond à toutes les valeurs entre 1 et INT_MAX? Comme log (n) croît sans limites (terme correct en anglais?), Mais log (n + 1) -log (n) va contre 0 pour n < / code> allant contre l'infini, nous trouverions un n suffisamment grand pour n'importe quel epsilon pour que le test échoue, uniquement que ce n sera trop grand pour tenir dans une plage entière si epsilon est suffisamment petit. ..
Un peu expérimenté, 1.0e-6 est en effet trop grand, essayez avec 4782970 ...
@Aconcagua, mon expérience avec cygwin / g ++ suggère qu'il peut être 1.0e-6 pour un grand ensemble de nombres mais il doit être presque 1.0e-11 pour INT_MAX. ideone.com/BgnQxV .
J'ai essayé avec des puissances négatives de deux, j'ai réussi à trouver des nombres pour 2 ^ -30 (entiers signés 32 bits) et 2 ^ 31 (entiers non signés 32 bits). On dirait étrangement que nous aurions besoin de 2 ^ -n pour être sûrs pour les valeurs n bits positives, sans essayer de prouver mathématiquement, cependant ...
Comme vous autorisez
intcomme entrée: les logarithmes ne sont pas définis pour les valeurs <= 0! Vous avez donc besoin d'une manipulation spéciale pour.Un autre cas particulier: quel est le logarithme de 1 ???