Étant donné deux nombres positifs x et y, vérifiez si y est une puissance de x ou non.
Exemples : 
 

Entrée : x = 10, y = 1
Sortie : Vrai
x^0 = 1

Entrée : x = 10, y = 1000
Sortie : Vrai
x^3 = 1

Entrée : x = 10, y = 1001
Sortie : Faux


Une solution simple consiste à calculer à plusieurs reprises les puissances de x. Si une puissance devient égale à y, alors y est une puissance, sinon non. 

bool isPower(int x, long int y)
{
    // The only power of 1 is 1 itself
    if (x == 1)
        return (y == 1);
 
    // Repeatedly comput power of x
    long int pow = 1;
    while (pow < y)
        pow *= x;
 
    // Check if power of x becomes y
    return (pow == y);
}
 
/* Driver program to test above function */
int main()
{
    cout << isPower(10, 1) << endl;
    cout << isPower(1, 20) << endl;
    cout << isPower(2, 128) << endl;
    cout << isPower(2, 30) << endl;
    return 0;
}

La complexité temporelle de la solution ci-dessus est O(Log x y)
Optimisation : 
Nous pouvons optimiser la solution ci-dessus pour qu'elle fonctionne en O(Log Log y). L'idée est de faire la quadrature de la puissance au lieu de la multiplier par x, c'est-à-dire de comparer y avec x^2, x^4, x^8, …etc. Si x devient égal à y, renvoie vrai. Si x devient supérieur à y, alors nous effectuons une recherche binaire de la puissance de x entre la puissance précédente et la puissance actuelle, c'est-à-dire entre x^i et x^(i/2).
Voici les étapes détaillées. 

1) Initialiser pow = x, i = 1
2) tant que (pow < y)
   {
      pow = pow*pow
      je *= 2
   }    
3) Si pow == y
     renvoie vrai ;
4) Sinon, construisez un tableau de puissances
   de x^i à x^(i/2)
5) Recherche binaire pour y dans le tableau construit
   à l'étape 4. S'il n'est pas trouvé, renvoyez false.
   Sinon retourne vrai.

Solution alternative : 
L'idée est de prendre log de y en base x. S'il s'avère être un entier, nous retournons vrai. Sinon faux. 

bool isPower(int x, int y)
{
    // logarithm function to calculate value
    int res1 = logنعم / log(x);
    double res2 = logنعم / log(x); // Note : this is double
 
    // compare to the result1 or result2 both are equal
    return (res1 == res2);
}
 
// Driven program
int main()
{
    cout << isPower(27, 729) << endl;
    return 0;
}
آخر تعديل: الثلاثاء، 16 أغسطس 2022، 7:58 PM