2026_TD3_DEV51_Qualite_Algo/banque.c

/*
 * R5.A.04 - Qualité Algorithmique
 * TD Complexité algorithmique : analyse des transactions d'une banque
 *
 * Le programme génère des transactions pseudo-aléatoires (toujours les
 * mêmes, grâce à une graine fixe), puis calcule plusieurs indicateurs
 * et produit un rapport dans rapport.txt.
 *
 * L'empreinte affichée à la fin doit rester IDENTIQUE après vos
 * optimisations : elle prouve que le résultat n'a pas changé.
 *
 * Interdit : modifier les constantes, la génération des données,
 * le format du rapport, ou écrire les résultats « en dur ».
 *
 * Compilation : gcc -O2 banque.c -o banque
 * Profiling   : gcc -O0 -g -pg banque.c -o banque && ./banque && gprof ./banque gmon.out
 */

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

#define NB_TRANSACTIONS 30000
#define NB_CLIENTS      2000
#define NB_JOURS        1000
#define NB_REQUETES     30000
#define MONTANT_MONNAIE 400
#define GRAINE          20261020UL

typedef struct {
    int id;
    int client;
    int jour;
    long montant;   /* en centimes, négatif pour un débit */
} Transaction;

/* ------------------------------------------------------------------ */
/* Données (ne pas modifier)                                          */
/* ------------------------------------------------------------------ */

static unsigned long etat_alea = GRAINE;

unsigned long alea(void)
{
    etat_alea = etat_alea * 6364136223846793005UL + 1442695040888963407UL;
    return etat_alea >> 33;
}

Transaction *generer_transactions(int n)
{
    Transaction *t = malloc(n * sizeof(Transaction));
    for (int i = 0; i < n; i++) {
        t[i].id = i;
        t[i].client = alea() % NB_CLIENTS;
        t[i].jour = alea() % NB_JOURS;
        if (i > 0 && alea() % 20 == 0)
            t[i].montant = -t[alea() % i].montant;   /* opération inverse */
        else
            t[i].montant = (long)(alea() % 100001) - 50000;
    }
    for (int i = n - 1; i > 0; i--) {                /* mélange des id */
        int j = alea() % (i + 1);
        int tmp = t[i].id;
        t[i].id = t[j].id;
        t[j].id = tmp;
    }
    return t;
}

/* ------------------------------------------------------------------ */
/* Fonctions à analyser et à optimiser                                */
/* ------------------------------------------------------------------ */

/* F1 : trie les transactions par montant croissant, puis par id.
 * Les id sont tous distincts : l'ordre est total, donc qsort (non stable)
 * donne le même résultat que le tri à bulles d'origine. */
int comparer_transactions(const void *pa, const void *pb)
{
    const Transaction *a = pa, *b = pb;
    if (a->montant != b->montant)
        return (a->montant > b->montant) - (a->montant < b->montant);
    return (a->id > b->id) - (a->id < b->id);
}

void trier_par_montant(Transaction *t, int n)
{
    qsort(t, n, sizeof(Transaction), comparer_transactions);
}

/* F2 : nombre de clients ayant au moins une transaction */
int nb_clients_distincts(const Transaction *t, int n)
{
    char vu[NB_CLIENTS] = {0};   /* vu[c] vaut 1 dès qu'une transaction du client c est rencontrée */
    int nb = 0;
    for (int i = 0; i < n; i++) {
        if (!vu[t[i].client]) {
            vu[t[i].client] = 1;
            nb++;
        }
    }
    return nb;
}

/* F3 : solde total de chaque client */
void total_par_client(const Transaction *t, int n, long *totaux)
{
    for (int c = 0; c < NB_CLIENTS; c++)
        totaux[c] = 0;
    for (int i = 0; i < n; i++)          /* un seul parcours : chaque montant va */
        totaux[t[i].client] += t[i].montant;   /* directement au total de son client */
}

/* F4 : solde total de chaque jour */
void total_par_jour(const Transaction *t, int n, long *totaux)
{
    for (int j = 0; j < NB_JOURS; j++)
        totaux[j] = 0;
    for (int i = 0; i < n; i++)          /* un seul parcours, comme pour F3 */
        totaux[t[i].jour] += t[i].montant;
}

/* F5 : période de jours consécutifs dont la somme des soldes est maximale */
/* Avec prefixe(j) = totaux[0] + ... + totaux[j-1], la somme des jours i à j
 * vaut prefixe(j+1) - prefixe(i). Pour chaque fin j, le meilleur début est
 * donc l'indice du plus petit prefixe(i), i <= j. On garde le premier minimum
 * et on ne remplace le meilleur que s'il est strictement dépassé : on obtient
 * la même période que la triple boucle d'origine, même en cas d'égalité. */
long meilleure_periode(const long *totaux, int nb_jours, int *debut, int *fin)
{
    long meilleur = totaux[0];
    long prefixe = 0, prefixe_min = 0;
    int debut_min = 0;
    *debut = 0;
    *fin = 0;
    for (int j = 0; j < nb_jours; j++) {
        if (prefixe < prefixe_min) {   /* prefixe vaut ici prefixe(j) */
            prefixe_min = prefixe;
            debut_min = j;
        }
        prefixe += totaux[j];          /* prefixe vaut maintenant prefixe(j+1) */
        if (prefixe - prefixe_min > meilleur) {
            meilleur = prefixe - prefixe_min;
            *debut = debut_min;
            *fin = j;
        }
    }
    return meilleur;
}

/* F6 : position[id] = indice de la transaction id dans t. Les id forment une
 * permutation de 0 .. n-1 (voir generer_transactions) : chaque id a sa case. */
int *indexer_par_id(const Transaction *t, int n)
{
    int *position = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        position[t[i].id] = i;
    return position;
}

/* F6 : retrouve une transaction à partir de son id, en O(1) grâce à l'index */
const Transaction *rechercher_par_id(const Transaction *t, const int *position, int id)
{
    return &t[position[id]];
}

/* Premier indice i tel que t[i].montant >= v, dans t trié par montant
 * croissant (recherche dichotomique, O(log n)). */
int premier_indice(const Transaction *t, int n, long v)
{
    int debut = 0, fin = n;
    while (debut < fin) {
        int milieu = (debut + fin) / 2;
        if (t[milieu].montant < v)
            debut = milieu + 1;
        else
            fin = milieu;
    }
    return debut;
}

/* Nombre de transactions de montant v, dans t trié par montant croissant */
int effectif(const Transaction *t, int n, long v)
{
    return premier_indice(t, n, v + 1) - premier_indice(t, n, v);
}

/* F7 : nombre de paires de transactions de montants opposés (a + b = 0).
 * t doit être trié par montant (F1). On compte, pour chaque transaction, les
 * transactions de montant opposé : chaque paire est vue deux fois, et chaque
 * montant nul se compte lui-même une fois en trop. */
long nb_paires_opposees(const Transaction *t, int n)
{
    long nb = 0;
    for (int i = 0; i < n; i++)
        nb += effectif(t, n, -t[i].montant);
    return (nb - effectif(t, n, 0)) / 2;
}

/* F8 : nombre de façons de rendre une somme avec les pièces disponibles */
static const int PIECES[] = {1, 2, 5, 10, 20, 50, 100, 200};
#define NB_PIECES 8

/* Programmation dynamique : après avoir traité les p premières pièces,
 * facons[s] est le nombre de façons de rendre s avec ces pièces. */
long nb_facons_rendre(int somme, int nb_pieces)
{
    long *facons = calloc(somme + 1, sizeof(long));
    facons[0] = 1;
    for (int p = 0; p < nb_pieces; p++)
        for (int s = PIECES[p]; s <= somme; s++)
            facons[s] += facons[s - PIECES[p]];
    long resultat = facons[somme];
    free(facons);
    return resultat;
}

/* F9 : catégorie d'une transaction (pour les statistiques), découpée par
 * sens de l'opération pour que chaque fonction reste simple (M <= 5). */
int est_week_end(int jour)
{
    return jour % 7 >= 5;   /* jours 5 et 6 de la semaine (jour >= 0) */
}

int categorie_debit(const Transaction *t)          /* montant < 0 */
{
    if (t->montant < -20000)
        return est_week_end(t->jour) ? 1 : 2;
    if (t->montant < -5000)
        return 3;
    return t->client % 10 == 0 ? 4 : 5;
}

int categorie_gros_credit(const Transaction *t)    /* montant > 30000 */
{
    return t->client % 10 == 0 && !est_week_end(t->jour) ? 6 : 7;
}

int categorie_credit(const Transaction *t)         /* montant > 0 */
{
    if (t->montant > 30000)
        return categorie_gros_credit(t);
    if (t->montant > 10000)
        return 8;
    if (t->montant > 1000)
        return t->jour % 30 == 0 ? 9 : 10;
    return 11;
}

int categorie(const Transaction *t)
{
    if (t->montant < 0)
        return categorie_debit(t);
    if (t->montant == 0)
        return 0;
    return categorie_credit(t);
}

/* F10 : ajoute une ligne à la fin du rapport. On passe la position du '\0'
 * final et on renvoie la nouvelle : plus besoin de recalculer la longueur. */
char *ajouter_ligne(char *fin, const char *ligne)
{
    while (*ligne != '\0')
        *fin++ = *ligne++;
    *fin = '\0';
    return fin;
}

/* ------------------------------------------------------------------ */
/* Programme principal (à adapter si vous changez les signatures)     */
/* ------------------------------------------------------------------ */

unsigned long empreinte(const char *s)
{
    unsigned long h = 1469598103934665603UL;
    for (int i = 0; s[i] != '\0'; i++) {
        h ^= (unsigned char)s[i];
        h *= 1099511628211UL;
    }
    return h;
}

/* Tous les indicateurs calculés, pour le rapport et l'affichage */
typedef struct {
    long somme_requetes;
    int nb_clients;
    long totaux_clients[NB_CLIENTS];
    long totaux_jours[NB_JOURS];
    int debut, fin;
    long meilleure;
    int categories[12];
    long nb_paires;
    long nb_facons;
} Resultats;

/* Recherches par id, dans l'ordre d'origine des transactions (F6) */
long sommer_requetes(const Transaction *t, int n)
{
    int *position = indexer_par_id(t, n);
    long somme = 0;
    unsigned long etat = 12345;
    for (int q = 0; q < NB_REQUETES; q++) {
        etat = etat * 1103515245UL + 12345UL;
        /* tout id de 0 à n-1 existe : le résultat n'est jamais NULL */
        somme += rechercher_par_id(t, position, (int)((etat >> 8) % n))->montant;
    }
    free(position);
    return somme;
}

void compter_categories(const Transaction *t, int n, int *categories)
{
    for (int i = 0; i < n; i++)
        categories[categorie(&t[i])]++;
}

/* Calcule tous les indicateurs. À la fin, t est trié par montant (F1). */
void analyser(Transaction *t, int n, Resultats *r)
{
    r->somme_requetes = sommer_requetes(t, n);      /* avant le tri : ordre d'origine */
    r->nb_clients = nb_clients_distincts(t, n);
    total_par_client(t, n, r->totaux_clients);
    total_par_jour(t, n, r->totaux_jours);
    r->meilleure = meilleure_periode(r->totaux_jours, NB_JOURS, &r->debut, &r->fin);
    compter_categories(t, n, r->categories);
    trier_par_montant(t, n);
    r->nb_paires = nb_paires_opposees(t, n);        /* a besoin du tri */
    r->nb_facons = nb_facons_rendre(MONTANT_MONNAIE, NB_PIECES);
}

/* Formate une ligne comme printf et l'ajoute à la fin du rapport (F10) */
char *ajouter_formatee(char *fin, const char *format, ...)
{
    char ligne[128];
    va_list arguments;
    va_start(arguments, format);
    vsnprintf(ligne, sizeof(ligne), format, arguments);
    va_end(arguments);
    return ajouter_ligne(fin, ligne);
}

char *construire_rapport(const Resultats *r, const Transaction *t)
{
    char *rapport = malloc(1 << 20);
    char *fin = rapport;   /* position du '\0' final du rapport */
    *fin = '\0';
    fin = ajouter_formatee(fin, "clients distincts;%d\n", r->nb_clients);
    fin = ajouter_formatee(fin, "somme des requetes;%ld\n", r->somme_requetes);
    fin = ajouter_formatee(fin, "meilleure periode;%d;%d;%ld\n", r->debut, r->fin, r->meilleure);
    fin = ajouter_formatee(fin, "paires opposees;%ld\n", r->nb_paires);
    fin = ajouter_formatee(fin, "facons de rendre %d;%ld\n", MONTANT_MONNAIE, r->nb_facons);
    for (int c = 0; c < 12; c++)
        fin = ajouter_formatee(fin, "categorie;%d;%d\n", c, r->categories[c]);
    for (int c = 0; c < NB_CLIENTS; c++)
        fin = ajouter_formatee(fin, "client;%d;%ld\n", c, r->totaux_clients[c]);
    for (int j = 0; j < NB_JOURS; j++)
        fin = ajouter_formatee(fin, "jour;%d;%ld\n", j, r->totaux_jours[j]);
    for (int i = 0; i < NB_TRANSACTIONS; i += 10)
        fin = ajouter_formatee(fin, "rang;%d;%d;%ld\n", i, t[i].id, t[i].montant);
    return rapport;
}

void ecrire_fichier(const char *nom, const char *texte)
{
    FILE *f = fopen(nom, "w");
    if (f != NULL) {
        fputs(texte, f);
        fclose(f);
    }
}

void afficher(const Resultats *r, const char *rapport)
{
    printf("Clients distincts   : %d\n", r->nb_clients);
    printf("Somme des requêtes  : %ld\n", r->somme_requetes);
    printf("Meilleure période   : jours %d à %d (%ld)\n", r->debut, r->fin, r->meilleure);
    printf("Paires opposées     : %ld\n", r->nb_paires);
    printf("Façons de rendre %d : %ld\n", MONTANT_MONNAIE, r->nb_facons);
    printf("Empreinte           : %016lx\n", empreinte(rapport));
}

int main(void)
{
    Transaction *t = generer_transactions(NB_TRANSACTIONS);
    Resultats r = {0};
    analyser(t, NB_TRANSACTIONS, &r);
    char *rapport = construire_rapport(&r, t);
    ecrire_fichier("rapport.txt", rapport);
    afficher(&r, rapport);
    free(rapport);
    free(t);
    return 0;
}