Vous devez vous connecter pour exécuter votre code.
Hoare 4 — Puissance (exponentiation indienne)
Écrivez le code C de l'exponentiation rapide (indienne) avec annotations Hoare : calculer x^n efficacement.
Invariant attendu :
r * d^k = x_initial^n_initial && k >= 0
Quantité de contrôle attendue :
k
#include <stdio.h>
// @pre: n >= 0
// @post: retourne x^n
// @invariant: r * d^n = x_initial^n_initial && k >= 0 && 0 <= k <= n_initial
// @variant: k
int puissance(int x, int n) {
int r = 1, d = x, k = n;
while (k > 0) {
if (k % 2 == 1) r = r * d;
d = d * d;
k = k / 2;
}
return r;
}
int main() {
int x, n;
scanf("%d %d", &x, &n);
printf("%d\n", puissance(x, n));
return 0;
}