Tableaux

0 - Préambule

Récupérez le fichier ExempleTableau.java. Il contient une fonction tableauAléatoire qui reçoit en paramètre un générateur aléatoire, et trois entiers n, a et b. Cette fonction fabrique un tableau de n entiers choisis au hasard entre a inclus et b inclus. Vous pouvez récupérer cette fonction pour tester vos solutions aux exercices qui suivent.

Outre la fonction tableauAléatoire, le fichier fourni contient les éléments suivants :

• un commentaire vous indiquant comment générer toujours le même tableau : il suffit de donner une graine entière constante lors de la création du générateur. Cela est fondamental pour debugger (corriger les erreur de votre programme). Si vous constatez que votre programme ne se comporte pas correctement, essayez de lui fournir une graine fixe (42 par exemple). Si vous constatez que le comportement anormal se produit avec cette graine, alors ajoutez des affichages pour comprendre ce qui se passe jusqu'à cerner le bug. Si le comportement anormal ne se produit pas, essayez avec une autre graine (43 par exemple) et recommencez jusqu'à trouver une graine pour laquelle le bug se produit. Sans cette technique, les tableaux sont toujours différents et la recherche de bugs bien plus complexe ;
• un affichage du tableau généré : vous pouvez constater qu'il faut parcourir tous les éléments, pas de magie (pour l'instant).

1 - Quelques méthodes

Le but dans cette partie est d'écrire une classe Tableaux qui contient un ensemble de méthodes (statiques) à utiliser sur les tableaux (il y aura, par exemple, tableauAleatoire dedans). Vous écrirez également au fur et à mesure une classe TestTableaux, dont le contenu est précisé dans la section suivante, pour tester vos méthodes.

Ecrire les méthodes de suivantes dans la classe Tableaux :

• static void afficher(int[] tab)
  affiche le tableau passé en paramètre ;
• static String conversionChaine(int[] tab)
  renvoie une chaîne de caractères représentant le tableau passé en argument. Par exemple si le tableau contient 3 éléments : 1 2 et 3, la méthode retournera la chaîne "[1;2;3]" ;
• static int min(int[] tab) et static int max(int[] tab)
  renvoient respectivement la valeur de minimum et maximum parmi les éléments du tableau tab ;
• static int indiceMin(int[] tab) et static int indiceMax(int[] tab)
  renvoient respectivement l'indice de l'élément de valeur minimum et maximum du tableau (indice de la première occurrence en cas d'égalité) ;
• les quatre méthodes précédentes sont un peu répétitives. Vous avez probablement du copier/coller le texte de la première pour écrire la seconde et ainsi de suite. C'est une mauvaise pratique, en effet, la répétition à l'identique ou presque à l'identique d'une partie du code pose plusieurs problèmes :
  • ceci est propice aux erreurs : on copie/colle, on modifie ce qui doit être modifie mais on oublie de modifier un endroit ;
  • ceci complique la maintenance : le code est plus gros, donc plus difficile à lire ;
  • cela demande des efforts : il faut écrire correctement les quatre méthodes.
  Il est pourtant possible d'écrire ces quatre méthode en une seule, appelée de différentes manières selon le traitement souhaité. Voici quelques indices pour y parvenir :
  • min peut être écrit à partir d'indiceMin (de même pour max avec indiceMax) ;
  • indiceMin et indiceMax font la même chose à l'exception d'une opération : la comparaison permettant de savoir s'il faut conserver l'élément courant comme nouveau minimum ou maximum. Le traitement pourrait être écrit dans une méthode commune prenant un paramètre supplémentaire indiquant quelle comparaison utiliser.
  Regrouper ainsi le code de plusieurs méthodes en une seule s'appelle factoriser, c'est l'une des notions les plus importantes en génie logiciel. Une code bien factorisé est plus facile à écrire, à lire et à tester. Par exemple, le test des quatre méthodes précédentes testera quatre fois la même méthode commune !
• static int indiceDe(int[] tab, int val)
  renvoie l'indice auquel l'entier val est présent et -1 sinon (indice de première occurrence en cas d'occurrences multiples). Avez vous une idée pour factoriser cette méthode avec les quatre précédentes ?
• static int[] listeIndicesMin(int[] tab)
  renvoie le tableau contenant tous les indices auxquels on trouve la plus petite valeur du tableau ;
• static boolean estCroissant(int[] tab)
  renvoie vrai si le tableau est trié dans l'ordre croissant et faux sinon ;
• static int occurrenceMax(int[] tab)
  renvoie l'entier apparaissant le plus de fois dans le tableau. En cas d'égalité, on renverra la plus petite des valeurs parmi les plus présentes. Avez vous vu que, si nous connaissons l'intervalle de valeurs des éléments du tableau (par exemple entre 0 et 100), il est possible d'écrire cette méthode avec un seul parcours ?
• static boolean palindrome(int[] tab)
  renvoie vrai si le tableau est un palindrome : la séquence des éléments du tableau parcourue dans l'ordre est identique à la séquence des éléments du tableau parcouru dans l'ordre inverse ;
• static int retentionEau(int[] tab)
  Imaginez une série de tours mises côte à côte comme des créneaux similaires à ceux de la partie gauche de la figure ci-dessous :
  
  On cherche à calculer efficacement la quantité d’eau qui serait retenue par une telle configuration après une pluie abondante (partie droite de la figure précédente). Ainsi sur l’exemple de la figure, on a 6 unités d’eau retenues après la pluie. La configuration des tours est modélisée par un tableau d’entiers, par exemple : [1,4,2,3,2,5,3,4,2], pour la figure précédente. La fonction retentionEau renvoie le volume d'eau retenu par les tours. Avez vous vu qu'il est possible de déterminer cette quantité en ne parcourant le tableau qu'une seule fois ? (cette question est extraite d'un exercice proposé par Nicolas Catusse et Hadrien Cambazard)

2 - Test

Il est maintenant temps de tester toutes les méthodes que vous avez écrites dans la partie précédente (mais vous l'avez fait en même temps, n'est-ce pas ?). Concevez et écrivez un programme principal (dont la classe est nommée TestTableaux) permettant de tester toutes les méthodes de la partie précédente. Quelque conseils :

• vous n'êtes pas obligé de ne tester que sur des tableaux générés aléatoirement, au contraire. Par exemple, sur le tableau [1, 2, 3], vous savez que la valeur minimum est 1, la maximum est 3, l'indice de la valeur minimum est 0, etc. Cela vous permet de verifier que les méthodes renvoient les bonnes valeurs et effectuant des tests directement dans votre programme ;
• pensez à tester les cas particuliers : tableau vide, valeurs toutes identiques, etc.

        int min = Tableaux.min(monTableau);

3 - Bonus

Quelques méthodes supplémentaires à écrire pour les plus enthousiastes :

• static int sousTableauMax(int [] tab)
  Renvoie la somme des éléments du sous tableau de somme maximale contenu dans tab. On définit un sous tableau d'un autre tableau tab comme un tableau constitué par la séquence d'éléments de tab compris entre i et j où i ≥ 0 et tab.length > j ≥ i. Le sous tableau de somme maximale d'un tableau tab est le sous tableau de tab dont la somme des éléments est maximale.
• static int sousSequenceCroissante(int [] tab)
  Renvoie la longueur de la sous séquence croissante la plus grande contenue dans tab. On définit une sous séquence d'un tableau tab comme une séquence d'éléments de tab d'indices i1, ..., in dans l'ordre où n < tab.length et i1, ..., in est strictement croissante.