Université de Nice-Sophia Antipolis  Deug MASS 2
Algorithmique et Structure de données  2000–2001
TP N^{∘} 6

Tableaux et Tris

1 Tableaux

1.1 Moyenne

Écrire un programme qui calcule la moyenne des éléments d’un tableau donné en paramètre.

Exemple : soit le tableau suivant.

1 3 12 5 14

Le programme renvoie la valeur : 7. La signature est: public float moyenne() ...

1.2 Recherche

– Écrire un programme qui permet de trouver l’indice du deuxième plus grand élément d’un tableau d’éléments distincts.

Exemple : soit le tableau suivant.

5 2 4 1 3

Le programme renvoie la valeur : 2.

– Écrire un programme qui permet de trouver l’indice du nième plus grand élément d’un tableau d’éléments distincts. La méthode aura la signature suivante: public int getNValue(int n) ...

1.3 Occurrence

Écrire un programme qui permet de trouver le nombre d’occurrences de nombres pairs dans un tableau.

Exemple : soit le tableau suivant. 5 2 5 4 5 La méthode, appelée sur ce tableau, renvoie la valeur : 2. La méthode aura la signature suivante: public int occurence() ...

1.4 Permutation

Écrire un programme qui permet de reconnaître si un tableau t est une permutation. Un tableau t de taille n est une permutation si :

– ∀i < j, t[i] ≠ t[j], et

– ∀i, 1 ≤ t[i] ≤ n.

Exemple : le tableau suivant est une permutation.

1 3 5 6 2 4

La méthode renvoie donc la valeur : vrai. Par contre, le tableau qui suit n’est pas une permutation. La méthode renvoie la valeur :

faux.

1 3 5 7 3 2

La signature de cette méthode doit être: public boolean permutation() ...

1.5 Descente

– Écrire un programme qui renvoie le nombre de descentes du tableau

donné en paramètre, c’est-à-dire le nombre de i tels que t[i + 1] < t[i].

Exemple : soit le tableau suivant.

3 2 1 5 4

La méthode renvoie la valeur : 3.

La signature est: public int descente() ...

– Écrire maintenant le programme qui compte le nombre de descentes “générale” dans le tableau, c’est-à-dire qui retournerait la valeur : 2 dans l’exemple précedant : parce qu’il n’y a que deux descentes générales: (3 - 2 - 1) et (5 - 4).

2 Tris

2.1 Tri par sélection

Ecrire une méthode JAVA de tri par sélection en ordre décroissant, en se basant sur le cours.

2.2 Fusion

Ecrire une méthode fusion “intelligente” qui étant donnée deux tableaux triés retourne un tableau trié.