Aller au contenu principal

Apprendre les algo – Jour 4

Introduction​

Aujourd'hui, nous découvrons deux bases très importantes :

  • les boucles
  • les tableaux

L'idée est simple :

  • une boucle permet de répéter une action
  • un tableau permet de stocker plusieurs valeurs dans une seule variable

Nous allons rester volontairement simples.

1. La boucle​

Définition​

Une boucle est une structure qui permet de refaire plusieurs fois la même instruction.

Elle est utile quand on ne veut pas écrire la même chose encore et encore.

Syntaxe​

Exemple en pseudo-code :

Pour i allant de 1 à 5 faire
  Écrire i
FinPour

Exemple​

Pour i allant de 1 à 3 faire
  Écrire "Bonjour"
FinPour

Résultat :

Bonjour
Bonjour
Bonjour

À retenir​

Une boucle sert à répéter.

2. La boucle pour​

Définition​

La boucle pour est utilisée quand on sait combien de fois on veut répéter une action.

Syntaxe​

Pour compteur allant de début à fin faire
  instruction
FinPour

Exemple​

Pour i allant de 1 à 5 faire
  Écrire i
FinPour

Résultat :

1
2
3
4
5

3. La boucle tant que​

Définition​

La boucle tant que est utilisée quand on veut répéter une action tant qu'une condition est vraie.

Syntaxe​

TantQue condition faire
  instruction
FinTantQue

Exemple​

i ← 1

TantQue i <= 3 faire
  Écrire i
  i ← i + 1
FinTantQue

Résultat :

1
2
3

À retenir​

Avec tant que, il faut penser à faire évoluer la variable, sinon la boucle peut tourner sans fin.

4. Le tableau​

Définition​

Un tableau est une structure qui permet de ranger plusieurs valeurs du même type.

On peut aussi dire, de manière plus formelle, qu'un tableau est une séquence contiguë à longueur explicite.

Cela veut dire simplement deux choses :

  • les éléments sont rangés les uns à la suite des autres
  • le tableau a une taille connue d'avance
Illustration d'un tableau comme séquence contiguë à longueur explicite

Exemple : une liste de notes, une liste de prénoms, une liste de températures.

Autrement dit, dans un même tableau, on évite de mélanger des choses différentes.

Par exemple :

  • un tableau d'entiers contient des nombres entiers
  • un tableau de textes contient des mots ou des phrases

En version très simple :

  • on ne mélange pas des pommes et des bananes dans le même tableau
  • on ne mélange pas des entiers et des chaînes de caractères

Syntaxe​

Exemple d'idée en pseudo-code :

notes = [12, 15, 9, 18]

Chaque case du tableau possède une position qu'on appelle souvent indice.

Exemple​

notes = [12, 15, 9]

Ici :

  • notes[0] = 12
  • notes[1] = 15
  • notes[2] = 9

À retenir​

Un tableau sert à stocker plusieurs valeurs.

5. Parcourir un tableau​

Définition​

Parcourir un tableau, c'est lire ses éléments un par un.

Pour cela, on utilise très souvent une boucle.

Syntaxe​

taille ← ...
i ← 0

TantQue i < taille faire
  Écrire tableau[i]
  i ← i + 1
FinTantQue

Exemple​

notes = [12, 15, 9]
taille ← 3
i ← 0

TantQue i < taille faire
  Écrire notes[i]
  i ← i + 1
FinTantQue

Résultat :

12
15
9

À retenir​

La boucle et le tableau vont souvent ensemble :

  • la boucle répète
  • le tableau stocke

6. Exemple très simple​

Problème​

Afficher tous les nombres d'un tableau.

Solution​

nombres = [4, 7, 10]
taille ← 3
i ← 0

TantQue i < taille faire
  Écrire nombres[i]
  i ← i + 1
FinTantQue

Explication simple​

  • nombres[0] vaut 4
  • nombres[1] vaut 7
  • nombres[2] vaut 10

La boucle permet de lire chaque case sans écrire trois fois Écrire.

7. Les deux schémas à retenir​

Dans les exercices sur les tableaux, on retombe très souvent sur deux réflexes :

  • soit on veut parcourir
  • soit on veut rechercher

Autrement dit, quand vous voyez un exercice sur un tableau, posez-vous d'abord cette question :

  • est-ce que je dois lire toutes les cases ?
  • ou est-ce que je cherche une valeur précise ?

8. Schéma de parcours​

Schéma​

Schéma de parcours d'un tableau

Principe du schéma​

Le parcours consiste à visiter les cases du tableau une par une, du début jusqu'à la fin.

Ici, on ne cherche pas forcément une valeur précise. On veut surtout traiter tous les éléments.

Quand l'utiliser​

On utilise ce schéma quand on veut :

  • afficher tous les éléments
  • calculer une somme
  • compter le nombre d'éléments
  • trouver le minimum ou le maximum

Exemple 1​

Problème : afficher tous les nombres du tableau.

notes = [12, 15, 9]
taille ← 3
i ← 0

TantQue i < taille faire
  Écrire notes[i]
  i ← i + 1
FinTantQue

Ici, on lit chaque case. Donc c'est un schéma de parcours.

Exemple 2​

Problème : calculer la somme des éléments.

notes = [12, 15, 9]
somme ← 0
i ← 0
taille ← 3

TantQue i < taille faire
  somme ← somme + notes[i]
  i ← i + 1
FinTantQue

Écrire somme

Ici encore, on passe sur tout le tableau. Donc c'est aussi un schéma de parcours.

9. Schéma de recherche​

Schéma​

Schéma de recherche dans un tableau

Principe du schéma​

La recherche consiste à avancer case par case jusqu'à trouver la valeur cherchée.

À chaque étape :

  • on regarde la case actuelle
  • on compare avec la valeur cherchée
  • si ce n'est pas bon, on continue
  • si c'est bon, on s'arrête

Le vrai point important ici, c'est qu'on peut écrire la condition directement dans la boucle.

En pseudo-code, cela donne souvent une forme comme celle-ci :

i ← 0

TantQue i != taille et puis tableau[i] != element faire
  i ← i + 1
FinTantQue

Cette écriture est très efficace, parce qu'elle dit en une seule ligne :

  • je continue tant que je ne suis pas à la fin
  • et tant que je n'ai pas encore trouvé l'élément

Dès qu'une des deux conditions devient fausse, on s'arrête, c'est-à-dire qu'on sort de la boucle.

Le et puis​

Le et puis correspond au && dans des langages comme C, C# ou Java.

condition1 et puis condition2

Cela veut dire :

  • on teste d'abord condition1
  • si condition1 est fausse, on s'arrête
  • si condition1 est vraie, alors on teste condition2

Le résultat final reste un ET logique :

  • il faut que condition1 soit vraie
  • et il faut aussi que condition2 soit vraie

Si une seule des deux est fausse, l'ensemble devient faux.

Petite nuance avec le et simple​

Le et simple et le et puis ont la même idée logique : les deux conditions doivent être vraies.

La nuance, c'est la manière d'évaluer :

  • avec et simple, on peut imaginer qu'on regarde les deux côtés
  • avec et puis, on regarde d'abord à gauche
  • si la gauche est fausse, on ne regarde même pas à droite

Cette nuance est très utile quand la partie droite ne doit être testée que si la partie gauche est vraie.

Dans notre schéma de recherche :

i != taille et puis tableau[i] != element

Cela veut dire :

  • i != taille : on n'est pas encore arrivé à la fin du tableau
  • tableau[i] != element : l'élément actuel n'est pas encore celui qu'on cherche

Donc :

  • si on arrive à la fin, on arrête
  • si on trouve l'élément, on arrête
  • et surtout, on évite de lire tableau[i] quand i est déjà arrivé à la fin

Quand l'utiliser​

On utilise ce schéma quand on veut :

  • savoir si une valeur existe dans le tableau
  • trouver la position d'un élément
  • compter combien de fois une valeur apparaît

Exemple 1​

Problème : savoir si 15 est présent.

notes = [12, 15, 9]
i ← 0
taille ← 3

TantQue i != taille et puis notes[i] != 15 faire
  i ← i + 1
FinTantQue

Si i != taille Alors
  Écrire "15 est present"
Sinon
  Écrire "15 n'est pas present"
FinSi
Illustration de la recherche de 15

Comment lire cette boucle simplement​

Prenez un petit cahier et un stylo. Lisez ce passage lentement, en essayant de visualiser le déplacement de i dans le tableau. Notez les valeurs une par une sur papier.

Cette habitude est très importante : si vous comprenez vraiment ce mécanisme aujourd'hui, il vous servira toute votre vie en algorithmique.

Au début, cette boucle peut paraître étrange, parce que dans le bloc TantQue, on ne fait presque rien :

i ← i + 1

En réalité, c'est normal. Le but de cette boucle n'est pas de calculer une somme ni d'afficher. Le but est seulement d'avancer dans le tableau jusqu'à trouver la bonne valeur.

Que veut dire i != taille ?​

Ici, taille = 3, donc le tableau contient 3 cases :

  • notes[0]
  • notes[1]
  • notes[2]

Donc :

  • si i = 0, on est sur la première case
  • si i = 1, on est sur la deuxième case
  • si i = 2, on est sur la troisième case
  • si i = 3, on est après la dernière case

Donc i != taille veut simplement dire :

  • on n'est pas encore arrivé à la fin du tableau

Pourquoi la boucle sort ?​

La boucle continue tant que la partie de gauche reste vraie, puis que la partie de droite reste vraie :

  • d'abord, on n'est pas à la fin
  • ensuite, on n'a pas encore trouvé 15

La boucle s'arrête, c'est-à-dire sort de la boucle, dans deux cas :

  • soit on trouve 15
  • soit on arrive à la fin du tableau

Lecture pas à pas​

Avec notes = [12, 15, 9] :

  • au début, i = 0
  • on regarde notes[0], donc 12
  • 12 n'est pas 15, donc on avance avec i ← i + 1
  • maintenant i = 1
  • on regarde notes[1], donc 15
  • cette fois, on a trouvé
  • la condition de la boucle devient fausse, donc on sort de la boucle

Ici, on cherche une valeur précise. Donc c'est un schéma de recherche.

Exemple 2​

Problème : trouver la position du premier 9.

notes = [12, 15, 9, 9]
i ← 0
taille ← 4

TantQue i != taille et puis notes[i] != 9 faire
  i ← i + 1
FinTantQue

Si i != taille Alors
  position ← i
Sinon
  position ← -1
FinSi

Ici aussi, on cherche une valeur. Donc on est dans un schéma de recherche.

10. Le bon réflexe​

Avant de résoudre un exercice sur un tableau, demandez-vous toujours :

  • Est-ce que je dois parcourir tout le tableau ?
  • Ou est-ce que je dois chercher une valeur ?

Si vous avez ce réflexe, beaucoup d'exercices deviennent plus simples à comprendre.

11. Petit exemple en C#​

Juste pour faire le lien avec C#, voici un exemple très simple :

int[] notes = { 12, 15, 9 };
int i = 0;

while (i != notes.Length && notes[i] != 15)
{
    i++;
}

if (i != notes.Length)
{
    Console.WriteLine("15 est present");
}
else
{
    Console.WriteLine("15 n'est pas present");
}

Ici :

  • notes.Length représente la taille du tableau
  • i++ permet d'avancer dans le tableau
  • la boucle s'arrête si on trouve 15 ou si on arrive à la fin

Le principe reste le même dans les autres langages de programmation, comme C, Java ou C++ :

  • on lit le tableau case par case
  • on avance avec un indice
  • on s'arrête quand on trouve l'élément ou quand on arrive à la fin