Chapitre 2: Algorithmes et Jeux

Objectifs:

• Savoir développer les jeu ChiFouMi (pierre feuille ciseaux)
• Création d'algorithmes à l'aide de boucles, et de fonctions

Plan du chapitre:

1. Algorithmes
2. Boucles for (Slides du TP)
   • Application: FizzBuzz
   • Application: Devine le nombre
3. Fonctions (Slides du TP)
   • Application: définition et appel de fonctions
   • Exercice: Jeu ChiFouMi

1. Algorithmes

Définition de Wikipedia

« Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat. »

Une recette de cuisine peut être réduite à un algorithme, si on peut réduire sa spécification aux éléments constitutifs :

• des entrées (les ingrédients, le matériel utilisé) ;
• des instructions élémentaires simples, dont l'exécution amène au résultat voulu ;
• un résultat : le plat préparé.

Un casse-tête, tel le Rubik's Cube, peut être résolu de façon systématique par un algorithme qui mécanise sa résolution.

Illustration: algorithme de résolution de Rubik's Cube.

Autre définition, plus concrète, de Gérard Berry

« Un algorithme, c’est tout simplement une façon de décrire dans ses moindres détails comment procéder pour faire quelque chose. [...] Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique (ordinateur…). On ne travaille donc qu’avec un reflet numérique du système réel avec qui l’algorithme interagit.

2. Boucles for

Qu'est-ce qu'une boucle ?

Une boucle permet de répeter plusieurs fois une séquence d'instuctions.

Pour afficher les nombres de 1 à 3 dans la console JavaScript, on pourrait utiliser les instructions suivantes:

console.log(1);
console.log(2);
console.log(3);

Et ça fonctionne très bien !

Par contre, le code deviendrait très fastidieux à écrire (et à lire) dans le cas où on voudrait afficher les nombres de 1 à 10000 !

Pour ce genre de répétition, le mot-clé for permet de définir une seule fois les instructions qui doivent êtres répétées, puis de spécifier combien de fois on souhaite qu'elles soient répétées.

Pour afficher les nombres de 1 à 10000, il suffit donc d'écrire le code suivant:

for ( var monNombre = 1; monNombre <= 10000; monNombre++ ) {
  console.log( monNombre );
}

On pourrait traduire ce code de la manière suivante:

Pour chaque valeur de monNombre, croissant de 1 à 10000 (compris), afficher la valeur de monNombre dans la console.

À quoi servent les boucles ?

Les boucles sont donc très utiles pour éviter les redondances dans un programme (ex: jouer 5 fois le même son, mettre tous les champs d'un formulaire en majuscules...), mais elles sont surtout indispensables dans de nombreuses applications courantes:

• Les jeux tour-par-tour consistent en une boucle qui se termine lorsqu'un joueur remporte la partie;
• Les jeux d'action utilisent une boucle permettant de mettre à jour l'affichage (frame par frame, pour utiliser la terminologie exacte) en fonction des actions du/des joueur(s);
• Ainsi que les algorithmes de tri et de manipulation de données utilisés dans 99% des logiciels.

Javascript fournit quatre mots-clés pour définir des boucles: do, while, until et for. La forme de boucle la plus courante est for car c'est la plus générique / adaptable. Nous allons donc seulement travailler avec des boucles for dans le cadre de ce cours.

Anatomie d'une boucle for en JavaScript

Reprenons l'exemple de boucle que nous avons vu plus haut:

for ( var monNombre = 1 ; monNombre <= 10000 ; monNombre++ ) {
  console.log( monNombre );
}

Cette boucle est définie par:

• l'usage du mot clé for;
• une liste d'instructions (saisie entre accolades {}) à répéter tant que la condition est vraie: console.log( monNombre ); (dans notre exemple, il n'y a qu'une seule instruction, mais on peut en mettre une infinité);
• une condition (expression conditionnelle, comme dans une condition if): monNombre <= 10000;
• une instruction d'itération qui sera exécutée après chaque itération de la boucle: monNombre++ (qui, ici, incrémente la valeur de monNombre, c'est à dire augmente sa valeur de 1);
• et une instruction d'initialisation qui ne sera exécutée qu'une seule fois: var monNombre = 1 (ici, on créée une variable monNombre et on lui affecte la valeur initiale 1).

On appelle itération chaque répétition de la boucle.

Pour synthétiser, voici la syntaxe à utiliser pour définir une boucle for en JavaScript:

for( /* initialisation */ ; /* condition */ ; /* incrémentation */ ) {
  /* instructions à répeter */
}

À noter que, dans la plupart des cas, les boucles sont utilisées pour itérer:

• sur un intervalle (dans notre exemple: nombres entiers entre 1 et 10000),
• ou sur une énumération de valeurs (ex: un tableau/Array, comme on le verra plus tard).

Traçage de l’exécution d'une boucle for

Afin de mieux comprendre le fonctionnement de la boucle for et de la manière de saisir ces trois paramètres, nous allons interpréter une boucle comme le fait un navigateur web (ou tout autre interpréteur JavaScript).

Prenons la boucle for suivante:

console.log('on va boucler');
for ( var i = 0; i < 4; i++ ) {
  console.log('i', i, i < 4);
}
console.log('on a fini de boucler');

Voici la manière dont elle va être interprétée et exécutée par la machine:

console.log('on va boucler');            // => affiche: on va boucler

// interprétation de la boucle => on commence par l'initialisation
var i = 0; // initialisation de la boucle, en affectant 0 à la variable i

// --- première itération de la boucle ---
i < 4 ?                       // condition vraie, car i vaut 0
console.log('i', i, i < 4);   // => affiche: i 0 true
i++;                          // incrémentation => i vaut maintenant 1

// --- seconde itération de la boucle ---
i < 4 ?                       // condition vraie, car 1 < 4
console.log('i', i, i < 4);   // => affiche: i 1 true
i++;                          // incrémentation => i vaut maintenant 2

// --- troisième itération de la boucle ---
i < 4 ?                       // condition vraie, car 2 < 4
console.log('i', i, i < 4);   // => affiche: i 2 true
i++;                          // incrémentation => i vaut maintenant 3

// --- quatrième itération de la boucle ---
i < 4 ?                       // condition vraie, car 3 < 4
console.log('i', i, i < 4);   // => affiche: i 3 true
i++;                          // incrémentation => i vaut maintenant 4

// --- cinquième itération de la boucle ---
i < 4 ?                       // condition fausse, car i==4 => fin de boucle

// boucle terminée => on interprète les instructions suivantes.
console.log('on a fini de boucler');     // => affiche: on a fini de boucler

Il est très pratique de décomposer une boucle de cette manière lorsqu'elle ne se comporte pas comme voulu. (débogage)

Interrompre l'exécution d'une boucle: break

Dans certains cas, il est pratique d'interrompre l'exécution d'une boucle, pendant l'exécution d'une de ses itérations (tel que définie entre les accolades de définition de la boucle).

for (var i = 0; i < 10; i++) {
  var commande = prompt('entrez une commande');
  if (commande === 'quitter') {
    break; // => on sort de la boucle for, la suite programme continue de s'exécuter (après ses accolades du for)
  }
}

Cependant, l'usage de break est non recommandé, car il rend la logique plus complexe à comprendre en lisant le code. Il est généralement possible et plus élégant d'intégrer la condition de sortie dans la condition de la boucle.

var commande;
for (var i = 0; i < 10 && commande !== 'quitter'; i++) {
  commande = prompt('entrez une commande');
}

Ici, on a intégré la condition à l'aide de l'opérateur logique &&, donc la boucle continuera d'itérer tant que i < 10 ET que commande !== 'quitter'.

Application: FizzBuzz

Algorithme à implémenter

À implémenter étape par étape:

1. Écrire un programme qui affiche les nombres de 1 à 199 (compris) dans la console.
2. Pour les multiples de 3, afficher Fizz au lieu du nombre.
3. Pour les multiples de 5, afficher Buzz au lieu du nombre.
4. Pour les nombres multiples de 3 et 5, afficher uniquement FizzBuzz.

Pour ne pas s'embrouiller, il est recommandé de:

• commencer par écrire la logique d'une seule itération, avant de la faire se répéter à l'aide d'une boucle;
• écrire sous forme de pseudo-code (en langue française), avant de l'implémenter en JavaScript.

Trace d'exécution de l'algorithme

On devrait obtenir les lignes suivantes dans la console:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

... et ainsi de suite, jusqu'à 199.

Comment savoir si un nombre est multiple d'un autre ?

Pour savoir si un nombre est multiple de 3 et/ou de 5, nous allons utiliser deux fonctions fournies ci-dessous:

function estMultipleDeTrois(nombre) {
  return nombre % 3 === 0;
}
function estMultipleDeCinq(nombre) {
  return nombre % 5 === 0;
}

Après avoir copié-collé la définition de ces deux fonctions dans la console JavaScript, vous pouvez les utiliser de la manière suivante:

estMultipleDeTrois(2); // => retourne false, car 2 n'est pas multiple de 3
estMultipleDeTrois(6); // => retourne true, car 6 est un multiple de 3
estMultipleDeCinq(6); // => retourne false, car 6 n'est pas un multiple de 5
estMultipleDeCinq(15); // => retourne true, car 15 est un multiple de 5

Vous pouvez alors appeler ces fonctions dans les parenthèses de vos conditions if, car, comme une expression de comparaison de valeurs, un appel de fonction retourne une valeur qui est vraie (true) ou fausse (false).

Exemple:

var monNombre = 5; // valeur fournie en guise d'exemple
if (estMultipleDeCinq(monNombre)) {
  console.log('monNombre est multiple de 5');
} else {
  console.log('monNombre n\'est pas multiple de 5');
}

Solution

Application: Devine le nombre

Fonctionnement du jeu à implémenter

• En début de partie, l'ordinateur va choisir un nombre aléatoire entre 0 et 100.
• Le joueur a droit à 10 tentatives pour deviner ce nombre.
• À chaque tentative:
  • Si le nombre saisi est inférieur à celui de l'ordinateur, afficher Plus grand.
  • Si le nombre saisi est supérieur à celui de l'ordinateur, afficher Plus petit.
  • Si le joueur a réussi à deviner le bon nombre, afficher Bravo !.
• La partie continue jusqu'à ce que le joueur gagne ou épuise ses 10 tentatives.

Pour implémenter ce jeu:

• vous allez avoir besoin d'interagir avec l'utilisateur, et donc d'utiliser les mots-clés prompt et alert;
• il est recommandé de commencer par écrire le code d'une seule itération (sans utiliser de boucle), et de le tester en donnant des valeurs arbitraires à vos variables, pour simuler chaque cas.

Exemple de déroulement d'une partie

Nombre saisi par le joueur: 10
Réponse de l'ordinateur: Plus grand
Nombre saisi par le joueur: 20
Réponse de l'ordinateur: Plus petit
Nombre saisi par le joueur: 16
Réponse de l'ordinateur: Bravo !

Comment obtenir un nombre aléatoire

Pour obtenir un nombre aléatoire entier entre 0 et 100:

Math.round(Math.random() * 100)

Libre à vous de stocker cette valeur dans une variable, si vous avez besoin de la comparer à d'autres valeurs, par exemple.

Solution

3. Fonctions

Introduction

Comme en mathématiques, une fonction transforme des paramètres (en "entrée") en une valeur de résultat (la "sortie"), lorsqu'elle est appelée. Avant de pouvoir l'appeler, on la définit par une suite d'instructions qui déterminera cette valeur de résultat, en fonction des paramètres qui lui seront passés.

Définir une fonction permet de regrouper des instructions JavaScript, afin qu'elles puissent être exécutées à différentes occasions, sans avoir à dupliquer le code correspondant.

Par exemple, sur le web, les fonctions JavaScript sont utilisées par le développeur pour définir le comportement que doit suivre le navigateur lorsque l'utilisateur effectue certaines actions (ex: saisie dans un champ, clic sur un bouton, soumission d'un formulaire).

Définition et appel de fonction

On définit une fonction de la manière suivante:

function nomDeLaFonction (parametre1, parametre2, parametre3 ...) {
  // instructions javascript
  // pouvant utiliser les paramètres parametre1, parametre2 et parametre3
  return resultat;
}

Par exemple:

function multiplierParDeux (nombre) {
  return nombre * 2;
}

Pour exécuter une fonction, il faut l'appeler en citant son nom, et en lui fournissant des valeurs pour chacun des paramètres entre parenthèses.

Par exemple:

var resultat = multiplierParDeux(3); // => le paramètre nombre vaut 3 => la variable resultat vaudra 6

Comme pour une variable, l'appel à une fonction sera remplacé la valeur qu'elle renvoie, au moment de l'exécution du programme. Contrairement aux variables, cette valeur dépendra de la valeur des paramètres passés à la fonction.

Ainsi, il est possible de passer le résultat de l'appel d'une fonction en paramètre d'une fonction.

Exemple de substitution d'un appel de fonction par sa valeur de retour:

resultat = multiplierParDeux(multiplierParDeux(3)); // équivaut à:
resultat = multiplierParDeux(3 * 2); // qui équivaut à:
resultat = (3 * 2) * 2; // qui vaut finalement:
resultat = 12;

Et, avec une autre valeur passée en paramètre:

var resultat = multiplierParDeux(multiplierParDeux(4)); // équivaut à:
var resultat = multiplierParDeux(4 * 2); // qui équivaut à:
var resultat = (4 * 2) * 2; // qui vaut finalement:
var resultat = 16;

Importance de return

Quand on exécute une fonction depuis une console JavaScript, la valeur retournée par cette fonction est affichée dans la console. Il ne faut pas pour autant confondre le mot clé return et la fonction console.log.

En effet:

• console.log peut être appelée plusieurs fois depuis un même définition de fonction, mais chaque appel de fonction ne peut résulter qu'en une seule valeur de retour spécifiée par return,
• l'usage de return permet à l'appelant d'une fonction de disposer de la valeur résultante comme il le souhaite: il peut par exemple décider d'afficher cette valeur dans la console, ou dans un alert, ou même de la stocker dans une variable. Or, si la définition de cette fonction affiche la valeur résultante dans la console au lieu d'utiliser return, il sera impossible pour l'appelant de récupérer cette valeur résultante dans son programme.

Pratique: Définition et appel de fonction

Dans cette partie de mise en pratique, nous allons définir ensemble plusieurs fonctions, et les tester en les appelant.

Développer:

• une fonction diviserParDeux qui retourne la moitié de la valeur passée en paramètre. Tests:

  • diviserParDeux(2) === 1;
  • diviserParDeux(4) === 2;
  • var n = Math.random(); diviserParDeux(n) === n / 2;

• une fonction somme qui retourne la somme des deux paramètres qui lui seront passés. Tests:

  • somme(1, 1) === 2;
  • somme(1, 2) === 3;
  • somme(2, 1) === 3;
  • var n = Math.random(); somme(n, 1) === n + 1;

• une fonction signe qui retourne la chaîne de caractères positif, négatif ou nul, selon le signe de la valeur passée en paramètre. Tests:

  • signe(-1) === 'negatif';
  • signe(0) === 'nul';
  • signe(Math.random()) === 'positif';

• une fonction factorielle qui retourne le produit de tous les entiers consécutifs entre 1 et l'entier passé en paramètre (compris). Exemple: factorielle(3) retourne le résultat de 1 * 2 * 3, soit 6. Tests:

  • factorielle(0) === 0;
  • factorielle(1) === 1;
  • factorielle(3) === 6;
  • factorielle(4) === 24;

Solution

Bugs et tests unitaires: comment tester une fonction

Appeler une fonction ajoute de l'incertitude et parfois de l'imprévisibilité au comportement du code, car cela revient à déléguer une fonctionnalité à une autre partie du code (la définition de la fonction appelée).

Afin de se rassurer sur le bon fonctionnement d'une fonction et éviter les bugs, il est important de tester les fonctions qu'on utilise.

Un bug est un comportement imprévu causant des anomalies et/ou l'interruption de l'exécution du programme. Il est généralement causé par une erreur d'implémentation ou une réalisation trop naïve (c.a.d. ne couvrant pas certains cas qui peuvent se produire).

Exemple d'implémentation naïve pouvant causer un bug:

function multiplierParDix (nombre) {
  return nombre + '0'; // on ajoute un zéro à la fin du nombre
}
multiplierParDix(2);   // => 20 => OK
multiplierParDix(3);   // => 30 => OK
multiplierParDix(0.5); // => 0.50 => BUG! on voulait obtenir 5 dans ce cas

Dans l'exemple ci-dessus, nous avons effectué trois tests d'appel de notre fonction multiplierParDix, et l'un d'eux nous a permis de détecter un bug dans notre fonction.

Afin de réduire le nombre de bugs potentiels d'une fonction, et donc de se rassurer sur son bon fonctionnement, il est important d'écrire et exécuter plusieurs tests unitaires, et penser intelligemment aux cas limites, les cas qui pourraient le plus probablement causer un bug.

Écrire un test unitaire pour une fonction consiste à:

• décrire un exemple d'usage de cette fonction, en précisant la valeur résultante attendue pour certaines valeurs de paramètres,
• implémenter l'appel de cette fonction, et comparer la valeur résultante à celle qui est attendue.

Lors de l'exécution du test unitaire, si la valeur de la comparaison détermine si la fonction fonctionne comme prévue sur l'exemple de ce test.

Par exemple, on pourrait définir les trois tests unitaires suivants pour valider notre fonction multiplierParDix:

multiplierParDix(2) === 20;  // => false (car '20' différent de 20)
multiplierParDix(3) === 30;  // => false (car '30' différent de 30)
multiplierParDix(0.5) === 5; // => false (car '0.50' différent de 0.5)

Avec la définition de la fonction multiplierParDix fournie plus haut, aucun de ces tests ne passe. C'est à dire que chaque test d'égalité sera false.

En revanche, les tests unitaires passeront avec la définition suivante de cette même fonction:

function multiplierParDix (nombre) {
  return nombre * 10;
}
multiplierParDix(2) === 20;  // => true => OK
multiplierParDix(3) === 30;  // => true => OK
multiplierParDix(0.5) === 5; // => true => OK

À retenir: Un test unitaire est un exemple d'appel permettant de vérifier qu'une fonction se comporte comme prévu dans un cas donné, en comparant le résultat effectivement retourné au résultat qui devrait être retourné.

Valeur et affectation d'une fonction

Nous avons vu que l'appel d'une fonction consiste à mentionner son nom, suivi de paramètres exprimés entre parenthèses. Et que cet appel est remplacé par la valeur retournée par son exécution.

// définition de la fonction multiplierParDeux()
function multiplierParDeux (nombre) {
  return nombre * 2;
}

// appel de la fonction multiplierParDeux(), en passant le nombre 3 en paramètre
var resultat = multiplierParDeux(3);

// la valeur retournée par l'appel de la fonction (6) est affectée à résultat

Ainsi, multiplierParDeux(3) est remplacé par sa valeur de retour: 6, après l'exécution de la fonction multiplierParDeux à laquelle on a passé la valeur littérale 3 comme valeur du paramètre appelé nombre.

Pour rappel, une variable Javascript est remplacée par la dernière valeur qui lui a été affectée. Ainsi, si la valeur 6 a été affectée à la variable maVariable à l'aide de l'instruction maVariable = 6;, les mentions suivantes de maVariable seront remplacée par sa valeur 6.

En Javascript, une fonction est une valeur, au même titre qu'un nombre ou une chaîne de caractères. Elle peut donc aussi être attribuée à une variable.

Ainsi, il est possible d'affecter la fonction multiplierParDeux à la variable maVariable:

maVariable = multiplierParDeux;

...et de l'appeler de la manière suivante:

maVariable(3); // => retourne la valeur 6;

Il est donc aussi possible d'affecter une fonction anonyme à une variable:

var multiplierParTrois = function (nombre) {
  return nombre * 3;
};

... ce qui est équivalent à écrire:

function multiplierParTrois (nombre) {
  return nombre * 3;
}

Exercice: Jeu ChiFouMi

Fonctionnement du jeu à implémenter

À chaque manche, l'ordinateur et le joueur choisissent chacun un élément parmi pierre, feuille ou ciseaux.

Un point est donné à celui qui a choisi l'élément le plus fort, sachant que:

• ciseaux > feuille (les ciseaux coupent la feuille)
• pierre > ciseaux (la pierre casse les ciseaux)
• feuille > pierre (la feuille enveloppe la pierre)

Si l'ordinateur et le joueur ont choisi le même élément, aucun d'eux n'emporte de point.

Exemple de déroulement d'une manche

• l'ordinateur choisit secrètement pierre (parmi les trois valeurs d'éléments possibles);
• le joueur est invité à saisir son choix => il tape feuille;
• l'ordinateur affiche feuille car c'est l'élément qui l'emporte (la feuille enveloppe la pierre).

Phase 1: Implémentation d'une manche

Pour implémenter le code d'une manche, nous allons:

• définir une fonction comparer(choix1, choix2) qui renvoie le nom de l'élément gagnant, entre les deux passés en paramètres;
• appeler cette fonction, en passant les choix de l'ordinateur et du joueur en paramètres, afin de savoir lequel des deux a remporté la manche.

Pour vous aider, le site codecademy propose un guide interactif: Créez un "Pierre, feuille, ciseaux".

Si vous ne souhaitez pas utiliser ce site, voici une proposition d'étapes à suivre:

1. Dessiner l'arbre de décision d'une manche: nom de l'élément gagnant en fonction de deux éléments choisis;
2. Transformer l'arbre de décision en conditions if imbriquées, en fonction de la valeur de deux variables: choix1 et choix2;
3. Chaque condition de dernier niveau va afficher dans la console le nom de l'élément qui remporte la manche;
4. Transférer ces conditions dans la définition d'une fonction comparer(choix1, choix2) qui retourne le nom de l'élément gagnant à l'aide de return (au lieu de l'afficher dans la console), parmi les deux passés en paramètres;
5. Tester cette fonction en lui passant chaque combinaison possible de valeurs du jeu en paramètres;
6. En dehors de la définition de la fonction, créer les variables choixOrdi et choixUtilisateur;
7. Faire en sorte que choixOrdi ait pour valeur un des trois éléments, choisi de manière aléatoire, et que choixUtilisateur soit saisi par l'utilisateur à l'aide de prompt();
8. Appeler la fonction comparer(), puis afficher dans la console la valeur de son résultat (l'élément qui remporte la manche), à partir des choix de l'ordinateur et du joueur.

Phase 2: Partie en 3 manches, et scores

Après avoir implémenté une manche à l'aide de la fonction comparer(), faites en sorte que le joueur puisse jouer 3 manches d'affilée et que le score final du joueur et de l'ordinateur soient affichés dans la console en fin de partie.

Pour cela:

1. Créer les variables scoreOrdi et scoreJoueur;
2. Après l'affichage du résultat de l'appel à comparer() dans la console, incrémenter une de ces variables, en fonction de qui a remporté la manche;
3. Mettre le code correspondant à une manche dans une boucle for, de manière à ce qu'il s'exécute 3 fois d'affilée;
4. En fin de partie, afficher qui a remporté la partie: 'ordi', 'joueur' ou 'aucun', en fonction des scores.

Solution de la phase 1

Solution de la phase 2