Royaume du Maroc
Ministère de l ’Education Nationale
de l ’Enseignement Supérieur, de la Formation des Cadres
et de la Recherche Scientifique
CPGE LYCEE OMAR OUJDA
EXAMEN BLANC(2010)
EPREUVE D ’INFORMATIQUE
FILIERE MP/TSI(SPE)
Exercice1 : /5
On se propose d'écrire un programme en langage C qui permet de calculer la somme :
1+ x + x2 + x3+ … + xN. (x réel et N0).
Donnez deux versions de ce programme :
a) Utilisez la fonction pow de la bibliothèque math.h:
Exemple: pow(2,3)=23
b) Utilisez une fonction récursive d’entête puissance(x,n) qui retourne xn .
Exercice 2 : La compression de données: /5
a- Définitions préliminaires
La compression de données est le traitement informatique, en utilisant un algorithme particulier, qui permet
de transformer une suite de bits A en une suite de bits B plus courte. Les suites A et B contiennent les mêmes
informations, mais codées d’une manière différente.
Le codage: d’une information est l’opération informatique qui permet de changer la représentation de
l'information, dans le but de rendre la représentation plus courte que la représentation originale.
La décompression et le décodage: sont les opérations inverses de la compression et du codage.
b- L’algorithme RLE
L’algorithme RLE (Run-Length Encoding), appelé en français le codage par plages, est un algorithme de
compression informatique qui consiste à repérer et à éliminer la redondance des données. Toute suite de bits ou
de caractères identiques est remplacée par un couple (caractère répété suivi de son nombre d’occurrences (son
nombre de répétitions)).
Exemple: CCCCBBBRTTTTCCBBBBB donne: C4B3R1T4C2B5
Dans ce qui suit, on se propose d’étudier l’algorithme RLE pour compresser des chaînes de caractères :
- On appelle chaîne d’origine, toute chaîne de caractères initiale avant sa compression. Exemple la chaîne
ch=DDDERRRTTTTT
- On appelle chaîne compressée de la chaîne d’origine ch, la chaîne de caractères contenant une occurrence
unique (un seul caractère) de toute suite de caractères identiques consécutifs se trouvant dans la chaîne ch .
Exemple :
- Soit la chaîne ch = AAARTTAAVVTTT , sa chaîne compressée S= ARTAVT
- Soient ch une chaîne d’origine et S sa chaîne compressée. On appelle tableau d’occurrences de S dans ch, un
tableau d’entiers contenant le nombre des répétions successives de chaque caractère de S dans la chaîne d’origine
ch.
Exemple
- Si la chaîne d’origine ch = BBBXXXXXXBBBYYYYYB alors sa chaîne compressée S =BXBYB et les éléments du
tableau d’occurrences de S dans ch sont:3, 6, 3, 5,1.
Il s’agit d’écrire des fonctions en langages C permettant de mettre en œuvre l’algorithme de codage RLE.
Rappels :
- Une chaîne de caractères en langage C est un tableau de caractères se terminant par le caractère spécial ‘\0’ (‘\0’
ne fait pas partie de la chaîne de caractères mais indique sa fin)
- Le premier élément d’un tableau en langage C a l’indice 0(zéro).
- La longueur d’une chaîne de caractères est le nombre de caractères contenus dans la chaîne avant le caractère ‘\
0’.
Remarques
- Seule la fonction de la bibliothèque du langage C strlen(chaine) déclarée dans le fichier string.h et qui retourne la
longueur de la chaîne qui est en paramètre peut être appelée et utilisée sans qu’elle soit définie. Toute autre
fonction doit être déclarée et définie avant son appel.
2
- On suppose avoir définit la directive de compilation suivante :#include <string.h>
- On suppose que toutes les chaînes de caractères manipulées dans ce programme , ont des longueurs strictement
inférieurs à 255.
On se propose d’écrire des fonctions en langage C pour construire la chaîne compressée d’une chaîne d’origine
donnée et pour remplir son tableau des occurrences.
- On suppose avoir déclaré comme suit les variables globales suivantes :
char ch [255]; // chaîne d’origine
char ch_compress[255] ; // chaîne compressé de ch
int occur[255] ; // tableau des occurrences de ch_compress
- On suppose que la chaîne de caractères d’origine ch est initialisée à une chaîne quelconque non vide.
Question 1) Ecrire le code d’une fonction en langage C d’entête : void compresser() qui permet de mettre dans la
chaîne ch_compress , la chaîne compressée de ch, ( les 2 chaînes ch et ch_compress sont déjà déclarées).
Exemple :
- Si la chaîne ch = AAAXRRZZZAAAA Après l’appel de la fonction compresser() , ch_compress =AXRZA
Question 2) Ecrire le code d’une fonction en langage C d’entête : void occurrence() qui permet de remplir le
tableau occur ( déjà déclaré), qui est le tableau d’occurrences de ch_compress dans ch
Exemple :
- Si la chaîne d’origine ch = DDDRRRRDTTYYYY, alors ch_compress = DRDTY
- Après l’appel de la fonction occurrence () les éléments du tableau occur sont : occur[0]=3, occur[1]=4,
occur[2]=1, occur[3]=2, occur[4]=4.
Exercice3 : /10
- Lire la totalité de l’exercice avant de commencer la résolution
On se propose d'écrire une application en langage C qui permet de mettre à jour des factures d’un
magasin. Chaque facture est définie selon le type facture suivant
typedef struct
{
unsigned long num ;//numéro de la facture
char nom[15];// nom du client
float prixHT ;//le prix hors taxe à payer en dh
}facture ;
On suppose aussi avoir les déclarations globales suivantes :
#define Taille 100
facture t[Taille]
typedef facture tablo [Taille] ;
Int N // taille de tableau
a) Ecrire une fonction void remplir tableau(tablo t[ ],int N) qui remplit le tableau t, de taille N, avec N factures saisi
par l’utilisateur.
b) Ecrire une fonction void aff_tableau(tablo t[ ],int N) qui affiche le contenu du tableau t .
c) Ecrire une fonction int compter_occ(char x[ ], tablo t[ ],int N) qui renvoie le nombre de factures du client dont
le nom est x dans le tableau t .
d) Ecrire une fonction void meilleure_facture( int tablo t[ ],int N) qui renvoie les informations de la facture ayant
le plus grand montant(prixHT).
e) Ecrire une fonction d ’entête float total_TTC(tablo t[ ],int N)qui retourne la somme des prix totaux TTC(Toute
Taxe Comprise)de toutes les factures implémentées dans le tableau La TVA étant fixée à 20%
f) Ecrire la fonction main qui appelle les fonctions définies ci-dessus pour répondre au problème posé.
