Fonctions et tableaux

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

Exercice 1 : Retour vers le futur — Seuls ceux qui passent les tests compteront !

Cet exercice est une reprise de l'exercice 3 du TP 5. Si vous aviez déjà fait cet exercice, vous pouvez passer directement à l'exercice suivant.
Cet exercice est l'occasion d'écrire des fonctions qui prennent d'autres fonctions en argument, et/ou qui renvoient une fonction. Comme d'habitude, on n'oubliera pas de tester chacune des fonctions que l'on aura écrites.

Recopiez la page Web exo1.html dans votre répertoire tp6.
Écrire une fonction estPair qui, étant donné un entier k, renvoie true si k est pair, et false sinon.
Écrire une fonction estCarré qui, étant donné un entier k, renvoie true si k est un carré parfait, et false sinon.
Écrire une fonction comptePairs qui, étant donné un entier n strictement positif, énumère les entiers de 1 à n, compte combien d'entre eux sont pairs, et renvoie le résultat de son décompte.
Écrire une fonction compteCarrés qui, étant donné un entier n strictement positif, énumère les entiers de 1 à n, compte combien d'entre eux sont des carrés parfaits, et renvoie le résultat de son décompte.

Ci-dessus, on a écrit deux fois la même chose, à ceci près qu'on a décompté les entiers pairs dans notre première fonction, et les carrés parfaits dans notre deuxième fonction. Comme la duplication de code est une erreur critique en programmation, il faut revoir les choses.
On va donc réécrire de manière plus professionnelle les fonctions comptePairs et compteCarrés, en créant une fonction compte qui prend un argument test et dont le comportement sera le suivant :

L'argument test sera une fonction qui, à chaque entier k, associe un booléen (c'est-à-dire true ou false) ; les fonctions estPair et estCarré sont deux exemples de telles fonctions.
Le résultat de compte(test) devra être une fonction qui, étant donné un entier n strictement positif, énumère les entiers de 1 à n, compte combien d'entre eux ont été associés au booléen true par la fonction test, et renvoie le résultat de son décompte ; par exemple, la fonction comptePairs peut désormais se réécrire const comptePairs2 = compte(estPair).

Comment écrire la fonction compteCarrés2, qui fait la même chose que compteCarrés, à partir des fonctions test et estCarré ? Cette réécriture est censée prendre une seule ligne de code.
Écrire la fonction compte.
Bien vérifier que les fonctions comptePairs2 et compteCarrés2 réécrites à partir de la fonction compte se comportent comme les fonctions comptePairs et compteCarrés.
Écrire, en une seule ligne de code, une fonction compte1mod3 qui, étant donné un entier n strictement positif, énumère les entiers de 1 à n, compte combien d'entre eux sont congrus à 1 modulo 3, et renvoie le résultat de son décompte.

Exercice 2 : Tableaux

Manipulations simples de tableau

Recopiez la page Web exo2.html dans votre répertoire tp6.
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 exo2.html que vous venez de récupérer (Une piste pour le trouver : regarder la source…)
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 les valeurs des cases 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.
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.

Les questions qui suivent utilisent les fonctions sur les tableaux que vous avez vues ce lundi en cous magistral. Comme c'est tout récent, elles sont donc facultatives.

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.
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.
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é).
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 3 : MinMax, génération aléatoire et calcul rapide

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

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.
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 ?

On peut améliorer le code obtenu à plusieurs 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 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());
```
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 minmax3.