CHAPITRE 3

---

auteur: Philippe Moreau (U.P.J.V.)

Exercices

Exercice 4:

On se propose d'examiner un algorithme pour le calcul de la valeur d'un polynôme.

P(X) = A_nXⁿ + A_n-1X^n-1 + ... ... + A₂X² + A₁X + A₀ (sans l'utilisation de l'exponentiation)

On peut, en effet, écrire le polynôme sous la forme suivante (méthode de calcul d'Horner):

P(X)= ((...((A_n*X + A_n-1)*X + A_n-2)*X + ... ... + A₂)*X + A₁)*X + A₀

a) Écrire une fonction qui traduit cet algorithme

b) Donner la complexité en temps de cet algorithme

 

solution de l'exercice 4.

 

 

 

Les trois exercices suivants, vont permettre de comparer des algorithmes résolvant le même problème.

 

Exercice 5: On désire calculer 2^N (sans utiliser l'exponentiation)

1ère Méthode: on écrit que: 2^N = 2 * 2 * 2 *... ... * 2 * 2 (Nfois)

a) Écrire une fonction qui traduit cet algorithme

b) Donner la complexité en temps de cet algorithme

 

solution de l'exercice 5.

 

 

Exercice 6: Le but est toujours de calculer 2^N (sans utiliser l'exponentiation)

2ème Méthode: en utilisant l'algorithme dit de "l'exponentiation indienne"

Le principe de cet algorithme (permettant de calculer X^N )est basé sur les observations suivantes:

- Si N est pair, il suffit de calculer X² puis d'élever celui-ci à la puissance N/2

- Si N est impair, on calcul X² puis on réalise l'opération (X² )(N-1)/2*X

a) Écrire une fonction qui traduit cet algorithme

b) Donner la complexité en temps de cet algorithme

 

 

solution de l'exercice 6.

 

 

Exercice 7: Toujours le calcul de 2^N (sans utiliser l'exponentiation)

3ème Méthode: on écrit que: 2^N = 2^N-1 + 2^N-1

a) Écrire une fonction qui traduit cet algorithme

b) Donner la complexité en temps de cet algorithme

 

solution de l'exercice 7.

 

Observation sur les résultats des trois exercices précédents

Auteur: Philippe Moreau (U.P.J.V.)