Découvrez le fonctionnement des algorithmes

Pour communiquer avec un ordinateur, vous avez d’abord besoin d’un langage. Entre humains, il existe beaucoup de langues différentes qui ont chacune leur usage. Nous avons d’ailleurs plusieurs familles de langues organisées souvent autour d’un alphabet : les langues indo-européennes (dont le français, l’espagnol ou l’anglais), les langues sino-tibétaines (dont le mandarin), les langues sémitiques (dont l’arabe), etc.

Ces langues partagent très souvent bien plus qu’un alphabet. Vous voyez où je veux en venir : par exemple, en français nous utilisons des verbes quand nous voulons exprimer une action. On utilise aussi des noms pour désigner les objets ou les personnes : une chaise, un tableau, une fille.

Les langages de programmation utilisent une logique très semblable. Dans ce cours, nous nous intéresserons à la programmation structurée qui est un des paradigmes de programmation les plus connus.

En programmation structurée, nous découpons un problème en micro tâches indépendantes les unes des autres, et modulaires. C’est exactement ce que nous sommes en train de faire !

Les noms : les variables

Une variable est une manière de faire référence à un objet. Dans le langage courant, c’est exactement ce que nous appelons "nom". Qu’est-ce qu’un mot, sinon une étiquette que nous avons collée sur un objet pour pouvoir y faire référence plus tard ? Une variable a donc une valeur, et un mot qui permet d'accéder à cette valeur. Vous pouvez donc soit lire la valeur soit la modifier.

Nous pouvons par exemple créer deux variables dans notre algorithme pour compter le nombre de déplacements et le score du joueur, qu’on aura initialisés à 0 au début du programme.

Vous pouvez déclarer l’ensemble des variables dans le pseudo-code dans une section dédiée aux variables ; cela permet de donner une indication des différentes variables de l'algorithme. Vous placerez cette section juste avant le mot-clé Début  , comme ceci :

Algorithme DéclarerVariable
Variable
    déplacement ← 0
    score ← 0
Début
Fin

Mettons-nous d’accord sur la manière de mettre à jour les variables, à travers ce tableau qui résume les différentes possibilités :

Prenons le labyrinthe ci-dessous, et essayons de construire l’algorithme qui permet de rejoindre la case d’arrivée. Il faudra prendre en compte la mise à jour de chaque variable.

Voici le pseudo-code :

Algorithme variable
Variable
    déplacement ← 0
    score ← 0
Début
    Déplacement à droite
    déplacement ← déplacement + 1
    score ← score + 10
    Déplacement en haut
    déplacement ← déplacement + 1
    score ← score + 10
    Déplacement en haut
    déplacement ← déplacement + 1
    score ← score + 10
    Déplacement à gauche
    déplacement ← déplacement + 1
    score ← score + 20
Fin

Ainsi, à la fin du jeu, la variable déplacement  contient la valeur 4, et la variable score  contient la valeur 50.

Les verbes : les fonctions

À présent, voyons comment simplifier la mise à jour des deux variables en regroupant les instructions dans un seul même bloc. Vous avez sûrement pu le remarquer, nous avons dû écrire plusieurs fois les instructions qui permettent de changer les valeurs des deux variables.

Nous allons utiliser ce qu’on appelle, en programmation, une fonction. Il s’agit d’un bloc qui regroupe plusieurs actions. Vous pouvez réutiliser ce bloc autant de fois que vous le voulez en invoquant son nom. Une fonction peut aussi être vue comme une moulinette qui va prendre des informations en entrée, les traiter et en renvoyer d’autres en sortie. C’est en quelque sorte un mini-algorithme.

Lorsqu'une fonction est "appelée", le programme "quitte" la section de code en cours et commence à exécuter la première ligne à l'intérieur de la fonction. 

Nous allons maintenant créer notre fonction à partir des critères suivants :

Nous pouvons décrire cette fonction à l’aide du pseudo-code :

Fonction maj_déplacement_score(déplacement, score, point_de_déplacement)
Début
    déplacement ← déplacement + 1
    score ← score + point_de_déplacement
Fin

Vous remarquerez qu’il n’y a pas de différence avec la description d’un algorithme en pseudo-code, sauf que nous avons ajouté entre parenthèses les paramètres d’entrée. Vous pouvez ajouter avant la fin de la fonction, avec le mot-clé Retourner  , les valeurs de sortie, s’il y en a.

Nous utiliserons  la fonction maj_déplacement_score pour modifier notre algorithme précédent ainsi :

Algorithme variable
Variable
    déplacement ← 0
    score ← 0
Début
    Déplacement à droite
    maj_déplacement_score(déplacement, score, 10)
    Déplacement en haut
    maj_déplacement_score(déplacement, score, 10)
    Déplacement en haut
    maj_déplacement_score(déplacement, score, 10)
    Déplacement à gauche
    maj_déplacement_score(déplacement, score, 20)
Fin

À vous de jouer

Contexte

Reprenons notre périple dans le labyrinthe.

Considérons le pseudo-code suivant qui dirige les déplacements du joueur dans le labyrinthe :

Algorithme déplacement
Variable
    déplacement ← 0
    score ← 0
Début
    Déplacement en haut
    Déplacement en haut
    Déplacement à droite
    Déplacement à gauche
    Déplacement en bas
    Déplacement en bas
Fin

Vous allez mettre en place dans cet exercice une fonction permettant de calculer votre score selon le nombre de déplacements effectués.

Consignes

Reprenez le pseudo-code ci-dessus et adaptez-le en fonction des consignes suivantes :

• Un déplacement incrémente la variable déplacement  de 1.

• Incrémentation du score  en fonction du sens de déplacement : 

  • à gauche :  50 points / le nombre de déplacements 

  • à droite :  70 points  / le nombre de déplacements 

  • en haut :  25 points  / le nombre de déplacements 

  • en bas :  90 points  / le nombre de déplacements 

• Si le joueur passe à nouveau sur une même case, il faut décrémenter le score de 25 points.

• Si le joueur revient à la case Départ, le score  est réinitialisé à 0.

Votre objectif : 

1. Créez l’algorithme qui prend en compte l’ensemble des consignes ci-dessus. N’hésitez pas à écrire à côté de chaque instruction la valeur courante des variables déplacement  et score  .

2. Créez une fonction qui permet de mettre à jour les variables déplacement  et score  .

3. Créez une fonction qui permet de réinitialiser la variable score  à 0.

4. Adaptez votre algorithme avec les deux nouvelles fonctions.

Vérifiez votre travail

Voici les quatre étapes à suivre pour obtenir le résultat final de cet exercice :

Première étape : création de l'algorithme de déplacement

Algorithme déplacement
Variable
    déplacement ← 0
    score ← 0
Début
    Déplacement en haut
    déplacement ← déplacement + 1
    score ← score + 25
    Déplacement en haut
    déplacement ← déplacement + 1
    score ← score + 25
    Déplacement à droite
    déplacement ← déplacement + 1
    score ← score + 70
    Déplacement à gauche
    déplacement ← déplacement + 1
    score ← score + 50 - 25 (Le joueur revient sur une case)
    Déplacement en bas
    déplacement ← déplacement + 1
    score ← score + 90 - 25 (Le joueur revient sur une case)
    Déplacement en bas
    déplacement ← déplacement + 1
    score ← score + 90 - 25 (Le joueur revient sur une case)
    score ← 0 (Le joueur est revenu à la case départ donc score = 0)
Fin

Seconde étape : création de la fonction de mise à jour des variables déplacement et score

Fonction maj_déplacement_score(déplacement, score, point_de_déplacement)
Début
    déplacement ← déplacement + 1
    score ← score + (point_de_déplacement / déplacement)
Fin

Troisième étape : création de la fonction de réinitialisation du score

Fonction réintialiser_score(score)
    Début -
    score ← 0
Fin

Quatrième étape : adaptation de l'algorithme avec les deux fonctions précédentes

Algorithme déplacement
Variable
    déplacement ← 0
    score ← 0
Début
    Déplacement en haut
    maj_déplacement_score(déplacement, score, 25)
    Déplacement en haut
    maj_déplacement_score(déplacement, score, 25)
    Déplacement à droite
    maj_déplacement_score(déplacement, score, 70)
    Déplacement à gauche
    maj_déplacement_score(déplacement, score, 50 - 25)  // Retour en arrière de 25 points
    Déplacement en bas
    maj_déplacement_score(déplacement, score, 90 - 25)  // Retour en arrière de 25 points
    Déplacement en bas
    maj_déplacement_score(déplacement, score, 90 - 25)
    réinitialiser_score(score)
Fin

En résumé

• La plupart des langages de programmation ont une structure de base similaire les uns aux autres.

• Les variables sont utilisées pour stocker des informations à référencer et à manipuler dans un programme informatique.

• Une fonction est simplement un "morceau" de code que vous pouvez réutiliser, plutôt que de le réécrire plusieurs fois.

• Les fonctions "prennent" généralement des données en entrée, les traitent et "renvoient" un résultat.

Vous avez découvert le monde des variables et comment simplifier votre algorithme en le découpant en fonctions. Il est maintenant temps de tester vos connaissances à l’aide d’un petit quiz dans le chapitre suivant. Bonne chance !