Cours de programmation séquentielle

Énoncé

Une façon de déclarer un tableau d’entiers tab dont la taille n’est connue qu’à l’exécution (tableau de taille variable, ou VLA) est la suivante :

#include <stdint.h>

int32_t size = 10;
int32_t tab[size];

Un tel tableau ne peut pas être initialisé lors de sa déclaration (= {0} est interdit) et il est alloué sur la pile : size doit donc être strictement positif et rester raisonnable (quelques milliers d’éléments au plus). Pour le passer à une fonction, on passe sa taille en premier argument :

void ma_fonction(int32_t size, int32_t tab[size]);

Écrire un programme qui réalise les tâches suivantes. Chaque tâche doit être réalisée par (au moins) une fonction, appelée depuis le main() qui affiche les résultats.

Demander à l’utilisateur d’entrer la valeur de size pour la création du tableau. Vérifier que la saisie est valide (scanf() a bien lu un entier et size > 0).

Remplir le tableau tab de valeurs aléatoires entières dans l’intervalle $[0, \mathrm{val\_max}[$ , où l’entier val_max (une constante de votre programme ou une valeur saisie par l’utilisateur) est beaucoup plus petit que size (disons 10 à 100 fois plus petit), afin que le tableau contienne de nombreux doublons. Par exemple, remplir tab de taille 100 avec des valeurs de 0 à 9 (val_max = 10). Ne pas oublier d’initialiser le générateur aléatoire une seule fois au début du programme, avec srand(time(NULL)).

Trouver le plus petit et le plus grand élément de tab.

Placer le plus grand élément de tab en fin de tableau en l’échangeant avec le dernier élément. Si le maximum apparaît plusieurs fois, on déplace sa première occurrence.

Rechercher dans tab un élément entré au clavier par l’utilisateur et retourner l’indice de sa première occurrence, ou -1 si l’élément n’est pas présent dans le tableau.

Calculer la moyenne des éléments de tab (attention à la division entière).

Calculer la variance des éléments de tab. La variance var des éléments de tab est définie par la formule : $\mathrm{var}=\frac{1}{\mathrm{size}}\sum_{i=0}^{\mathrm{size}-1}(\mathrm{tab}[i]-\mathrm{tab}_m)^2, \qquad{(2.1)}$ où $\mathrm{tab}_m$ désigne la moyenne des éléments de tab et $\mathrm{tab}[i]$ est l’élément d’indice $i$ de tab. En déduire l’écart-type, défini comme $\sigma=\sqrt{\mathrm{var}}$ (fonction sqrt() de math.h, compiler avec l’option -lm).

Trier les éléments de tab par ordre croissant. Le tri doit être écrit à la main (tri par sélection, par insertion, …) : l’utilisation de qsort() n’est pas autorisée.

Trouver l’élément médian du tableau tab. Après avoir trié le tableau tab, l’élément médian est défini comme étant la valeur :

tab[(size-1)/2] si size est impair,
(tab[(size-1)/2] + tab[size/2])/2.0 si size est pair.

Exemple : le tableau

devient, une fois trié,

Sa taille étant paire (10), son élément médian vaut

(tab[4] + tab[5])/2.0 = (3 + 3)/2.0 = 3

Vérifier que le générateur de nombres aléatoires rand() est équitable, c’est-à-dire que toutes les valeurs de $[0, \mathrm{val\_max}[$ sont tirées aussi souvent les unes que les autres. Pour cela, effectuer un grand nombre n de tirages (indépendamment de tab) et utiliser un tableau d’entiers histo de taille val_max, initialisé à zéro, pour comptabiliser le nombre de fois que chaque valeur est tirée. À noter que la valeur tirée correspond à l’indice du tableau et que c’est son contenu qui est incrémenté de 1. Utiliser les fonctions précédentes (minimum/maximum, moyenne, écart-type) sur histo pour dire si le générateur est équitable. Pour un générateur équitable, le rapport écart-type / moyenne doit diminuer lorsque n augmente (il est proportionnel à $1/\sqrt{n}$ ) : vérifier ce comportement pour plusieurs valeurs de n (par exemple $10^3$ , $10^5$ et $10^7$ ).

Visualiser le contenu du tableau histo horizontalement et verticalement dans le terminal, en représentant chaque effectif par une barre de caractères *. Les effectifs étant potentiellement très grands, la longueur des barres doit être mise à l’échelle (la plus grande barre fait par exemple 50 caractères horizontalement). Ainsi, pour val_max = 5 et des effectifs proportionnels à 30, 50, 40, 20 et 45 :

0 | ******************************
1 | **************************************************
2 | ****************************************
3 | ********************
4 | *********************************************

et, avec une hauteur maximale de 5 lignes :

  *
  * *   *
* * *   *
* * * * *
* * * * *
---------
0 1 2 3 4

Compter le nombre de valeurs distinctes qui apparaissent au moins deux fois dans le tableau tab.

Exemple :

Ici, 8 apparaît 4 fois, 3 et 5 apparaissent chacun 2 fois, 1 et 6 n’apparaissent qu’une seule fois. Le résultat est donc 3 (les valeurs 3, 5 et 8 apparaissent au moins deux fois).

Buts

Énoncé