\begin{questions}
\item Un algorithme possible est le suivant:
\begin{algorithme}{}
x est un nombre entier entré par l'utilisateur
p $\leftarrow$ Vrai
Si x\%2 = 1:
\quad p $\leftarrow$ Faux
Sinon:
\quad Tant que x\%2 = 0:
\qquad x $\leftarrow$ E(x/2) (partie entière de x/2)
\qquad n $\leftarrow$ n+1
\quad Fin du Tant que
\quad Si x $\neq$ 1:
\qquad p $\leftarrow$ Faux
\quad Fin du Si
Fin du Si
Afficher p
\end{algorithme}

\Par

Explications :
\begin{itemize}
\item on commence avant tout par tester si $x$ est pair (dans ce cas, $x\%2=0$). Si tel n'est pas le cas, le booléen \texttt{p} vaut \textit{Faux};
\item si $x$ est pair, on le divise par 2 autant de fois que possible (boucle \og Tant que \fg), c'est-à-dire tant que le résultat est pair;
\item la boucle terminée, si $x$ vaut 1, c'est que l'on a divisé par 2 tout le temps, et donc que $x$ est une puissance de 2. Sinon, $x$ n'est pas une puissance de 2, et le booléen \texttt{p} vaut alors \textit{Faux}.
\end{itemize}

\begin{Remarque}
la variable $n$ n'est pas utile au premier abord, mais elle nous servira pour trouver un invariant de boucle à la question 3.
\end{Remarque}

\item Un variant de boucle possible est le reste $r$ de $x$ dans sa division euclidienne par 2 ($r=x\%2$). En effet, le reste vaut 0 ou 1 dans une telle division et prend nécessairement la valeur 1 :
\begin{itemize}
\item soit quand $x$ n'est pas une puissance de 2 (le résultat de la division sera alors à un moment égal à un nombre impair plus grand que 1),
\item soit quand $x$ est une puissance de 2 (en divisant par 2 tout le temps, on arrive à un moment à $2\div2=1$ et là, le reste est égal à 1).
\end{itemize}

La boucle n'est donc pas infinie.

\item Avant d'entrer dans la boucle \og Tant que \fg, posons $a=x$ et la pré-condition \og $a$ est une puissance de 2 \fg.  Posons alors :
\begin{center}
$P$ : \og $a=2^m$, $x = a \div 2^n$ et $n\leqslant m$ \fg.
\end{center}

\newpage

Montrons que c'est un invariant de la boucle \og Tant que \fg{} :
\begin{itemize}
\item avant d'entrer dans la boucle, $x = a = a \div 2^0 = a \div 2^n$. De plus, $n=0\leqslant m$ car $m$ est un entier naturel.

Donc $P$ est vraie;

\item posons $x_1$ et $n_1$ les valeurs de $x$ et $n$ lors d'une itération où $P$ est vraie. Ainsi, $x_1=\dfrac{a}{2^{n_1}}$ et $n_1 < m$ (différent de $m$ car il faut qu'il y ait une autre itération).

Posons ensuite $x_2$ et $n_2$ les valeurs de ces mêmes variables à l'itération suivante. Alors, $n_2=n_1+1$ et:
\[
x_2 = \dfrac{x_1}{2} = \dfrac{1}{2}x_1=\dfrac{1}{2}\times\dfrac{a}{2^{n_1}}=\dfrac{a}{2^{n_1+1}}=\dfrac{a}{2^{n_2}}. \]
De plus,
\[
n_2=n_1+1<m+1\leqslant m.
\]
$P$ est donc vraie à cette étape.
\end{itemize}
Donc $P$ est un invariant de la boucle \og Tant que \fg.

La boucle étant finie, \texttt{n} contient le nombre de fois que l'on a divisé \texttt{x} par 2 et \texttt{x} vaut 1, donc :
\[
1 = \dfrac{a}{2^n},\qquad\text{soit}\qquad a = 2^n.
\]
\end{questions}
