Lista del curso Registrarse Inicia sesión

Información

Fecha de entrega Sin fecha de envío
Tiempo límite de envío Sin límite de envío

Etiquetas

Inicia sesión

Inicia sesión

[4.1] Rappel des concepts [Obligatoire]

L'itération

Le principe de l'itération est de pouvoir répéter une séquence d'instructions plusieurs fois. Ce principe peut se matérialiser dans plusieurs structures :

  • la boucle while répète une séquence d'instructions tant qu'une condition d'itération est vraie :

    int nombre = -1;
while (nombre < 0) {
    scanf("%d", &nombre);
}
printf("%d est forcément un nombre positif\n", nombre);

  • la boucle do...while exécute une première fois une séquence d'instructions puis la répète tant qu'une condition d'itération est vraie :

    int nombre;
do {
    scanf("%d", &nombre);
} while (nombre < 0);
printf("%d est forcément un nombre positif\n", nombre);

  • la boucle for est une alternative à la boucle while spécialisée pour itérer un nombre connu ou calculé de fois :

    for (int i = 0; i < 10; i++) {
    printf("%d\n", i);
}

Exemple

Voici une petite visualisation d'un programme écrit en C qui permet de calculer la somme des nombres de 1 à 5 grâce à une boucle for :

Précondition, postcondition et invariant

Chaque boucle qui se termine possède toujours une précondition, une postcondition et un invariant :

  • Précondition (PRE) : Une proposition qui doit être vraie avant l'exécution de la boucle.

    Elle peut être composée de plusieurs prédicats comme dans la précondition x > 0 && y > 2 qui signifie qu'il faut s'assurer que la variable x soit plus grande que 0 et que la variable y soit plus grande que 2 avant que la boucle ne soit exécutée.

  • Postcondition (POST) : Une proposition qui doit être vraie après l'exécution de la boucle.

    Elle peut être composée de plusieurs prédicats comme dans la postcondition \( n \in \mathbb{N} \land n = n_0 \land somme = \sum^{n}_{x = 1} x \) qui signifie qu'après l'exécution de la boucle, la variable n sera un entier naturel égal à sa valeur avant l'exécution de la boucle et la variable somme sera la somme des nombres de 1 à n.

  • Invariant (INV) : Une proposition qui doit être vraie au moment de l'entrée et après chaque itération de la boucle.

    Elle peut être composée de plusieurs prédicats comme dans l'invariant \( n \in \mathbb{N} \land n = n_0 \land 0 \leq i \leq n \land somme = \sum^{i}_{x = 1} x \) qui signifie que au moment de l'entrée dans la boucle et après chaque itération l'exécution de la boucle, la variable n sera un entier naturel égal à sa valeur avant l'exécution de la boucle, la variable i sera inclue entre 0 et n et la variable somme sera la somme des nombres de 1 à i.

En général, il est souvent nécessaire de réaliser quelques instructions avant et après la boucle donc on inclut souvent ces quelques instructions dans le concept de boucle.

Voici donc la liste des différentes parties d'une boucle :

  • Initialisation : La séquence d'instructions juste avant d'entrer dans la boucle qui sert, par exemple, à initialiser des variables temporaires qui sont nécessaires dans la boucle et son invariant mais qui ne sont pas dans la précondition comme des variables dites "compteur".
  • Condition d'itération : C'est la condition qui doit être respectée pour itérer sur la boucle et qui est toujours associée à une condition d'arrêt qui est simplement la négation de cette condition d'itération.
  • Instructions d'itération : La séquence d'instructions qui est réexécutée à chaque itération de la boucle.
  • Clôture : La séquence d'instructions juste après l'exécution de la boucle qui sert, par exemple, à désallouer les variables temporaires qui étaient nécessaires dans la boucle et son invariant mais qui ne le sont plus dans la postcondition.

En résumé, ces différents concepts ressemblent à cela sur une boucle while :

// PRE

// Initialisation

// INV

while (...) {  // Condition d'itération
    // Instructions d'itération
}

// Clôture

// POST
Informations supplémentaires
Souvent, ces concepts ne sont pas directement utilisés par les ordinateurs. Cependant, ils sont importants pour communiquer entre développeurs et ils seront utilisés dans les cours Algorithmique 1 (IHDCB232) et Algorithmique 2 (IHDCB331). Il est donc important que vous sachiez dès maintenant identifier ces différents concepts dans un programme et que vous comprenniez comment ils fonctionnent sur des exemples simples.

Exemple avec un invariant

Ci-dessous, vous pouvez trouver une visualisation d'un programme qui calcule la moyenne de la somme des nombres de 0 à 4 avec une boucle while. Dans celle-ci, vous pouvez voir que la précondition, la postcondition et l'invariant sont respectés quand ils doivent l'être. Plus important, elle permet de visualiser le lien qu'il y a entre les variables de ces propositions, comme le lien entre la variable i et la variable sum dans l'invariant.

Pregunta 1: Différents types de boucles

Vous avez vu au cours trois types de boucle :

  • les boucles 1️⃣ qui s'écrivent comme suit :

    1️⃣ (<CONDITION>) {
    <corps de la boucle>
}

    où la condition est une expression de type 2️⃣ et où le corps de la boucle est une séquence d'3️⃣.

  • les boucles 4️⃣ qui s'écrivent :

    5️⃣ {
    <corps de la boucle>
} 6️⃣ (<CONDITION>);
    ATTENTION!

    Après la dernière condition, il ne faut pas oublier le point-virgule !

  • les boucles 7️⃣ qui s'écrivent comme suit :

    7️⃣ (<initialisation de la variable>; <CONDITION>; <mise à jour de la variable>) {
    <corps de la boucle>
}
Pregunta 2: Condition d'itération 
int j = 0;
int somme = 0;
while (j < n) {
    somme = somme + j;
    j = j + 1;
}

Quel est la condition d'itération dans la boucle ci-dessus ?

Pregunta 3: Condition d'arrêt 
int j = 0;
int somme = 0;
while (j < n) {
    somme = somme + j;
    j = j + 1;
}

Quel est la condition d'arrêt dans la boucle ci-dessus ?

Pregunta 4: CI 
int j = 0;
int somme = 0;
while (j < n) {
    somme = somme + j;
    j = j + 1;
}

Dans la boucle ci-dessus, la variable j est un ... (indice: ça commence par c...)

Pregunta 5: Incrémentation 
int j = 0;
int somme = 0;
while (j < n) {
    somme = somme + j;
    j = j + 1;  // Ici
}

Remplacez l'instruction d'incrémentation du compteur d'itération par une instruction plus courte (qui permet quand même d'incrémenter le compteur).

ATTENTION!
N'oubliez pas le point-virgule à la fin !
Pregunta 6: Incrémentation d'une autre variable 
int j = 0;
int somme = 0;
while (j < n) {
    somme = somme + j;  // Ici
    j = j + 1;
}

Remplacez l'incrémentation de la variable somme par une instruction plus courte qui a le même effet.

ATTENTION!
N'oubliez pas le point-virgule à la fin !
Pregunta 7: Comment ça s'arrête ? 
int main(void) {
    int n;
    scanf("%i", &n);

    while (n >= 0) {
        printf("Vous avez entre le nombre %d.\n", n);
        scanf("%i", &n);
    }

    return 0;
}

La boucle s’arrête quand l’utilisateur entre...

Pregunta 8: Simulation d'un programme 
int nombre = 7;
int n = 20;
int i = 0;
int j = 0;
while (j < n) {
    if (i % nombre == 0) {
        printf("%d\n", i);
        j++;
    }
    i++;
}
printf("%d\n", j);

Simule l'exécution du bout de programme ci-dessus. Pour ce faire, remplis un tableau dont chaque colonne contient l'une des 4 variables et dont chaque ligne représente les numéros successifs des passages dans la boucle :

  • La première ligne (numéro 0) contient donc l'état initial des variables: 7, 20, 0, 0.
  • La seconde ligne (numéro 1) contient les nouvelles valeurs des variables, après un passage dans la boucle.
  • ...

Et ainsi de suite, jusqu'à ce que la boucle se termine.

Ensuite, réponds aux questions qui suivent :

Pregunta 9: Un invariant est vrai...

L'invariant d'une boucle est une proposition qui est vraie... (3 cases à cocher)

Pregunta 10: Invariants 
int main(void) {
    int e;
    scanf("%i", &e);

    if (e < 0) {
        e = 0;
    }

    // PRE: e >= 0

    int i = 0;
    int r = 1;

    while (i < e) {
        r = 2 * r;
        i++;
    }

    // POST: r = 2^e

    printf("%i\n", r);

    return 0;
}

Le programme ci-dessus récupère un nombre entré par l'utilisateur et affiche 2^(ce nombre). Par exemple, si l'utilisateur entre 4 le programme affichera 2^4, soit 16.

Pour chaque invariant ci-dessous, répondez s'il est correct et complet :