CSC 3101 – Algorithmique et langage de programmation

Portail informatique

Histogramme (∼30mn – moyen – entraînement)

Écrivez un programme permettant de représenter un histogramme sur un écran (voir figure ci-dessous) à partir d'un tableau tab d'entiers.

* * * * * ** * * ** +++++*++++ ** * ** * * * *

L'histogramme doit être cadré en haut à gauche de l'écran. Chaque colonne i contient un nombre d'étoiles égal à la valeur de tab[i]. L'axe des abscisses est représenté comme une ligne de '+', mais si tab[i] vaut 0, votre programme doit afficher un '*'. L'histogramme représenté sur la figure correspond au tableau suivant :

int[] tab = { -1, -3, 2, -2, 3, 0, 4, 2, -2, -1 };

On fait l'hypothèse que le tableau est compatible avec la taille de l'écran.

Pour réussir l'exercice, il faut savoir que System.out.print(char c) affiche le caractère c sans ajouter retour à la ligne, alors que System.out.println() affiche juste un retour à la ligne.

Commencez par écrire une boucle qui trouve les valeurs minimum et maximum du tableau.

De façon à imposer que la ligne 0 soit affichée même lorsque le minimum et le maximum sont strictement supérieurs (resp. strictement inférieurs) à 0, vous devez pré-initialiser ces minimums et maximums à 0 avant de parcourir le tableau.

À l'aide d'un indice line parcourez l'ensemble des valeurs se trouvant entre le maximum et le minimum dans le sens décroissant. À chaque tour de boucle, vous devez parcourir, avec l'indice col, le tableau et afficher le caractère adéquat.

  • Vous devez afficher une étoile dans trois cas :
    • si line est égal à 0 et si tab[col] est égal à 0,
    • si line est strictement supérieur à 0, si tab[col] est strictement supérieur à 0 et si tab[col] est plus grand que line,
    • si line est strictement inférieur à 0, si tab[col] est strictement inférieur à 0 et si tab[col] est plus petit que line.
  • Si vous n'affichez pas une étoile, vous devez afficher un caractère blanc lorsque line est différent de 0, et le caractère + lorsque line est égal à 0.

Quelle est la complexité de l'algorithme en fonction du tableau utilisé ? Réfléchissez à quelles sont les propriétés du tableau qui doivent entrer en jeu.
Nous allons avoir besoin de la taille n du tableau, ainsi que de la valeur maximale M et la valeur minimale N.
Trouver le maximum et le minimum est linéaire en la taille du tableau. Pour afficher l'histogramme, nous devons faire une boucle entre le min et le max. Dans cette boucle, nous avons une autre boucle sur la taille du tableau. La complexité finale est donc 𝒪((Mm)*n)\mathcal{O}((M - m) * n).