Les tableaux et les matrices sont les briques fondamentales pour implémenter des algorithmes de traitement de données à grande échelle. Cette section met en pratique les notions acquises dans la Partie 3 à travers trois problèmes d'ingénierie algorithmique classiques : le tri à bulles optimisé, la recherche dichotomique et l'analyse d'un carré magique.
Problème 1 : L'Algorithme du Tri à Bulles optimisé (Bubble Sort)#
Énoncé#
Le tri d'une liste d'éléments est l'un des problèmes les plus fréquents en informatique. L'algorithme du tri à bulles parcourt le tableau en comparant chaque paire d'éléments consécutifs et les échange s'ils sont dans le mauvais ordre. Les éléments les plus grands "remontent" ainsi progressivement vers la fin du tableau, comme des bulles d'air dans l'eau.
Écrivez une fonction void TrierBulles(int tab[], int taille) qui trie un tableau d'entiers par ordre croissant, en intégrant un drapeau d'optimisation (flag) pour interrompre le tri dès que le tableau est ordonné.
flowchart TD
Start[Début du tour de boucle] --> Compare["Comparer tab[j] et tab[j+1]"]
Compare --> Test{"tab[j] > tab[j+1] ?"}
Test -- Oui --> Swap["Échanger tab[j] et tab[j+1]\nActiver drapeau echange = true"]
Test -- Non --> Next[Passer à la paire suivante]
Swap --> Next
Next --> EndPass{"Fin du parcours ?"}
EndPass -- Non --> Compare
EndPass -- Oui --> CheckFlag{"echange == true ?"}
CheckFlag -- Oui --> Start
CheckFlag -- Non --> TriFini["Tableau déjà trié !\nArrêt anticipé O(N)"]
Solution complète en C#
#include <stdio.h>
#include <stdbool.h>
void AfficherTableau(const int tab[], int taille)
{
printf("[ ");
for (int i = 0; i < taille; i++)
{
printf("%d ", tab[i]);
}
printf("]\n");
}
void TrierBulles(int tab[], int taille)
{
for (int i = 0; i < taille - 1; i++)
{
bool echange_effectue = false;
// Les i derniers éléments sont déjà à leur place définitive
for (int j = 0; j < taille - 1 - i; j++)
{
if (tab[j] > tab[j + 1])
{
// Échange des deux éléments
int temporaire = tab[j];
tab[j] = tab[j + 1];
tab[j + 1] = temporaire;
echange_effectue = true;
}
}
// Si aucun échange n'a eu lieu pendant tout le tour, le tableau est déjà trié !
if (!echange_effectue)
{
break;
}
}
}
int main(void)
{
int donnees[] = {64, 34, 25, 12, 22, 11, 90};
int taille = sizeof(donnees) / sizeof(donnees[0]);
printf("Tableau initial : ");
AfficherTableau(donnees, taille);
TrierBulles(donnees, taille);
printf("Tableau ordonne : ");
AfficherTableau(donnees, taille);
return 0;
}
Problème 2 : Recherche Dichotomique (Binary Search)#
Énoncé#
Alors qu'une recherche séquentielle naïve sur un tableau non trié examine un à un les \(N\) éléments en \(\mathcal{O}(N)\), la recherche dichotomique sur un tableau préalablement trié divise par deux l'espace de recherche à chaque étape, atteignant une efficacité fulgurante en \(\mathcal{O}(\log_2 N)\).
Implémentez une fonction int RechercheDichotomique(const int tab[], int taille, int cible) qui renvoie l'indice de l'élément recherché ou -1 s'il est absent.
#include <stdio.h>
int RechercheDichotomique(const int tab[], int taille, int cible)
{
int gauche = 0;
int droite = taille - 1;
while (gauche <= droite)
{
// Calcul du milieu (évite les dépassements de capacité d'entiers)
int milieu = gauche + (droite - gauche) / 2;
if (tab[milieu] == cible)
{
return milieu; // Trouvé !
}
else if (tab[milieu] < cible)
{
// La cible est dans la moitié droite
gauche = milieu + 1;
}
else
{
// La cible est dans la moitié gauche
droite = milieu - 1;
}
}
return -1; // Cible introuvable
}
int main(void)
{
int catalogue_ids[] = {102, 115, 220, 305, 412, 530, 680, 799, 950};
int n = sizeof(catalogue_ids) / sizeof(catalogue_ids[0]);
int recherche1 = 412;
int recherche2 = 500;
int pos1 = RechercheDichotomique(catalogue_ids, n, recherche1);
int pos2 = RechercheDichotomique(catalogue_ids, n, recherche2);
printf("Recherche de l'ID %d : %s (indice %d)\n",
recherche1, (pos1 != -1) ? "TROUVE" : "INEXISTANT", pos1);
printf("Recherche de l'ID %d : %s\n",
recherche2, (pos2 != -1) ? "TROUVE" : "INEXISTANT");
return 0;
}
Problème 3 : Détecteur de Carré Magique (Magic Square)#
Énoncé#
Un carré magique d'ordre \(N\) est une matrice carrée \(N \times N\) telle que la somme des nombres de chaque ligne, de chaque colonne et des deux diagonales principales soit rigoureusement identique. Cette somme commune est appelée la constante magique : $\(M = \frac{N(N^2 + 1)}{2} \quad (\text{pour } N = 3, \, M = 15)\)$
Écrivez un programme qui valide si une matrice donnée est un carré magique.
#include <stdio.h>
#include <stdbool.h>
#define N 3
bool VerifierCarreMagique(const int mat[N][N])
{
// 1. Calcul de la constante de référence sur la première ligne
int somme_reference = 0;
for (int j = 0; j < N; j++)
{
somme_reference += mat[0][j];
}
// 2. Vérification des lignes
for (int i = 1; i < N; i++)
{
int somme_ligne = 0;
for (int j = 0; j < N; j++)
{
somme_ligne += mat[i][j];
}
if (somme_ligne != somme_reference) return false;
}
// 3. Vérification des colonnes
for (int j = 0; j < N; j++)
{
int somme_colonne = 0;
for (int i = 0; i < N; i++)
{
somme_colonne += mat[i][j];
}
if (somme_colonne != somme_reference) return false;
}
// 4. Vérification des deux diagonales
int diag_principale = 0;
int diag_secondaire = 0;
for (int i = 0; i < N; i++)
{
diag_principale += mat[i][i];
diag_secondaire += mat[i][N - 1 - i];
}
if (diag_principale != somme_reference || diag_secondaire != somme_reference)
{
return false;
}
return true;
}
int main(void)
{
// Le célèbre carré magique d'Albrecht Dürer (ordre 3)
int carre[N][N] = {
{8, 1, 6},
{3, 5, 7},
{4, 9, 2}
};
printf("--- VERIFICATION DU CARRE MAGIQUE 3x3 ---\n");
if (VerifierCarreMagique(carre))
{
printf("Succes : Cette matrice est un CARRE MAGIQUE parfait (somme = 15) !\n");
}
else
{
printf("Echec : Cette matrice n'est pas un carre magique.\n");
}
return 0;
}
Vous maîtrisez désormais le stockage contigu en mémoire. Dans la Partie 4, nous allons aborder le sujet le plus emblématique et redouté du langage C : les pointeurs et l'allocation dynamique de mémoire.
Commentaires