CNC Info 2011
CNC Info 2011
CNC Info 2011
MATHEMATIQUES
Préambule
Un ensemble mathématique est un groupement d’objets distincts, appelés éléments de cet ensemble.
La théorie des ensembles est l’étude des propriétés et des opérations sur des ensembles
(appartenance, inclusion, réunion,…) elle représente une branche essentielle des mathématiques.
Ce problème d’intéresse aux algorithmes réalisant quelques traitements sur des ensembles
mathématiques finis de nombres entiers
Si E est un ensemble fini de N éléments (0<N),e0, e1,….,ei, ei+1, .. ,eN-1, alors E sera noté ainsi E={ e0,
e1,….,ei, ei+1, .. ,eN-1}.
Dans cette partie, il s’agit de représenter par des tableaux, des ensembles finis dont les éléments sont
des nombres entiers strictement positifs.
Appellations
On appellera "Ensemble Tableau de taille N", tout tableau de N, (0<N) entiers strictement positifs et
tous différents. Ce tableau sera noté T={T[0],T[1],…,T[N-1]}
On appellera "Ensemble Tableau de taille N trié", tout "Ensemble Tableau de taille N", T, dont les
éléments sont triés par ordre croissant : (Pour tout i tel que 0<=i<N-1, on a T[i]<T[i+1])
Remarque
Dans toutes les questions de la partie A, on suppose que N, N1, N2 sont des constantes entières
strictement positives déjà définies.
Notation :
Ecrire les instructions qui vérifient si T est un "Ensemble Tableau de taille N".
Pour ce faire :
Soit T un "Ensemble Tableau de taille N" déclaré et initialisé et soit x une variable entière déclarée et
initialisée avec un entier quelconque.
Ecrire les instructions qui affichent sur l’écran l’une des deux affirmations suivantes (a) ou
(b) (dans les 2 cas, la variable x sera remplacée par sa valeur à l’affichage)
(a) " x appartient à T" si x est un élément du tableau T.
(b) " x n’appartient pas à T" si x n’est pas un élément du tableau T.
Exemples :
- Si N=4, T={3,5,2 9} et x=2 alors on affichera : "2 appartient à T"
- Si N=3, T={12,6,9} et x=3 alors on affichera : "3 n’appartient pas à T".
Exemple :
- si N=4, T={3,1,12,8} après les instructions de tri, on aura T={1,3,8,12}
remarque concernant les questions suivantes de la partie A(question4 et question5)
On suppose avoir déjà déclaré et initialisé 2 variables globales T1 et T2 avec T1 est un "Ensemble
Tableau de taille N1 trié" et T2 un "Ensemble Tableau de taille N2 trié "
Exemple :
Soit T un tableau de taille N déjà déclaré (N est la taille du tableau union de T1 et T2).
Exemple :
Dans cette partie, on se propose de représenter des ensembles finis d’entiers strictement positifs triés
par ordre croissant par des listes chainées définies en langage C comme suit
} ensembleListe ;
Appellation
On appellera "Ensemble Liste d’adresse p" une liste chainée d’éléments de type ensembleListe
(définie plus haut) et possédant les propriétés suivantes :
Exemple
L’ensemble {3,7,10,36} sera représenté par l’Ensemble Liste d’adresse p comme suit :
On suppose avoir définie et inséré des éléments dans l’ "Ensemble Liste d’adresse p"(p est déclaré
plus haut).
Ecrire une fonction d’entête : void inserer(int val) qui permet d’insérer à sa place l’élément
de type ensebmleListe dans l’ "Ensemble Liste d’adresse p" pour que la liste reste toujours
triée par ordre croissant. Cet élément a dans son champ nombre la valeur val (paramètre de la
fonction), en plus, on suppose que (val>p->nombre) (voir rappel, remarque et exemple)
p 2 3 5 7 9 12 98
p 2 3 5 7 8 9 12 98
La distance de Hamming définie par Richard Hamming permet de quantifier la différence entre
deux séquences de symboles. Elle est utilisée en informatique et en télécommunications pour
compter le nombre de bits altérés dans la transmission d’un message d’une longueur donnée.
La distance de Hamming entre deux chaines de caractères de mêmes longueurs est égale au
nombre de caractères, à la même position, qui sont différents.
Exemples :
- La distance de Hamming entre « sure » et « cure » est 1.
- La distance de Hamming entre « aabbcc » et « xaybzc » est 3.
- Ecrire une fonction d’entête : int distanceH(char S1[],char S2[],int M) qui calcule et retourne la
distance de Hamming entre S1 et S2 (les paramètres S1 et S2 sont deux chaines de caractères de
même longueur M et on suppose que le paramètre M est strictement positif).
La distance de Hamming entre deux nombres entiers positifs est le nombre de bits distincts dans
leurs représentations binaires (voir exemple)
Exemple : la distance de Hamming entre 7 et 4 est 2( 7 est représenté en binaire sur un octet (8
bits) par 00000111 et 4 est représenté en binaire par 00000100)
Question 3-a :
Ecrire une fonction d’entête : void binaire(char * bin, int N) qui met dans la chaîne d’adresse
bin, la représentation binaire de N ( on suppose que 0<=N<256)
Question 3-b :
Ecrire une fonction d’entête : int distanceNombre(int A, int B) qui calcule et retourne la
distance de Hamming entre les deux nombres A et B (on suppose que 0<=A<256 et
0<=B<256).