rabot/2026_TD3_DEV51_Qualite_Algo
1
0
Fork 0
forked from menault/2026_TD3_DEV51_Qualite_Algo
Code Pull Requests Activity
Files
main
2026_TD3_DEV51_Qualite_Algo/banque.c
T

411 lines
12 KiB
C
Raw Permalink Blame History

/*
* 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 <stdio.h>
#include <stdlib.h>
#include <string.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 */
static int comparer_transactions(const Transaction *a, const Transaction *b)
{
if (a->montant != b->montant)
return (a->montant > b->montant) - (a->montant < b->montant);
return (a->id > b->id) - (a->id < b->id);
}
static void trier_intervalle(Transaction *t, Transaction *tampon, int debut, int fin)
{
if (fin - debut < 2)
return;
int milieu = debut + (fin - debut) / 2;
trier_intervalle(t, tampon, debut, milieu);
trier_intervalle(t, tampon, milieu, fin);
int gauche = debut;
int droite = milieu;
for (int i = debut; i < fin; i++) {
if (gauche < milieu &&
(droite == fin || comparer_transactions(&t[gauche], &t[droite]) <= 0))
tampon[i] = t[gauche++];
else
tampon[i] = t[droite++];
}
memcpy(t + debut, tampon + debut, (size_t)(fin - debut) * sizeof(*t));
}
void trier_par_montant(Transaction *t, int n)
{
if (n < 2)
return;
Transaction *tampon = malloc((size_t)n * sizeof(*tampon));
if (tampon == NULL) {
perror("Allocation du tampon de tri");
exit(EXIT_FAILURE);
}
trier_intervalle(t, tampon, 0, n);
free(tampon);
}
/* F2 : nombre de clients ayant au moins une transaction */
int nb_clients_distincts(const Transaction *t, int n)
{
unsigned char vus[NB_CLIENTS] = {0};
int nb = 0;
for (int i = 0; i < n; i++) {
if (!vus[t[i].client]) {
vus[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++)
totaux[t[i].client] += t[i].montant;
}
/* 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++)
totaux[t[i].jour] += t[i].montant;
}
/* F5 : période de jours consécutifs dont la somme des soldes est maximale */
/* Précondition : nb_jours > 0. En cas d'égalité, garder le premier intervalle. */
long meilleure_periode(const long *totaux, int nb_jours, int *debut, int *fin)
{
long meilleur = totaux[0];
long somme = totaux[0];
int debut_courant = 0;
*debut = 0;
*fin = 0;
for (int j = 1; j < nb_jours; j++) {
if (somme < 0) {
somme = totaux[j];
debut_courant = j;
} else {
somme += totaux[j];
}
if (somme > meilleur) {
meilleur = somme;
*debut = debut_courant;
*fin = j;
}
}
return meilleur;
}
/* F6 : retrouve une transaction à partir de son id */
/* Les id forment une permutation de 0 à n - 1. Reconstruire après tout tri. */
void indexer_par_id(const Transaction *t, int n, const Transaction **index_ids)
{
for (int i = 0; i < n; i++)
index_ids[t[i].id] = &t[i];
}
const Transaction *rechercher_par_id(const Transaction *const *index_ids, int n, int id)
{
if (id < 0 || id >= n)
return NULL;
return index_ids[id];
}
/* F7 : nombre de paires de transactions de montants opposés (a + b = 0) */
static long compter_paires_triees(const Transaction *t, int n)
{
long nb = 0;
int gauche = 0;
int droite = n - 1;
while (gauche < droite) {
long somme = t[gauche].montant + t[droite].montant;
if (somme < 0) {
gauche++;
} else if (somme > 0) {
droite--;
} else if (t[gauche].montant == 0) {
long taille = droite - gauche + 1;
nb += taille * (taille - 1) / 2;
break;
} else {
long nb_gauche = 1;
long nb_droite = 1;
while (gauche + 1 < droite && t[gauche + 1].montant == t[gauche].montant) {
gauche++;
nb_gauche++;
}
while (droite - 1 > gauche && t[droite - 1].montant == t[droite].montant) {
droite--;
nb_droite++;
}
nb += nb_gauche * nb_droite;
gauche++;
droite--;
}
}
return nb;
}
long nb_paires_opposees(const Transaction *t, int n)
{
if (n < 2)
return 0;
Transaction *copie = malloc((size_t)n * sizeof(*copie));
if (copie == NULL) {
perror("Allocation de la copie des transactions");
exit(EXIT_FAILURE);
}
memcpy(copie, t, (size_t)n * sizeof(*copie));
trier_par_montant(copie, n);
long nb = compter_paires_triees(copie, n);
free(copie);
return nb;
}
/* 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
long nb_facons_rendre(int somme, int nb_pieces)
{
if (somme < 0)
return 0;
long *facons = calloc((size_t)somme + 1, sizeof(*facons));
if (facons == NULL) {
perror("Allocation du tableau de rendu de monnaie");
exit(EXIT_FAILURE);
}
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) */
static int categorie_debit(const Transaction *t)
{
if (t->montant < -20000) {
if (t->jour % 7 >= 5)
return 1;
return 2;
}
if (t->montant < -5000)
return 3;
if (t->client % 10 == 0)
return 4;
return 5;
}
static int categorie_credit(const Transaction *t)
{
if (t->montant > 30000) {
if (t->client % 10 == 0 && t->jour % 7 < 5)
return 6;
return 7;
}
if (t->montant > 10000)
return 8;
if (t->montant > 1000) {
if (t->jour % 30 == 0)
return 9;
return 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 */
/* fin_rapport désigne le '\0' courant ; l'appelant conserve la nouvelle fin. */
char *ajouter_ligne(char *fin_rapport, const char *ligne)
{
while (*ligne != '\0')
*fin_rapport++ = *ligne++;
*fin_rapport = '\0';
return fin_rapport;
}
/* ------------------------------------------------------------------ */
/* 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;
}
int main(void)
{
Transaction *t = generer_transactions(NB_TRANSACTIONS);
char *rapport = malloc(1 << 20);
char ligne[128];
rapport[0] = '\0';
char *fin_rapport = rapport;
/* recherches par id, dans l'ordre d'origine */
static const Transaction *index_ids[NB_TRANSACTIONS];
indexer_par_id(t, NB_TRANSACTIONS, index_ids);
long somme_requetes = 0;
unsigned long etat = 12345;
for (int q = 0; q < NB_REQUETES; q++) {
etat = etat * 1103515245UL + 12345UL;
const Transaction *r = rechercher_par_id(index_ids, NB_TRANSACTIONS, (int)((etat >> 8) % NB_TRANSACTIONS));
if (r != NULL)
somme_requetes += r->montant;
}
int nb_clients = nb_clients_distincts(t, NB_TRANSACTIONS);
static long totaux_clients[NB_CLIENTS];
total_par_client(t, NB_TRANSACTIONS, totaux_clients);
static long totaux_jours[NB_JOURS];
total_par_jour(t, NB_TRANSACTIONS, totaux_jours);
int debut, fin;
long meilleure = meilleure_periode(totaux_jours, NB_JOURS, &debut, &fin);
long nb_paires = nb_paires_opposees(t, NB_TRANSACTIONS);
int categories[12] = {0};
for (int i = 0; i < NB_TRANSACTIONS; i++)
categories[categorie(&t[i])]++;
trier_par_montant(t, NB_TRANSACTIONS);
long nb_facons = nb_facons_rendre(MONTANT_MONNAIE, NB_PIECES);
/* rapport */
snprintf(ligne, sizeof(ligne), "clients distincts;%d\n", nb_clients);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
snprintf(ligne, sizeof(ligne), "somme des requetes;%ld\n", somme_requetes);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
snprintf(ligne, sizeof(ligne), "meilleure periode;%d;%d;%ld\n", debut, fin, meilleure);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
snprintf(ligne, sizeof(ligne), "paires opposees;%ld\n", nb_paires);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
snprintf(ligne, sizeof(ligne), "facons de rendre %d;%ld\n", MONTANT_MONNAIE, nb_facons);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
for (int c = 0; c < 12; c++) {
snprintf(ligne, sizeof(ligne), "categorie;%d;%d\n", c, categories[c]);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
}
for (int c = 0; c < NB_CLIENTS; c++) {
snprintf(ligne, sizeof(ligne), "client;%d;%ld\n", c, totaux_clients[c]);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
}
for (int j = 0; j < NB_JOURS; j++) {
snprintf(ligne, sizeof(ligne), "jour;%d;%ld\n", j, totaux_jours[j]);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
}
for (int i = 0; i < NB_TRANSACTIONS; i += 10) {
snprintf(ligne, sizeof(ligne), "rang;%d;%d;%ld\n", i, t[i].id, t[i].montant);
fin_rapport = ajouter_ligne(fin_rapport, ligne);
}
FILE *f = fopen("rapport.txt", "w");
if (f != NULL) {
fputs(rapport, f);
fclose(f);
}
printf("Clients distincts : %d\n", nb_clients);
printf("Somme des requêtes : %ld\n", somme_requetes);
printf("Meilleure période : jours %d à %d (%ld)\n", debut, fin, meilleure);
printf("Paires opposées : %ld\n", nb_paires);
printf("Façons de rendre %d : %ld\n", MONTANT_MONNAIE, nb_facons);
printf("Empreinte : %016lx\n", empreinte(rapport));
free(rapport);
free(t);
return 0;
}
View Git Blame Copy Permalink