Retour à la page précédente

Puissances

Calcul de aⁿ . Montrez que A ^N x R = aⁿ est un invariant de la boucle.

A := a;
N := n;
R := 1;
tant que N > 0 faire
si N pair alors début A := A * A; N := N/2; fin
sinon début R := R * A; N := N − 1; fin.

- Si N est pair, diviser N par 2 et remplacer A par A ² ne change pas A ^N car A² mis à l'exposant (N/2) est égal à A ^N

- Si N est impair, comme N est décrémenté de 1, A ^N devient A ^N-1, mais R est remplacé par R x A donc A ^N x R ne change pas.

Si cette démonstration vous paraît trop vague, alors il vous faut remplacer chacune des variables informatiques A, R et N par une suite : A_i , R_i et N_i (la suite des valeurs que prend la variable) et vous retrouverez alors une méthode bien connue : la démonstration par récurrence.