[TP09] Exponentiation - Induction - [LINFO1103] Introduction à l'algorithmique

Câu hỏi 1: Cas de base

Sélectionnez, parmi les propositions suivantes, celle(s) qui corresponde(nt) à un cas de base pour l'algorithme puiss.

L'algorithme est triviallement correct pour \(x = n-1\)

L'algorithme est triviallement correct pour \(x \geq 1\)

L'algorithme est triviallement correct pour \(x = 1\)

L'algorithme est triviallement correct pour \(x \geq 0\)

L'algorithme est triviallement correct pour \(n = n-1\)

L'algorithme est triviallement correct pour \(n \geq 1\)

L'algorithme est triviallement correct pour \(n = 0\)

L'algorithme est triviallement correct pour \(n = 1\)

Câu hỏi 2: Induction

Sélectionnez, parmi les propositions suivantes, celle(s) qui corresponde(nt) à un raisonnement par induction pour prouver que l'algorithme puiss est correct.

Si l'énoncé est vrai pour \(n+1`\) alors il est vrai pour \(n\)

Si l'énoncé est vrai pour \(n/2\) alors il est vrai pour \(n\)

Si l'énoncé est vrai pour \((n-1)/2\) alors il est vrai pour \(n\)

Si l'énoncé est vrai pour \(n\) alors il est vrai pour le cas de base

Si l'énoncé est vrai pour \(\lfloor n/2 \rfloor\) alors il est vrai pour \(n\)

Si l'énoncé est vrai pour \(n+1\) alors il est vrai pour \(n-1\)

Si l'énoncé est vrai pour \(n/2\) alors il est vrai pour \(2n\)

Si l'énoncé est vrai pour le cas de base alors il est vrai tout \(n\)

Si l'énoncé est vrai pour \(n/2\) alors il est vrai pour \(2n+1\)

Si l'énoncé est vrai pour \(n-1\) alors il est vrai pour \(n\)

Câu hỏi 3: Hypothèse

Sélectionnez, parmi les propositions suivantes, celle(s) qui corresponde(nt) à l'hypothèse d'une preuve par induction pour prouver que l'algorithme puiss est correct.

Si n est pair :

\begin{align*} \mathit{puiss}(x, n) = & \mathit{puiss}(x^2, \frac{n}{2})\\ = & {{\left(x\right)}^{\frac{n}{2}}}^{2}\\ = & x^n \end{align*}

Si n est pair :

\begin{align*} \mathit{puiss}(x, n) = & \mathit{puiss}(x^2, \frac{n}{2})\\ = & {\left({x}^{\frac{n}{2}}\right)}^{2}\\ = & x^n \end{align*}

Si n est impair :

\begin{align*} \mathit{puiss}(x, n) = & x \times \mathit{puiss}(x^2, \frac{n-1}{2})\\ = & x \times {\left(x^2\right)}^{\frac{n-1}{2}}\\ = & x^n \end{align*}

Si n est impair :

\begin{align*} \mathit{puiss}(x, n) = & x \times \mathit{puiss}(x^2, \frac{n-1}{2})\\ = & {\left(x^2\right)}^{\frac{n}{2}}\\ = & x^n \end{align*}

Si n est impair :

\begin{align*} \mathit{puiss}(x, n) = & x \times \mathit{puiss}(x^2, \frac{n-1}{2})\\ = & {\left(x^3\right)}^{\frac{n-1}{2}}\\ = & x^n \end{align*}

Si n est pair :

\begin{align*} \mathit{puiss}(x, n) = & \mathit{puiss}(x^2, \frac{n}{2})\\ = & {\left(x^2\right)}^{\frac{n}{2}}\\ = & x^n \end{align*}

Si n est impair :

\begin{align*} \mathit{puiss}(x, n) = & x \times \mathit{puiss}(x^2, \frac{n-1}{2})\\ = & {\left(x^2\right)}^{\frac{n-1}{2}+x}\\ = & x^n \end{align*}

Câu hỏi 4: Preuve

Sélectionnez, parmi les réponses suivantes, celle qui est correcte.

Le raisonnement inductif permet de prouver que l'algorithme puiss est correct

Le raisonnement inductif ne permet pas de prouver que l'algorithme puiss est correct

Le raisonnement inductif permet de prouver que l'algorithme puiss est incorrect

Tác giả	Vincent Branders, Pierre Dupont
Hạn chót	22/04/2026 14:00:00
Giới hạn nộp bài	Không có giới hạn

Thông tin

Đăng nhập