Deug MASS 2 - Année 2000/2001

ALGORITHMIQUE ET STRUCTURES DE DONNEES

TP N$^\circ$ 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 :

• $\forall i < j,\ t[i] \neq t[j]$, et
• $\forall i,\ 1 \leq t[i] \leq 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é.