[LOGO]

Tableaux et filter, map, reduce


Comme pour les TPs précédents, on vous demande de créer un répertoire tp5 qui contiendra les exercices de cette feuille de TP et de faire un compte rendu de TP en HTML.

Exercice 1 : Tableaux

Manipulations simples de tableau

  1. Recopiez la page Web exo1.html dans votre répertoire tp5.
    Expliquez ce que fait le code sans pour autant regarder le code de graph.js.
    Note : pour tester, vous devez récupérer aussi le fichier graph.js et le placer correctement par rapport au fichier exo1.html que vous venez de récupérer (Une piste pour le trouver : regarder la source…)
  2. La suite de cet exercice consiste à compléter chaque question en écrivant un code à l'endroit des 'TODO'.
    On cherche à écrire une fonction addThree qui prend en paramètre un tableau et retourne un nouveau tableau qui contient le même nombre de cases que le tableau pris en paramètre et dont la valeur de chaque case est la valeur de la case de même index du tableau pris en paramètre augmentée de trois.
    Par exemple, si le tableau initial contient [11, 21, 5, -13, 2, 12, 19, 5], alors le résultat de l'appel à addThree doit être un nouveau tableau avec les valeurs [14, 24, 8, -10, 5, 15, 22, 8].
    Si cela vous aide, vous pouvez dans un premier temps écrire l'algorithme en pseudo-code, puis dans un deuxième temps, transformez le pseudo-code en JavaScript.
    Attention ! Votre fonction ne doit pas modifier le tableau d'origine.
  3. En fait, le code que l'on a écrit n'est pas très générique : si l'on doit ajouter 4 à chaque case ou alors multiplier la valeur des cases par 2, il faut dupliquer le code avec un copier/coller et changer l'opération à effectuer.
    Comme on n'est pas des barbares, on se dit que l'on pourrait réutiliser la même fonction pour tous ces cas. On va pour cela créer une fonction intermédiaire.
    Donc dans un premier temps, écrivez une fonction applyForEachElement qui prend deux arguments (un tableau et une fonction) et qui, pour chaque élément du tableau, appelle la fonction en lui donnant l'élement en guise de paramètre.
    Une fois que applyForEachElement marche, écrivez une nouvelle version de addThree, addThree2 qui va utiliser applyForEachElement, vérifiez que le résultat est identique.
  4. Il y a toutes les chances que votre fonction applyForEachElement contienne une boucle for. Cependant, on peut éviter d'écrire cette boucle explicitement, en utilisant la méthode forEach sur un tableau : écrire la fonction applyForEachElement2 pour utiliser la méthode forEach, puis l'utiliser pour écrire une nouvelle version de addThree, nommée addThree3.
  5. Que fait la méthode map si on l'appelle sur un tableau ?
    Comment peut-on l'utiliser pour écrire addThree ?
    Écrivez addThree en utilisant la méthode map et vérifiez que l'on obtient le même résultat que précédemment.
  6. On souhaite afficher les valeurs du tableau trié en utilisant la méthode sort sur un tableau.
    Rappelez en quoi la méthode sort est différente des méthodes map et filter.
    Écrivez la fonction sortedArray qui renvoie un nouveau tableau avec les valeurs triées (Attention ! Le tableau pris en paramètre ne doit pas être modifié).
  7. On veut afficher les valeurs du tableau seulement si celles-ci sont positives ou nulles.
    Sachant que l'on peut utiliser la méthode filter sur un tableau, écrivez la fonction positiveArray qui renvoie un tableau ne contenant que les valeurs positives ou nulles du tableau pris en paramètre.

Exercice 2 : MinMax

On cherche à calculer le minimum et le maximum d'un tableau sans parcourir le tableau plusieurs fois.
Avant de commencer, recopiez la page Web exo2.html dans votre répertoire tp5 .

  1. On cherche à écrire une fonction minmax qui prend en paramètre un tableau, calcule le minimum et le maximum de ce tableau et renvoie les deux valeurs sous forme d'un nouveau tableau à 2 cases dont la première case est le minimum et la seconde case est le maximum.
    Pour des questions d'efficacité, on veut que le calcul du minimum et du maximum soit fait lors du même parcours du tableau.
    Écrivez, dans un premier temps, l'algorithme que vous allez implanter en pseudo-code, puis écrivez le code JavaScript correspondant.
    Note : il existe les fonctions Math.min et Math.max.
  2. Au lieu d'écrire la boucle à la main, on peut vouloir directement utiliser l'opérateur spread (…) pour calculer le minimum et le maximum du tableu.
    Écrivez le code de minmax2 qui utilise cet opérateur. Si l'on utilise cette fonction, combien de fois aura-t-on parcouru le tableau ? Cela satisfait-il les contraintes posées en début d'exercice ?
  3. Une autre manière de procéder consiste à utiliser la méthode reduce sur un tableau qui permet d'effectuer un même calcul sur chaque valeur.
    Note : comme ici, on s'intéresse au maximum et au minimum en même temps, la valeur propagée devra contenir ces deux valeurs.
    Quelle doit être la valeur passée en second paramètre à reduce ?
    Quelle doit être la valeur propagée pour chaque case dans le cas où le tableau est [8, 2, 4, 0, 3, 9, 1, 5, 7, 6] ?
    Écrivez le code de minmax3 qui appelle la méthode reduce.
    Note 2 : vous pouvez vérifier que les valeurs intermédiaires de la valeur propagée sont bonnes avec console.log.
  4. En fait, retourner un tableau avec 2 cases stockant le minimum et le maximum, n'est pas terrible comme convention, il faut mieux renvoyer un dictionnaire avec les clefs min et max.
    Donnez la syntaxe Javascript qui permet de créer un dictionnaire avec 3 comme valeur de min et 7 comme valeur de max.
    Enfin, écrivez la fonction minmax4 utilisant des dictionnaires comme valeur propagée à la place d'un tableau à 2 cases.
    Note : Si vous n'avez pas vu les dictionnaires en cours, vous êtes invités à lire le cours correspondant, mais vous pouvez aussi sauter cette question sans vous sentir trop coupables.

Exercice 3 : Génération aléatoire et calcul rapide

On peut améliorer le code de l'exercice précédent à deux endroits.
Au lieu de tester avec un tableau écrit « en dur », tirer aléatoirement un tableau permettrait de tester avec davantage de tableaux différents.
De plus, l'algorithme minmax écrit précédemment n'est pas le plus efficace. Il existe une version qui fait moins de comparaisons (et qui est bien sûr plus compliquée à écrire).
On utilisera pour cela la page Web exo3.html.

  1. On souhaite pouvoir mélanger les cases d'un tableau dans le but de tester plus de combinaisons.
    L'idée de l'algorithme de mélange est la suivante : pour chaque case i, on tire un nombre aléatoire entre i et n - 1 (n étant le nombre de cases du tableau) et l'on va permuter (échanger si vous préférez) la case courante avec la case à l'index du nombre que l'on vient de tirer aléatoirement.
    Si l'on fait cela pour toutes les cases, le tableau sera mélangé (et on peut même s'offrir la joie de démontrer que ce tableau est bien échantillonné uniformément au hasard parmi tous les tableaux possibles).
    Écrivez dans un premier temps une fonction swap qui permet d'échanger deux cases du tableau.
    Puis écrivez la fonction randomArray qui mélange les valeurs du tableau pris en paramètre.
    Note : tirer un nombre aléatoire entre 0 (inclus) et n (exclu) en JavaScript se fait avec la fonction suivante :
    const random = n => Math.floor(n * Math.random());
  2. Il est possible de diminuer le nombre de tests fait par la fonction minmax. En effet, si au lieu de faire évoluer le min et le max pour chaque case du tableau, on commence par lire deux valeurs de cases consécutives, regarder quelle est la plus grande puis la comparer avec le max, dans ce cas, la valeur la plus petite ne doit être comparée qu'avec le min donc chaque case n'a pas besoin d'être comparée et avec le max et avec le min.
    Écrivez dans un premier temps l'algorithme en pseudo-code.
    Note : pour éviter de dupliquer le code, on peut écrire le code si une valeur est plus grande que l'autre et dans l'autre cas, permuter les valeurs (attention, les valeurs, pas les cases du tableau) pour se retrouver dans le même cas.
    Vérifiez que votre algo fonctionne que le nombre de cases soit pair ou impair.
    Enfin, écrivez la fonction minmax5.