Cet article présente plusieurs implémentations courantes d'algorithmes et de structures de données en langage C, souvent rencontrées dans des examens de programmation.

Addition de grands entiers

#include <stdio.h>
#include <string.h>

#define MAX_TAILLE 20

void inverser_chaine(char *chaine) {
    int debut = 0, fin = strlen(chaine) - 1;
    while (debut < fin) {
        char temp = chaine[debut];
        chaine[debut++] = chaine[fin];
        chaine[fin--] = temp;
    }
}

void addition_grands_entiers(const char *premier, const char *second, char *resultat) {
    char operande1[MAX_TAILLE] = "", operande2[MAX_TAILLE] = "";
    strcpy(operande1, premier);
    strcpy(operande2, second);
    inverser_chaine(operande1);
    inverser_chaine(operande2);

    int index = 0, retenue[MAX_TAILLE + 1] = {0};
    int longueur_max = strlen(premier) > strlen(second) ? strlen(premier) : strlen(second);

    for (index = 0; index < longueur_max || retenue[index] != 0; index++) {
        int chiffre_a = operande1[index] >= '0' && operande1[index] <= '9' ? operande1[index] - '0' : 0;
        int chiffre_b = operande2[index] >= '0' && operande2[index] <= '9' ? operande2[index] - '0' : 0;
        int somme = chiffre_a + chiffre_b + retenue[index];

        if (somme > 9) {
            somme = somme % 10;
            retenue[index + 1] = 1;
        }
        resultat[index] = somme + '0';
    }
    inverser_chaine(resultat);
}

Résolution d'équation quadratique

#include <stdio.h>
#include <math.h>

int main() {
    double coeff_a, coeff_b, coeff_c;
    scanf("%lf %lf %lf", &coeff_a, &coeff_b, &coeff_c);

    double discriminant = coeff_b * coeff_b - 4 * coeff_a * coeff_c;

    if (discriminant > 0) {
        double racine1 = (-coeff_b - sqrt(discriminant)) / (2 * coeff_a);
        double racine2 = (-coeff_b + sqrt(discriminant)) / (2 * coeff_a);
        printf("x1=%.2lf, x2=%.2lf\n", racine1, racine2);
    } else if (discriminant == 0) {
        double racine_unique = -coeff_b / (2 * coeff_a);
        printf("x1 = x2 = %.2lf\n", racine_unique);
    } else {
        printf("Pas de racines réelles\n");
    }
    return 0;
}

Factorielle par récursivité

#include <stdio.h>

long long calcul_factorielle_rec(int n) {
    if (n <= 1) {
        return 1LL;
    }
    return (long long)n * calcul_factorielle_rec(n - 1);
}

int main() {
    int valeur = 10;
    printf("La factorielle de %d est %lld\n", valeur, calcul_factorielle_rec(valeur));
    return 0;
}

Fusion d'ensembles (listes chaînées)

#include <stdio.h>
#include <stdlib.h>

typedef int ElementListe;

struct NoeudChainee {
    ElementListe donnee;
    struct NoeudChainee *suivant;
};

struct ListeChainee {
    struct NoeudChainee *tete;
    struct NoeudChainee *queue;
};

struct ListeChainee* initier_liste() {
    struct ListeChainee *liste = (struct ListeChainee*)malloc(sizeof(struct ListeChainee));
    liste->tete = NULL;
    liste->queue = NULL;
    return liste;
}

void ajouter_en_queue(struct ListeChainee *liste, ElementListe val) {
    struct NoeudChainee *nouveau = (struct NoeudChainee*)malloc(sizeof(struct NoeudChainee));
    nouveau->donnee = val;
    nouveau->suivant = NULL;
    if (liste->queue == NULL) {
        liste->tete = nouveau;
        liste->queue = nouveau;
    } else {
        liste->queue->suivant = nouveau;
        liste->queue = nouveau;
    }
}

int trouver_element(struct ListeChainee *liste, ElementListe val) {
    struct NoeudChainee *courant = liste->tete;
    while (courant != NULL) {
        if (courant->donnee == val) {
            return 1;
        }
        courant = courant->suivant;
    }
    return 0;
}

struct ListeChainee* fusionner_ensembles(struct ListeChainee *ensemble1, struct ListeChainee *ensemble2) {
    struct ListeChainee *resultat = initier_liste();
    struct NoeudChainee *courant;

    courant = ensemble1->tete;
    while (courant != NULL) {
        ajouter_en_queue(resultat, courant->donnee);
        courant = courant->suivant;
    }

    courant = ensemble2->tete;
    while (courant != NULL) {
        if (!trouver_element(ensemble1, courant->donnee)) {
            ajouter_en_queue(resultat, courant->donnee);
        }
        courant = courant->suivant;
    }
    return resultat;
}

Tri à bulles

#include <stdio.h>

void tri_a_bulles(int tableau[], int taille) {
    for (int i = 0; i < taille - 1; i++) {
        for (int j = 0; j < taille - 1 - i; j++) {
            if (tableau[j] > tableau[j + 1]) {
                int temp = tableau[j];
                tableau[j] = tableau[j + 1];
                tableau[j + 1] = temp;
            }
        }
    }
}

Plus Grand Commun Diviseur (PGCD)

#include <stdio.h>

int pgcd_euclide(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int nombre1 = 48, nombre2 = 18;
    printf("Le PGCD de %d et %d est %d\n", nombre1, nombre2, pgcd_euclide(nombre1, nombre2));
    return 0;
}

Gestion d'informations étudiantes (tri)

#include <stdio.h>
#include <string.h>

#define TAILLE_CHAINE 100
#define NOMBRE_ETUDIANTS 2

typedef struct {
    char matricule[TAILLE_CHAINE];
    char nom[TAILLE_CHAINE];
} FicheEtudiant;

int main() {
    FicheEtudiant promotion[NOMBRE_ETUDIANTS];
    // Supposons que les données sont déjà remplies
    for (int i = 0; i < NOMBRE_ETUDIANTS; i++) {
        for (int j = i + 1; j < NOMBRE_ETUDIANTS; j++) {
            if (strcmp(promotion[i].matricule, promotion[j].matricule) > 0) {
                FicheEtudiant temp = promotion[i];
                promotion[i] = promotion[j];
                promotion[j] = temp;
            }
        }
    }
    return 0;
}

Rotation d'une matrice carrée de 90°

#include <stdio.h>

#define DIMENSION 3

void pivoter_matrice(int matrice[DIMENSION][DIMENSION]) {
    // Étape 1: Transposition
    for (int i = 0; i < DIMENSION; i++) {
        for (int j = i + 1; j < DIMENSION; j++) {
            int temp = matrice[i][j];
            matrice[i][j] = matrice[j][i];
            matrice[j][i] = temp;
        }
    }
    // Étape 2: Inversion des colonnes
    for (int i = 0; i < DIMENSION; i++) {
        for (int j = 0; j < DIMENSION / 2; j++) {
            int temp = matrice[i][j];
            matrice[i][j] = matrice[i][DIMENSION - 1 - j];
            matrice[i][DIMENSION - 1 - j] = temp;
        }
    }
}

Plus Petit Commun Multiple (PPCM) par récursivité

#include <stdio.h>

int ppcm_recursif(int a, int b, int multiple) {
    if (multiple % a == 0 && multiple % b == 0) {
        return multiple;
    }
    return ppcm_recursif(a, b, multiple + 1);
}

int main() {
    int val_a = 12, val_b = 18;
    int ppcm = ppcm_recursif(val_a, val_b, (val_a > val_b) ? val_a : val_b);
    printf("Le PPCM de %d et %d est %d\n", val_a, val_b, ppcm);
    return 0;
}