Université Bordeaux 1 Licence Informatique 2005/2006

Initiation à l'algorithmique
 
TD 6

Exercice 6.1

Donner une version récursive des fonctions Puissance, Modulo, QuotientEntier, PGCD (voir feuille 1)

Exercice 6.2

Donner une version récursive des fonction Moyenne, Minimum, IndiceDuMaximum, Insere, EstCroissant, EstTrié, InserDansUnTableauCroissant (voir feuille 4)

Exercice 6.3

Le nombre de combinaisons de n éléments pris p à p est défini par :

$$\forall n > 0, ~ C_n^0=C_n^n=1; ~~ \forall n,p,~ 0<p<n, ~ C_n^p = C_{n-1}^{p-1} + C_{n-1}^{p}$$

Écrire une fonction récursive calculant le coefficient binomial $C_n^p$.
Évaluer sa complexité.
Écrire une fonction itérative de calcul de $C_n^p$ utilisant le principe du triangle de Pascal.
Peut-on utiliser un tableau à une dimension pour effectuer ce calcul ?
Écrire la fonction correspondante. Évaluez la complexité de cette fonction.

Exercice 6.4

T est un tableau de n entiers.
Écrire une fonction qui construit un tableau RANG tel que RANG[i] soit l'indice dans T du I-ième élément dans l'ordre croissant. (Le tableau T ne doit être modifié à aucun moment.)

Exercice 6.5

E est l'ensemble des entiers de 1 à n.
Toute partie de E peut être représentée par un tableau [1..n] de booléens.
Écrire les fonctions implémentant les opérations suivantes (où A et B représentent deux parties de E et x un élément de E) :

• EstVide(A)
• Appartient(x, A)
• Vider(A)
• Intersection(Res,A,B)
• Complementaire(Res,A)
• Union(Res,A,B)
• DifférenceSymétrique(Res,A,B)