Devoir Surveillé 1er Semestre

Problème 1 : Algorithmique (10 points)

Partie I

Question 1 - Définition du type ENS-GOUV

Pour modéliser cet ensemble, nous définissons une structure de type enregistrement (pour regrouper les propriétés d'un gouvernorat) et un type tableau pour représenter l'ensemble de ces gouvernorats. Le nom demandé est ENS-GOUV (nous utiliserons le tiret de soulignement _ dans le pseudo-code pour respecter les normes de nommage usuelles).

Constante
    MAX = 24  // Nombre maximum de gouvernorats

Type
    Gouvernorat = Enregistrement
        Nom : Chaîne de caractères
        Habitants : Entier
        Superficie : Réel
    Fin Enregistrement

    ENS_GOUV = Tableau [1..MAX] de Gouvernorat

Question 2 - Procédure de Lecture

Cette procédure parcourt le tableau pour instancier les données. On ajoute un paramètre N représentant le nombre effectif de gouvernorats à lire.

Procédure Lecture (Var T : ENS_GOUV, N : Entier)
Variables
    i : Entier
Début
    Pour i de 1 à N faire
        Ecrire("Gouvernorat N°", i)
        Ecrire("Nom : ")
        Lire(T[i].Nom)
        Ecrire("Nombre d'habitants : ")
        Lire(T[i].Habitants)
        Ecrire("Superficie (en km2) : ")
        Lire(T[i].Superficie)
    Fin Pour
Fin

Question 3 - Fonction Recherche

La recherche s'effectue séquentiellement. Dès que l'on trouve le nom, on retourne l'indice (le rang). Si la boucle se termine sans succès, on retourne 0.

Fonction Recherche (T : ENS_GOUV, N : Entier, NomRecherche : Chaîne de caractères) : Entier
Variables
    i : Entier
    Trouve : Booléen
Début
    i <-- 1
    Trouve <-- Faux

    Tant que (i <= N) et (Trouve = Faux) faire
        Si (T[i].Nom = NomRecherche) alors
            Trouve <-- Vrai
        Sinon
            i <-- i + 1
        Fin Si
    Fin Tant que

    Si Trouve = Vrai alors
        Retourner i
    Sinon
        Retourner 0
    Fin Si
Fin

Question 4 - Module Densité

Ce module calcule la densité. On s'assure d'éviter une division par zéro si jamais la superficie saisie est nulle.

Fonction Densite (Habitants : Entier, Superficie : Réel) : Réel
Début
    Si Superficie > 0 alors
        Retourner Habitants / Superficie
    Sinon
        Retourner 0
    Fin Si
Fin

Question 5 - Module Densité-Min-Max

On utilise la fonction Densite pour chaque gouvernorat et on mémorise les indices des gouvernorats correspondant au minimum et au maximum.

Procédure Densite_Min_Max (T : ENS_GOUV, N : Entier)
Variables
    i, IndMin, IndMax : Entier
    D, MinD, MaxD : Réel
Début
    Si N > 0 alors
        IndMin <-- 1
        IndMax <-- 1
        MinD <-- Densite(T[1].Habitants, T[1].Superficie)
        MaxD <-- MinD

        Pour i de 2 à N faire
            D <-- Densite(T[i].Habitants, T[i].Superficie)
            Si D < MinD alors
                MinD <-- D
                IndMin <-- i
            Fin Si
            Si D > MaxD alors
                MaxD <-- D
                IndMax <-- i
            Fin Si
        Fin Pour

        Ecrire("Gouvernorat ayant la densité minimale : ", T[IndMin].Nom)
        Ecrire("Gouvernorat ayant la densité maximale : ", T[IndMax].Nom)
    Fin Si
Fin

Partie II

Question 6 - Définition du type ENS-GOUV-ETENDU

Nous enrichissons la structure précédente avec l'adresse (elle-même une structure) et le nombre de délégations.

Type
    Adresse = Enregistrement
        Rue : Chaîne de caractères
        Numero : Entier
        CodePostal : Entier
    Fin Enregistrement

    GouvEtendu = Enregistrement
        Nom : Chaîne de caractères
        Habitants : Entier
        Superficie : Réel
        NbDelegations : Entier
        AdrSiege : Adresse
    Fin Enregistrement

    ENS_GOUV_ETENDU = Tableau [1..MAX] de GouvEtendu

Question 7 - Fonction NbreDelegations

Cette fonction réalise une somme itérative classique des délégations.

Fonction NbreDelegations (T : ENS_GOUV_ETENDU, N : Entier) : Entier
Variables
    i, Somme : Entier
Début
    Somme <-- 0
    Pour i de 1 à N faire
        Somme <-- Somme + T[i].NbDelegations
    Fin Pour
    Retourner Somme
Fin

Question 8 - Module ChangeAdr

On adapte la logique de la question 3 pour rechercher le gouvernorat. Une fois son rang identifié, on procède à la modification.

Procédure ChangeAdr (Var T : ENS_GOUV_ETENDU, N : Entier, NomGouv : Chaîne de caractères, NouvAdr : Adresse)
Variables
    i : Entier
    Trouve : Booléen
Début
    // Recherche de l'indice
    i <-- 1
    Trouve <-- Faux
    Tant que (i <= N) et (Trouve = Faux) faire
        Si (T[i].Nom = NomGouv) alors
            Trouve <-- Vrai
        Sinon
            i <-- i + 1
        Fin Si
    Fin Tant que

    // Mise à jour si trouvé
    Si Trouve = Vrai alors
        T[i].AdrSiege <-- NouvAdr
        Ecrire("Mise à jour effectuée avec succès.")
    Sinon
        Ecrire("Erreur : Gouvernorat non trouvé.")
    Fin Si
Fin

Question 9 - Ré-organisation et suppression

Il faut calculer le nombre total de délégations, définir le seuil de 5% (0.05 × total), puis parcourir le tableau. À chaque élément sous le seuil, on décale les éléments suivants vers la gauche pour le supprimer. Attention : quand on supprime un élément à l'indice i, il ne faut pas incrémenter i à l'itération suivante pour ne pas sauter l'élément qui vient d'être décalé à cette position.

Procédure Reorganisation (Var T : ENS_GOUV_ETENDU, Var N : Entier)
Variables
    TotalDeleg : Entier
    Seuil : Réel
    i, j : Entier
Début
    TotalDeleg <-- NbreDelegations(T, N)
    Seuil <-- TotalDeleg * 0.05

    i <-- 1
    Tant que (i <= N) faire
        Si (T[i].NbDelegations < Seuil) alors
            // Décalage pour suppression
            Pour j de i à N - 1 faire
                T[j] <-- T[j + 1]
            Fin Pour
            N <-- N - 1  // La taille du tableau diminue
        Sinon
            i <-- i + 1
        Fin Si
    Fin Tant que
Fin

Problème 2 : Programmation C (10 points)

Partie I

Question 1 - Fonction SupprimeEspace

L'objectif est d'ignorer les espaces du début, de compacter les espaces multiples au milieu, et de retirer l'espace final s'il y en a un.

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

void SupprimeEspace(char *NP) {
    int i = 0, j = 0;
    int espaceTrouve = 0;
    char temp[200]; // Chaîne temporaire pour manipuler en sécurité

    // Ignorer les espaces initiaux
    while (NP[i] == ' ') {
        i++;
    }

    // Parcourir et formater
    while (NP[i] != '\0') {
        if (NP[i] != ' ') {
            temp[j++] = NP[i++];
            espaceTrouve = 0;
        } else {
            // Ajouter un seul espace
            if (espaceTrouve == 0) {
                temp[j++] = ' ';
                espaceTrouve = 1;
            }
            i++;
        }
    }

    // Supprimer un éventuel espace à la fin
    if (j > 0 && temp[j - 1] == ' ') {
        j--;
    }
    temp[j] = '\0'; // Fin de chaîne

    strcpy(NP, temp);
}

Question 2 - Fonction PrenomNom

Ici, on présume que la chaîne ne contient plus d'espaces excédentaires. On identifie la position de l'unique espace pour scinder la chaîne et la recomposer.

void PrenomNom(char *NP) {
    char nom[100], prenom[100];
    char *espace = strchr(NP, ' '); // Trouve le pointeur du premier espace
    
    if (espace != NULL) {
        int longueurNom = espace - NP;
        
        // Isoler le nom
        strncpy(nom, NP, longueurNom);
        nom[longueurNom] = '\0'; // strncpy ne met pas de \0 si longueur maximale atteinte
        
        // Isoler le prénom (tout ce qui suit l'espace)
        strcpy(prenom, espace + 1);
        
        // Recomposer: prenom + espace + nom
        strcpy(NP, prenom);
        strcat(NP, " ");
        strcat(NP, nom);
    }
}

Question 3 - Fonction FormaterNP

La fonction crée et retourne une nouvelle chaîne allouée dynamiquement. Format attendu : "nom première_lettre_prenom".

#include <stdlib.h>

char* FormaterNP(char *NP) {
    char *resultat = (char*)malloc(strlen(NP) + 1);
    char nom[100];
    char *espace = strchr(NP, ' ');
    
    if (espace != NULL && resultat != NULL) {
        int longueurNom = espace - NP;
        strncpy(nom, NP, longueurNom);
        nom[longueurNom] = '\0';
        
        // Le prénom débute à espace + 1. Son premier caractère est (espace + 1)[0]
        char premiereLettre = *(espace + 1);
        
        // Ecriture formatée
        sprintf(resultat, "%s %c", nom, premiereLettre);
    } else {
        strcpy(resultat, NP); // Sécurité si espace non trouvé
    }
    
    return resultat;
}

Question 4 - Fonction Test

Pour comparer correctement deux chaînes sans se soucier des espaces superflus, il est nécessaire de nettoyer des copies des paramètres avec SupprimeEspace puis d'appliquer la fonction strcmp.

int Test(char *NP1, char *NP2) {
    char copie1[200];
    char copie2[200];
    
    strcpy(copie1, NP1);
    strcpy(copie2, NP2);
    
    SupprimeEspace(copie1);
    SupprimeEspace(copie2);
    
    if (strcmp(copie1, copie2) == 0) {
        return 1;
    }
    return 0;
}

Partie II

Question 5 - Structure adéquate

Puisqu'il faut allouer dynamiquement l'espace pour chaque chaîne, et qu'il y a au maximum 50 employés, un tableau de pointeurs sur des caractères est la structure idéale en C.

typedef struct {
    char *tab[50];
    int n; // Nombre d'employés effectif
} EnsembleEmployes;

Question 6 - Programme principal

L'énoncé demande de créer un programme principal qui utilise les concepts demandés. Ce programme complet inclut les étapes a. jusqu'à f.

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

// On suppose que les fonctions SupprimeEspace, FormaterNP et Test
// sont déclarées au-dessus du main.

int main() {
    EnsembleEmployes employes;
    char buffer[100];
    int i, j, k;

    // a. Lire le nombre N des employés
    do {
        printf("Saisissez le nombre d'employés (1-50) : ");
        scanf("%d", &employes.n);
        getchar(); // Nettoie le caractère de retour à la ligne (\n) laissé par scanf
    } while (employes.n < 1 || employes.n > 50);

    // b. Lecture et allocation dynamique
    for (i = 0; i < employes.n; i++) {
        printf("Employé %d (Nom Prénom) : ", i + 1);
        fgets(buffer, sizeof(buffer), stdin);
        
        // Remplacement du retour chariot \n par une fin de chaîne \0
        buffer[strcspn(buffer, "\n")] = '\0';
        
        employes.tab[i] = (char*)malloc((strlen(buffer) + 1) * sizeof(char));
        strcpy(employes.tab[i], buffer);
    }

    // c. Enlever les duplications (en ignorant les espaces en trop) et nettoyer
    i = 0;
    while (i < employes.n) {
        j = i + 1;
        while (j < employes.n) {
            if (Test(employes.tab[i], employes.tab[j])) {
                // S'ils sont identiques, on supprime le j-ème
                free(employes.tab[j]);
                // Décalage
                for (k = j; k < employes.n - 1; k++) {
                    employes.tab[k] = employes.tab[k + 1];
                }
                employes.n--;
            } else {
                j++; // Avance seulement si aucune suppression
            }
        }
        // Nettoyage définitif des espaces sur l'élément restant unique
        SupprimeEspace(employes.tab[i]);
        i++;
    }

    // d. Transformer sous la forme: <nom> <première lettre du prénom>
    for (i = 0; i < employes.n; i++) {
        char *chaineFormatee = FormaterNP(employes.tab[i]);
        free(employes.tab[i]); // Libérer l'ancienne chaîne mémoire
        employes.tab[i] = chaineFormatee; // Assigner la nouvelle
    }

    // e. Trier l'ensemble par ordre alphabétique (Tri à bulles simple)
    for (i = 0; i < employes.n - 1; i++) {
        for (j = i + 1; j < employes.n; j++) {
            if (strcmp(employes.tab[i], employes.tab[j]) > 0) {
                // Echange des pointeurs
                char *temp = employes.tab[i];
                employes.tab[i] = employes.tab[j];
                employes.tab[j] = temp;
            }
        }
    }

    // f. Afficher la liste triée
    printf("\nListe finale triée :\n");
    for (i = 0; i < employes.n; i++) {
        printf("%s\n", employes.tab[i]);
    }

    // Nettoyage final de la mémoire
    for (i = 0; i < employes.n; i++) {
        free(employes.tab[i]);
    }

    return 0;
}

Méthode

Face à ce type de sujet, la clé est la modularité et la gestion scrupuleuse des indices de tableaux.

1. L'algorithmique des tableaux avec suppressions (Problème 1 et 2) : Le piège classique lors de la suppression d'un élément d'un tableau ou d'une liste est l'incrémentation inconditionnelle du compteur de boucle. Si vous décalez les éléments i+1, i+2 vers la gauche, le nouvel élément se retrouve à l'indice i. Il faut donc évaluer à nouveau cet indice i et ne l'incrémenter que lorsqu'aucune suppression n'a eu lieu. C'est pourquoi une boucle Tant Que (ou while) est préférable à une boucle Pour (ou for) dans ce scénario.
2. Gestion de la mémoire en C : Quand le sujet parle d'allocation dynamique avec des chaînes (char*), souvenez-vous toujours du + 1 pour inclure le caractère nul de fin de chaîne (\0). Le réflexe doit être : malloc(strlen(chaine) + 1). Enfin, chaque malloc doit aboutir à un moment donné à un free, notamment lorsqu'on retire un doublon du système.
3. Encapsulation : Le sujet permet de réutiliser les modules. N'hésitez pas à les appeler (comme Test ou SupprimeEspace dans la boucle principale du programme). Cela simplifie radicalement l'écriture de votre fonction finale et démontre au correcteur que vous avez l'esprit structuré.