Notations et pseudo-code | Exercices corrigés

Concepts & Exercices

\(\text{Algorithme} \leftarrow \text{Variables} + \text{Instructions} + \text{Structures de contrôle}\)

Structure d'un algorithme

📦

Variables : Espaces mémoire nommés pour stocker des données.

🔄

Affectation : Opération qui attribue une valeur à une variable.

❓

Conditionnelle : Structure SI/SINON pour prendre des décisions.

🔁

Boucles : Structures Pour/TantQue pour répéter des instructions.

Exercice 1

Écrire un algorithme qui calcule la moyenne de 5 notes saisies par l'utilisateur et affiche la mention correspondante.

Exercice 2

Écrire un algorithme qui calcule la somme des n premiers entiers naturels en utilisant une boucle TantQue.

Exercice 3

Écrire un algorithme qui détermine si un nombre est premier en utilisant des structures conditionnelles et des boucles.

Exercice 4

Écrire un algorithme qui inverse les éléments d'un tableau de 10 entiers en utilisant des boucles et des affectations.

Exercice 5

Écrire un algorithme qui calcule le PGCD de deux nombres en utilisant l'algorithme d'Euclide.

Corrigé : Exercices 1 à 3

1 Calcul de moyenne et mention

Définition :

Moyenne : Somme des valeurs divisée par le nombre de valeurs.

Mention : Classification basée sur des seuils prédéfinis.

Structure de l'algorithme :

Déclaration des variables
Saisie des 5 notes
Calcul de la somme
Calcul de la moyenne
Attribution de la mention selon la moyenne

Algorithme complet

Variables note1, note2, note3, note4, note5, somme, moyenne : réels
Début
  Afficher("Entrez la première note : ")
  Lire(note1)
  Afficher("Entrez la deuxième note : ")
  Lire(note2)
  Afficher("Entrez la troisième note : ")
  Lire(note3)
  Afficher("Entrez la quatrième note : ")
  Lire(note4)
  Afficher("Entrez la cinquième note : ")
  Lire(note5)
  
  somme ← note1 + note2 + note3 + note4 + note5
  moyenne ← somme / 5
  
  Afficher("La moyenne est : ", moyenne)
  
  Si moyenne >= 16 Alors
    Afficher("Mention : Très bien")
  Sinon Si moyenne >= 14 Alors
    Afficher("Mention : Bien")
  Sinon Si moyenne >= 12 Alors
    Afficher("Mention : Assez bien")
  Sinon Si moyenne >= 10 Alors
    Afficher("Mention : Passable")
  Sinon
    Afficher("Mention : Insuffisant")
  FinSi
Fin

Étape 1 : Variables

Déclaration des variables : note1, note2, note3, note4, note5, somme, moyenne

Toutes de type réel pour accepter les décimaux

Étape 2 : Saisie des notes

Instructions Lire pour récupérer les 5 notes

Étape 3 : Calcul

somme ← note1 + note2 + note3 + note4 + note5

moyenne ← somme / 5

Étape 4 : Attribution de la mention

Structure conditionnelle SINON SI pour les seuils

Très bien ≥ 16, Bien ≥ 14, Assez bien ≥ 12, Passable ≥ 10

Réponse finale :

L'algorithme utilise des variables pour stocker les données, des affectations pour les calculs, et des structures conditionnelles pour attribuer la mention.

Règles appliquées :

• Variables : Déclaration explicite des types

• Affectation : Utilisation de l'opérateur ←

• Conditionnelle : Structure SINON SI pour les seuils ordonnés

Point clé 1

Les seuils doivent être ordonnés du plus élevé au plus bas pour que l'algorithme fonctionne correctement

Point clé 2

La structure SINON SI garantit que seule la première condition vraie est exécutée

2 Somme des n premiers entiers

Définition :

Somme des entiers : \(S = 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}\).

Algorithme avec boucle TantQue

Variables n, i, somme : entiers
Début
  Afficher("Entrez la valeur de n : ")
  Lire(n)
  
  somme ← 0  // Initialisation de l'accumulateur
  i ← 1      // Initialisation du compteur
  
  TantQue i <= n Faire
    somme ← somme + i  // Accumulation
    i ← i + 1          // Incrémentation du compteur
  FinTantQue
  
  Afficher("La somme des ", n, " premiers entiers est : ", somme)
Fin

Étape 1 : Variables et initialisation

Variables : n (entrée), i (compteur), somme (accumulateur)

somme ← 0 (initialisation indispensable)

i ← 1 (compteur commence à 1)

Étape 2 : Boucle TantQue

Condition : i ≤ n (continuer tant que i n'a pas dépassé n)

Instruction : somme ← somme + i (addition cumulative)

Incrémentation : i ← i + 1 (avancement du compteur)

Étape 3 : Trace de l'exécution (pour n=5)

i=1: somme=0+1=1, i=2

i=2: somme=1+2=3, i=3

i=3: somme=3+3=6, i=4

i=4: somme=6+4=10, i=5

i=5: somme=10+5=15, i=6

i=6: condition i≤5 fausse, sortie de la boucle

Étape 4 : Alternative avec boucle Pour

Pour i de 1 à n Faire
  somme ← somme + i
FinPour

Réponse finale :

L'algorithme utilise une boucle TantQue pour accumuler les entiers de 1 à n dans une variable somme.

Règles appliquées :

• Initialisation : L'accumulateur doit être initialisé à 0

• Boucle TantQue : Nécessite une condition et une modification de variable

• Invariant : somme contient la somme des entiers de 1 à i-1

Point clé 1

Le compteur doit être incrémenté dans la boucle pour éviter une boucle infinie

Point clé 2

L'accumulateur doit être initialisé avant la boucle

3 Test de primalité

Définition :

Nombre premier : Nombre supérieur à 1 qui n'est divisible que par 1 et lui-même.

Algorithme de test de primalité

Variables n, i, estPremier : entiers
Début
  Afficher("Entrez un nombre : ")
  Lire(n)
  
  Si n <= 1 Alors
    Afficher(n, " n'est pas premier")
  Sinon
    estPremier ← 1  // Supposé premier
    i ← 2           // Premier diviseur potentiel
    
    TantQue (i <= racine_carree(n)) ET (estPremier = 1) Faire
      Si n MOD i = 0 Alors
        estPremier ← 0  // Trouvé un diviseur
      Sinon
        i ← i + 1
      FinSi
    FinTantQue
    
    Si estPremier = 1 Alors
      Afficher(n, " est premier")
    Sinon
      Afficher(n, " n'est pas premier")
    FinSi
  FinSi
Fin

Étape 1 : Cas particuliers

Si n ≤ 1 : n n'est pas premier

Étape 2 : Initialisation

estPremier ← 1 (variable booléenne simulée)

i ← 2 (premier diviseur à tester)

Étape 3 : Optimisation de la boucle

On teste jusqu'à √n car si n a un diviseur > √n, il en a un < √n

Condition de continuation : (i ≤ √n) ET (estPremier = 1)

Étape 4 : Test de divisibilité

Si n MOD i = 0 : i divise n, donc n n'est pas premier

On met estPremier ← 0 pour sortir de la boucle

Étape 5 : Trace de l'exécution (pour n=17)

i=2: 17 MOD 2 ≠ 0, i=3

i=3: 17 MOD 3 ≠ 0, i=4

i=4: 4 > √17 ≈ 4.12, condition fausse, sortie de boucle

estPremier = 1, donc 17 est premier

Réponse finale :

L'algorithme utilise des structures conditionnelles imbriquées et une boucle TantQue pour tester la divisibilité.

Règles appliquées :

• Optimisation : Tester jusqu'à √n suffit pour la primalité

• Booléen simulé : Variable entière pour représenter un état

• Sortie anticipée : Arrêter dès qu'un diviseur est trouvé

Point clé 1

Tester jusqu'à la racine carrée réduit considérablement le nombre d'opérations

Point clé 2

Les structures conditionnelles imbriquées permettent de gérer des cas complexes

Corrigé : Exercices 4 à 5

4 Inversion d'un tableau

Définition :

Inversion de tableau : Permuter les éléments pour inverser l'ordre.

Algorithme d'inversion

Variables tab[10], temp : entiers
Variables i, j : entiers
Début
  // Initialisation du tableau
  Pour i de 0 à 9 Faire
    Afficher("Entrez l'élément ", i, " : ")
    Lire(tab[i])
  FinPour
  
  // Affichage avant inversion
  Afficher("Tableau avant inversion : ")
  Pour i de 0 à 9 Faire
    Afficher(tab[i], " ")
  FinPour
  
  // Inversion du tableau
  i ← 0
  j ← 9  // Dernier indice
  
  TantQue i < j Faire
    temp ← tab[i]      // Échange des éléments
    tab[i] ← tab[j]
    tab[j] ← temp
    
    i ← i + 1          // Avancement des indices
    j ← j - 1
  FinTantQue
  
  // Affichage après inversion
  Afficher("Tableau après inversion : ")
  Pour i de 0 à 9 Faire
    Afficher(tab[i], " ")
  FinPour
Fin

Étape 1 : Initialisation du tableau

Boucle Pour pour remplir le tableau de 10 éléments

Étape 2 : Variables de position

i ← 0 (premier indice)

j ← 9 (dernier indice)

Étape 3 : Boucle d'échange

TantQue i < j : continuer tant que les indices ne se sont pas rencontrés

Échange des éléments tab[i] et tab[j] avec variable temporaire

i ← i + 1 et j ← j - 1 pour avancer les positions

Étape 4 : Trace de l'exécution (exemple)

Tableau initial : [2, 5, 8, 1, 9, 3, 7, 6, 4, 0]

i=0, j=9: échange 2↔0 → [0, 5, 8, 1, 9, 3, 7, 6, 4, 2]

i=1, j=8: échange 5↔4 → [0, 4, 8, 1, 9, 3, 7, 6, 5, 2]

i=2, j=7: échange 8↔6 → [0, 4, 6, 1, 9, 3, 7, 8, 5, 2]

i=3, j=6: échange 1↔7 → [0, 4, 6, 7, 9, 3, 1, 8, 5, 2]

i=4, j=5: échange 9↔3 → [0, 4, 6, 7, 3, 9, 1, 8, 5, 2]

i=5, j=4: condition i

Résultat : [0, 4, 6, 7, 3, 9, 1, 8, 5, 2]

Réponse finale :

L'algorithme utilise une boucle TantQue avec des affectations pour échanger les éléments symétriques du tableau.

Règles appliquées :

• Échange : Utilisation d'une variable temporaire pour permuter

• Indices opposés : i croissant, j décroissant

• Condition d'arrêt : i < j empêche les doubles échanges

Point clé 1

La condition i < j évite d'échanger deux fois le même couple

Point clé 2

Les affectations successives permettent de permuter deux éléments

5 Algorithme d'Euclide

Définition :

PGCD : Plus Grand Commun Diviseur de deux nombres.

Algorithme d'Euclide : PGCD(a,b) = PGCD(b, a MOD b) jusqu'à ce que b = 0.

Algorithme d'Euclide

Variables a, b, reste : entiers
Début
  Afficher("Entrez le premier nombre : ")
  Lire(a)
  Afficher("Entrez le deuxième nombre : ")
  Lire(b)
  
  TantQue b ≠ 0 Faire
    reste ← a MOD b
    a ← b
    b ← reste
  FinTantQue
  
  Afficher("Le PGCD est : ", a)
Fin

Étape 1 : Saisie des nombres

Lecture des deux nombres a et b

Étape 2 : Boucle d'Euclide

TantQue b ≠ 0 : condition de continuation

reste ← a MOD b : calcul du reste

a ← b et b ← reste : décalage des valeurs

Étape 3 : Trace de l'exécution (pour a=48, b=18)

Itération 1: reste=48 MOD 18=12, a=18, b=12

Itération 2: reste=18 MOD 12=6, a=12, b=6

Itération 3: reste=12 MOD 6=0, a=6, b=0

b=0, sortie de boucle, PGCD=6

Étape 4 : Alternative avec récursivité

Fonction PGCD(a, b)
  Si b = 0 Alors
    Retourner a
  Sinon
    Retourner PGCD(b, a MOD b)
  FinSi
FinFonction

Réponse finale :

L'algorithme d'Euclide utilise une boucle TantQue pour calculer le PGCD en remplaçant les nombres par leurs restes successifs.

Règles appliquées :

• Algorithme d'Euclide : PGCD(a,b) = PGCD(b, a MOD b)

• Division euclidienne : Utilisation de l'opérateur MOD

• Itération : Répétition jusqu'à l'obtention d'un reste nul

Point clé 1

L'algorithme d'Euclide est très efficace et converge rapidement

Point clé 2

Les affectations successives permettent de conserver les valeurs nécessaires

Cours bien détaillé

\(\text{Variable} \leftarrow \text{Valeur}\)

Affectation

📦

Variables : Espaces mémoire nommés pour stocker des données.

🔄

Affectation : Attribuer une valeur à une variable avec ←.

❓

Conditionnelle : Structure SI/SINON/SINON SI pour les décisions.

🔁

Boucles : Structures Pour/TantQue/Répéter pour les répétitions.

💡

Conseil : Toujours déclarer les variables avec leur type

🔍

Attention : Vérifier que les boucles ont une condition de sortie

⚡

Astuce : Utiliser des noms de variables explicites

📋

Méthode : Indenter correctement pour la lisibilité

✅

Vérification : Faire une trace d'exécution pour valider

Méthodologie de conception :

Analyse du problème : Identifier les données d'entrée et les résultats attendus
Choix des variables : Déterminer les variables nécessaires
Choix des structures : Sélectionner les structures de contrôle appropriées
Implémentation : Écrire l'algorithme en pseudo-code
Validation : Vérifier avec des exemples concrets

Règles fondamentales :

Les variables doivent être déclarées avant utilisation
Les accumulateurs doivent être initialisés (0 pour addition, 1 pour multiplication)
Les boucles TantQue doivent avoir une condition qui évolue
Les structures conditionnelles doivent couvrir tous les cas possibles
Les variables de contrôle doivent être modifiées dans les boucles

\(\text{SI condition ALORS instruction1 SINON instruction2 FINSI}\)

Structure conditionnelle

Notations et pseudo-codeExercices corrigés

Notations et pseudo-code
Exercices corrigés