Structures de Base des Algorithmes | Mathématiques 1ère
Introduction
Découvrez les structures fondamentales qui constituent les algorithmes : séquence, conditionnelle, itération, et comment elles s'organisent pour résoudre des problèmes
Définition des structures algorithmiques
Qu'est-ce qu'une structure algorithmique ?
Une structure algorithmique est un modèle de construction qui détermine comment les instructions d'un algorithme sont organisées et exécutées. Elle définit le flot de contrôle de l'algorithme. Les structures de base sont :
- Structure séquentielle : instructions exécutées dans l'ordre
- Structure conditionnelle : exécution dépendant d'une condition
- Structure itérative : répétition d'instructions
Structure séquentielle
Instructions exécutées dans l'ordre
2 Opération : effectuer un calcul
3 Entrée/sortie : lire ou afficher des données
4 Suite d'instructions : exécutées dans l'ordre d'écriture
ALGORITHME CalculExpression
VARIABLES a, b, resultat : RÉEL
DÉBUT
AFFICHER "Entrez la valeur de a : "
LIRE a
AFFICHER "Entrez la valeur de b : "
LIRE b
resultat ← a² + 2*a*b + b²
AFFICHER "Le résultat est : ", resultat
FIN
Cet algorithme suit une structure strictement séquentielle : chaque instruction est exécutée dans l'ordre.
Structure conditionnelle
Branchements conditionnels
La structure conditionnelle permet d'exécuter des instructions seulement si une condition est vraie :
SI condition ALORS
instruction1
instruction2
SINON
instruction3
instruction4
FINSI
La condition est une expression logique qui peut être VRAIE ou FAUSSE.
ALGORITHME Maximum
VARIABLES a, b, max : RÉEL
DÉBUT
AFFICHER "Entrez deux nombres : "
LIRE a, b
SI a > b ALORS
max ← a
SINON
max ← b
FINSI
AFFICHER "Le maximum est : ", max
FIN
Cet algorithme utilise une structure conditionnelle pour déterminer le plus grand des deux nombres.
Structure itérative
Boucles et répétitions
La boucle POUR répète un bloc d'instructions un nombre fixe de fois :
POUR i DE 1 À n FAIRE
instruction1
instruction2
FINPOUR
Exemple : afficher les entiers de 1 à 10
La boucle TANT QUE répète tant qu'une condition est vraie :
TANTQUE condition FAIRE
instruction1
instruction2
FINTANTQUE
Exemple : lecture de nombres jusqu'à un nombre négatif
La boucle RÉPÉTER exécute d'abord puis vérifie la condition :
RÉPÉTER
instruction1
instruction2
JUSQU'À condition
Exemple : saisie d'un nombre positif
Exemple complet - Algorithme de tri
Tri par sélection
Implémenter un algorithme de tri par sélection pour ordonner un tableau d'entiers dans l'ordre croissant.
Le tri par sélection consiste à :
- Rechercher le plus petit élément du tableau
- Échanger avec le premier élément
- Rechercher le plus petit élément du reste du tableau
- Échanger avec le deuxième élément
- Répéter jusqu'à la fin du tableau
ALGORITHME TriSelection
VARIABLES tab : TABLEAU[1..n] DE RÉEL
i, j, min_pos, temp : ENTIER
DÉBUT
POUR i DE 1 À n-1 FAIRE
min_pos ← i
POUR j DE i+1 À n FAIRE
SI tab[j] < tab[min_pos] ALORS
min_pos ← j
FINSI
FINPOUR
temp ← tab[i]
tab[i] ← tab[min_pos]
tab[min_pos] ← temp
FINPOUR
FIN
Cet algorithme combine des structures itératives imbriquées et conditionnelles.
Exemple concret - Suite de Fibonacci
Calcul des termes
La suite de Fibonacci est définie par : F(0) = 0, F(1) = 1, et F(n) = F(n-1) + F(n-2) pour n ≥ 2.
On veut calculer le n-ième terme de la suite.
Voici un algorithme utilisant une structure itérative :
ALGORITHME Fibonacci
VARIABLES n, i, a, b, c : ENTIER
DÉBUT
AFFICHER "Entrez le rang n : "
LIRE n
SI n = 0 ALORS
AFFICHER 0
SINON SI n = 1 ALORS
AFFICHER 1
SINON
a ← 0
b ← 1
POUR i DE 2 À n FAIRE
c ← a + b
a ← b
b ← c
FINPOUR
AFFICHER c
FINSI
FIN
Cet algorithme combine structures conditionnelles et itératives.
Structures imbriquées
Imbrication des structures
Les structures peuvent être imbriquées :
- Boucle dans une condition : traitement conditionnel dans une boucle
- Condition dans une boucle : test à chaque itération
- Boucle dans une boucle : structures itératives imbriquées
- Condition dans une condition : tests multiples
ALGORITHME Recherche2D
VARIABLES tab[1..n][1..m] : RÉEL
x : RÉEL
i, j : ENTIER
trouvé : BOOLÉEN
DÉBUT
trouvé ← FAUX
POUR i DE 1 À n FAIRE
POUR j DE 1 À m FAIRE
SI tab[i][j] = x ALORS
trouvé ← VRAI
AFFICHER "Trouvé en position (", i, ",", j, ")"
FINSI
FINPOUR
FINPOUR
SI trouvé = FAUX ALORS
AFFICHER "Élément non trouvé"
FINSI
FIN
Cet algorithme combine des boucles imbriquées et des conditions imbriquées.
Exercice d'application
Problème complet
Écrire un algorithme qui :
- Lit un entier n strictement positif
- Calcule la somme des n premiers entiers impairs
- Si cette somme est un carré parfait, afficher "Carré parfait !", sinon afficher "Pas un carré"
- Le programme doit vérifier si un nombre est un carré parfait en utilisant une boucle
Exemple : pour n = 3, on calcule 1 + 3 + 5 = 9, et 9 est un carré parfait (3²).
Solution de l'exercice
Correction détaillée
1. Calcul de la somme : somme des n premiers impairs = n²
2. Vérification du carré : on teste si la somme est un carré parfait
3. Structure requise : boucle pour la somme, condition pour le test
ALGORITHME SommeImpairsCarre
VARIABLES n, i, somme, k, racine_carree : ENTIER
est_carre : BOOLÉEN
DÉBUT
AFFICHER "Entrez n : "
LIRE n
somme ← 0
POUR i DE 1 À n FAIRE
somme ← somme + (2*i - 1)
FINPOUR
est_carre ← FAUX
k ← 0
TANTQUE k*k ≤ somme FAIRE
SI k*k = somme ALORS
est_carre ← VRAI
FINSI
k ← k + 1
FINTANTQUE
SI est_carre ALORS
AFFICHER "Carré parfait !"
SINON
AFFICHER "Pas un carré"
FINSI
FIN
Cet algorithme utilise des structures itératives imbriquées dans des conditions.
Algorithmes récursifs
Récursion
Un algorithme récursif est une fonction qui s'appelle elle-même pour résoudre un problème. Il se compose de :
- Condition d'arrêt : cas de base qui empêche l'infini
- Appel récursif : appel de la fonction avec des paramètres modifiés
FONCTION factorielle(n)
DÉBUT
SI n = 0 OU n = 1 ALORS
RETOURNER 1
SINON
RETOURNER n * factorielle(n - 1)
FINSI
FINFONCTION
La récursion est une structure alternative aux boucles itératives.
Exercices supplémentaires
Pratiquez davantage
Écrire un algorithme qui calcule le PGCD de deux nombres en utilisant l'algorithme d'Euclide (itératif ou récursif).
Implémenter un algorithme de recherche dichotomique dans un tableau trié en utilisant des structures conditionnelles et itératives.
Créer un algorithme qui lit n notes, calcule la moyenne, le minimum, le maximum et l'écart-type en utilisant des boucles.
Solutions des exercices
Corrections détaillées
ALGORITHME PGCD_iteratif
VARIABLES a, b, reste : ENTIER
DÉBUT
AFFICHER "Entrez a et b : "
LIRE a, b
TANTQUE b ≠ 0 FAIRE
reste ← a MOD b
a ← b
b ← reste
FINTANTQUE
AFFICHER "PGCD = ", a
FIN
Cet algorithme utilise une structure itérative avec une condition d'arrêt.
ALGORITHME RechercheDichotomique
VARIABLES tab[1..n] : RÉEL
debut, fin, milieu : ENTIER
x : RÉEL
trouvé : BOOLÉEN
DÉBUT
debut ← 1
fin ← n
trouvé ← FAUX
TANTQUE debut ≤ fin ET trouvé = FAUX FAIRE
milieu ← (debut + fin) DIV 2
SI tab[milieu] = x ALORS
trouvé ← VRAI
SINON SI tab[milieu] < x ALORS
debut ← milieu + 1
SINON
fin ← milieu - 1
FINSI
FINTANTQUE
SI trouvé ALORS
AFFICHER "Trouvé à la position ", milieu
SINON
AFFICHER "Non trouvé"
FINSI
FIN
Combinaison de structures conditionnelles et itératives.
Résumé
Points clés
- Séquentielle : instructions exécutées dans l'ordre
- Conditionnelle : branchements selon une condition
- Itérative : répétition d'instructions
- Structures imbriquées : une structure dans une autre
- Structures récursives : fonction qui s'appelle elle-même
- Structures complexes : combinaisons multiples
- Identifier les structures dans un algorithme
- Choisir la bonne structure pour chaque situation
- Imbriquer les structures de manière claire
- Respecter les conditions d'arrêt
Conclusion
Félicitations !
Continuez à pratiquer pour renforcer vos compétences