Université Bordeaux 1 Licence Informatique 2004/2005

Initiation à l'algorithmique
 
TD 4

Dans tous les exercices, NMAX représente la taille du tableau. Pour chacun des exercices, on étudiera la complexité des algorithmes utilisés.

Exercice 4.1
Écrire une fonction qui retourne la valeur moyenne des éléments d'un tableau contenant $n$ nombres réels (  $1 \leq ~n~ \leq NMAX$ ).

Exercice 4.2
Écrire une fonction qui retourne la valeur du plus petit élément d'un tableau contenant $n$ nombres entiers distincts (  $1 \leq ~n~ \leq NMAX$ ).

Exercice 4.3
Écrire une fonction qui retourne l'indice du plus grand élément d'un tableau contenant $n$ nombres réels distincts (  $1 \leq ~n~ \leq NMAX$ ).

Exercice 4.4
Écrire une fonction qui insère un élément donné $e$ à la position $k$ d'un tableau contenant $n$ nombres entiers distincts (  $1\leq~k~ \leq ~n+1~ \leq NMAX$ ). L'ordre initial du tableau sera conservé.

Exercice 4.5
Écrire une fonction qui teste si un tableau de réels est trié ou non. Cette fonction retournera un booléen (Vrai ou Faux suivant le cas).

Exercice 4.6
Soit t un tableau de taille $NMAX$ contenant au maximum $n$ entiers ($n ~<~NMAX$) rangés dans l'ordre croissant.
Écrire une fonction qui insère un nouvel élément $e$ dans le tableau t en respectant l'ordre croissant.

Exercice 4.7
On considère une suite de $n$ nombres entiers rangées dans un tableau. Écrire une fonction permettant d'enlever de la suite toute occurrence d'un élément $x$.
Exemple: si le tableau contient la suite:

$$2, -7, 4, 5, 12, 10, 4, 2, 4, 132, -18, 19$$

et si $x$ vaut 4, après l'exécution de la fonction le tableau contiendra la suite:

$$2, -7, 5, 12, 10, 2, 132, -18, 19$$

Exercices complémentaires

Exercice 4.8
Écrire une fonction qui inverse l'ordre des éléments d'un tableau d'entiers.
Exemple: si le tableau contient la suite:

$$2, -7, 4, 5, 12, 10, 4, 2, 4, 132, -18, 19$$

après l'exécution de la fonction le tableau contiendra la suite:

$$19, -18, 132, 4, 2, 4, 10, 12, 5, 4, -7, 2$$

Exercice 4.9
P est le polynôme défini par : $P(X)~=~a_0 + a_1X + a_2X^2 + \ldots + a_nX^n$
Ce polynôme de degré $n$ est représenté par un tableau de nombres réels de dimension n+1, tel que l'élément d'indice $k$ du tableau est le coefficient $a_k$.
Par exemple, le polynôme $Q(X)~=~5X^4 - 3X +1$ est représenté par un tableau contenant $1, -3, 0, 0, 5$
Écrire une fonction qui évalue pour toute valeur x du paramètre, le polynôme P(x) en utilisant l'algorithme de Horner.
Rappel : Algorithme de Horner
Pour evaluer le polynome $P(X)~=~a_0 + a_1X + a_2X^2 + \ldots+a_{n-1}X^{n-1} + a_nX^n$, il suffit de remarquer que $P(X)~=~((\ldots((a_nX+a_{n-1})X+a_{n-2})\ldots+a_2)X+a_1)X+a_0$