# Boucles Imbriquées
> [!video] Vidéo explicative
> <iframe width="560" height="315" src="https://www.youtube.com/embed/oy1FOOU1_uQ?si=I0ug8Qargx8ZJXzw" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
## Introduction
En programmation, les boucles permettent d'exécuter un bloc d'instructions de manière répétée. Lorsque la logique d'un algorithme nécessite des répétitions au sein d'autres répétitions, on utilise des **boucles imbriquées**. Ce concept est fondamental pour traiter des structures de données multidimensionnelles ou pour générer des combinaisons d'éléments. Il s'appuie sur votre compréhension des boucles simples et des principes de la logique combinatoire.
## 1. Concept des Boucles Imbriquées
> [!definition] Définition
> Une **boucle imbriquée** est une structure de contrôle où une boucle (dite *interne*) est placée à l'intérieur du corps d'une autre boucle (dite *externe*). Pour chaque itération de la boucle externe, la boucle interne exécute toutes ses propres itérations.
L'exécution d'une boucle imbriquée suit un schéma précis :
1. La boucle externe commence sa première itération.
2. La boucle interne commence et exécute toutes ses itérations de A à Z.
3. Une fois la boucle interne terminée, la boucle externe passe à sa deuxième itération.
4. La boucle interne recommence et exécute de nouveau toutes ses itérations.
5. Ce processus se répète jusqu'à ce que la boucle externe ait terminé toutes ses itérations.
> [!note] Remarque
> Il est possible d'imbriquer plus de deux boucles (par exemple, trois boucles pour un tableau 3D), bien que cela devienne rapidement complexe et coûteux en ressources.
## 2. Structure en Pseudo-code
La structure générale d'une boucle imbriquée peut être représentée comme suit :
```pseudo
POUR chaque_élément_de_boucle_externe FAIRE
{
// Instructions de la boucle externe
POUR chaque_élément_de_boucle_interne FAIRE
{
// Instructions de la boucle interne
// Ces instructions s'exécutent pour chaque combinaison
// des éléments des boucles externe et interne
}
// Instructions de la boucle externe après l'exécution complète de la boucle interne
}
```
Ou avec des boucles `TANT_QUE` :
```pseudo
i = début_externe
TANT_QUE i < fin_externe FAIRE
{
// Instructions de la boucle externe
j = début_interne
TANT_QUE j < fin_interne FAIRE
{
// Instructions de la boucle interne
j = j + pas_interne
}
// Instructions de la boucle externe
i = i + pas_externe
}
```
## 3. Exemple Concret
### 3.1. Génération de Paires
Les boucles imbriquées sont utiles pour générer toutes les paires possibles à partir d'un ensemble d'éléments.
> [!example] Exemple : Afficher toutes les paires (i, j)
> ```pseudo
> POUR i DE 1 À 3 FAIRE
> {
> POUR j DE 1 À 3 FAIRE
> {
> AFFICHER "(" + i + ", " + j + ")"
> }
> }
>
> // Sortie :
> // (1, 1)
> // (1, 2)
> // (1, 3)
> // (2, 1)
> // (2, 2)
> // (2, 3)
> // (3, 1)
> // (3, 2)
> // (3, 3)
> ```
## 4. Performance et Complexité
> [!warning] Attention
> L'utilisation de boucles imbriquées a un impact significatif sur la performance de votre algorithme. Le nombre total d'opérations est le produit du nombre d'itérations de chaque boucle.
Si la boucle externe s'exécute $N$ fois et la boucle interne $M$ fois, le bloc d'instructions de la boucle interne sera exécuté $N \times M$ fois.
Pour deux boucles imbriquées qui parcourent chacune $N$ éléments, la complexité temporelle est typiquement de l'ordre de $O(N^2)$. Cela signifie que le temps d'exécution augmente quadratiquement avec la taille des données, ce qui peut devenir très lent pour de grandes valeurs de $N$.
> [!tip] Astuce
> Toujours évaluer la nécessité d'une boucle imbriquée. Parfois, des algorithmes plus efficaces existent pour résoudre le même problème avec une meilleure complexité (par exemple, $O(N \log N)$ ou $O(N)$).
## Résumé
Les boucles imbriquées sont un outil puissant pour gérer des répétitions complexes et des structures de données multidimensionnelles.
Elles sont essentielles pour des tâches comme le parcours de matrices, la génération de combinaisons ou la recherche exhaustive.
Cependant, il est crucial de comprendre leur impact sur la performance des algorithmes. Ces principes fondamentaux se retrouveront dans tous les langages de programmation, y compris Python, où seule la syntaxe changera.
## 🗓️ Historique
> **Dernière mise à jour :** `26 octobre 2025`
> **Rédigé par :** [[Julien DUQUENNOY]]