“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 179 — #189
i
i
i
i
i
i
i
i
3.9 Exercices
179
3.9 EXERCICES
➤ Exercice 1 — La valeur absolue des nombres réels
Nous voulons définir une fonction Abs qui calcule la valeur absolue d’un nombre
réel. La définition suivante est fausse :
fun {Abs X} if X<0 then ˜X else X end end
Pourquoi ? Comment la corrigeriez-vous ?
Indice : Le problème est trivial.
➤ Exercice 2 — Les racines cubiques
Ce chapitre utilise la méthode de Newton pour calculer les racines carrées. La
méthode peut être étendue pour calculer des racines de tout degré. Par exemple, la
méthode suivante calcule les racines cubiques. Soit une estimation g de la racine
cubique de x, une estimation améliorée est donnée par (x/g
2 + 2g)/3. Écrivez
un programme déclaratif pour calculer les racines cubiques avec la méthode de
Newton.
➤ Exercice 3 — La méthode du demi-intervalle
18
La méthode du demi-intervalle est une technique simple mais puissante pour
trouver des racines de l’équation f (x) = 0, où f est une fonction réelle continue.
L’idée est la suivante : si nous avons des nombres réels a et b tels que f (a) <
0 < f (b), alors f doit avoir au moins une racine entre a et b. Pour la localiser,
prenez x = (a + b)/2 et calculez f (x). Si f (x) > 0, f aura une racine entre a et
x. Si f (x) < 0, f aura une racine entre x et b. La répétition de cette procédure
définira des intervalles de plus en plus petits qui convergeront vers une racine.
Écrivez un programme déclaratif pour résoudre ce problème avec les techniques
du calcul itératif.
➤ Exercice 4 — Une SumList itérative
Réécrivez la fonction SumList de la section 3.4.2 pour qu’elle soit itérative
avec les techniques développées pour Length.
➤ Exercice 5 — Les invariants d’état
Écrivez un invariant d’état pour la fonction IterReverse.
➤ Exercice 6 — Une autre Append
La section 3.4.2 définit la fonction Append en faisant de la récursion sur le
premier argument. Que se passe-t-il si nous essayons de faire de la récursion
avec le deuxième argument ? Voici une solution possible :
18. Cet exercice vient de [1].
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.9 Exercices
179
3.9 EXERCICES
➤ Exercice 1 — La valeur absolue des nombres réels
Nous voulons définir une fonction Abs qui calcule la valeur absolue d’un nombre
réel. La définition suivante est fausse :
fun {Abs X} if X<0 then ˜X else X end end
Pourquoi ? Comment la corrigeriez-vous ?
Indice : Le problème est trivial.
➤ Exercice 2 — Les racines cubiques
Ce chapitre utilise la méthode de Newton pour calculer les racines carrées. La
méthode peut être étendue pour calculer des racines de tout degré. Par exemple, la
méthode suivante calcule les racines cubiques. Soit une estimation g de la racine
cubique de x, une estimation améliorée est donnée par (x/g
2 + 2g)/3. Écrivez
un programme déclaratif pour calculer les racines cubiques avec la méthode de
Newton.
➤ Exercice 3 — La méthode du demi-intervalle
18
La méthode du demi-intervalle est une technique simple mais puissante pour
trouver des racines de l’équation f (x) = 0, où f est une fonction réelle continue.
L’idée est la suivante : si nous avons des nombres réels a et b tels que f (a) <
0 < f (b), alors f doit avoir au moins une racine entre a et b. Pour la localiser,
prenez x = (a + b)/2 et calculez f (x). Si f (x) > 0, f aura une racine entre a et
x. Si f (x) < 0, f aura une racine entre x et b. La répétition de cette procédure
définira des intervalles de plus en plus petits qui convergeront vers une racine.
Écrivez un programme déclaratif pour résoudre ce problème avec les techniques
du calcul itératif.
➤ Exercice 4 — Une SumList itérative
Réécrivez la fonction SumList de la section 3.4.2 pour qu’elle soit itérative
avec les techniques développées pour Length.
➤ Exercice 5 — Les invariants d’état
Écrivez un invariant d’état pour la fonction IterReverse.
➤ Exercice 6 — Une autre Append
La section 3.4.2 définit la fonction Append en faisant de la récursion sur le
premier argument. Que se passe-t-il si nous essayons de faire de la récursion
avec le deuxième argument ? Voici une solution possible :
18. Cet exercice vient de [1].
© Dunod – La photocopie non autorisée est un délit