Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

-Devoir libre N° 1 page 1/3- SMI /S4 Module : Structures de données 2014-2015 P

-Devoir libre N° 1 page 1/3- SMI /S4 Module : Structures de données 2014-2015 Prof : S.NOUH Devoir Libre N°1 ( à rendre le 13/03/2015) PROBLÈME I: REPRÉSENTATION DE GRANDS NOMBRES ENTIERS NATURELS Contexte du problème : Pour tout langage de programmation, la représentation des nombres par des types prédéfinis est très limitée (en langage C, une variable entière v de type long int est bornée ainsi : -2147483648<=v<=2147483647). Cependant, plusieurs problèmes (par exemple les systèmes CPS, la cryptographie ou encore les applications de gestion) ont besoin d'utiliser des nombres ayant des valeurs et des précisions qui dépassent largement les limites des types prédéfinis par les langages de programmation. Pour toutes ces applications, les types de base ne conviennent plus et il faudra définir de nouvelles représentations pour ces nombres. Le problème suivant s'inscrit dans ce contexte. Il s'intéresse à la représentation des nombres entiers positifs pouvant avoir des valeurs très grandes non spécifiées par les types standard su langage C. A : Représentation par des chaines de caractères Dans cette partie, on représentera un nombre positif ou nul par une chaine de caractères contenant ses chiffres. Rappels – Une chaine de caractères en langage C est un tableau de caractères se terminant par le caractère spécial '\0'. – La longueur d'une chaine de caractères est le nombre de caractères avant '\0'. Notations – On dira qu'une chaine de caractères S est une ChaineChiffres si sa longueur est strictement positive et tout caractère de S est un caractère chiffre (les caractères chiffres sont '0','1','2','3','4','5','6','7','8,'9'). – Soit N un nombre entier positif ou nul de NC chiffres (NC > 0), la valeur décimale (base 10) de N est: N=CNC-1CNC-2...Ci...C1C0, (C0 chiffre des unités, C1 chiffre des dizaines,...), on dit que N est représenté par une chaineChiffre S, si S contient les chiffres de N comme suit : S= "CNC-1CNC-2...Ci...C1C0" Exemple : Le nombre N=45009876156430987 de 17 chiffres sera représenté par la ChaineChiffres S= "45009876156430987" (S [0]=’4 ’, S[1]= ’5 ’, S[2]= ’0 ’ ,...S[16]= ’7 ’)  Question 1 : Chaine de chiffres Soit S une chaine de caractères quelconque déjà déclarée et initialisée.  Définir une fonction d'entête int ChaineChiffres() qui retourne 1 si S est une ChaineChiffres ou 0 (zéro) sinon. Exemple : – Si S= "78500120360007" alors l'appel à la fonction ChaineChiffres() retourne 1. – Si S= "856942a1478" alors l'appel de la fonction ChaineChiffres() retourne 0.  Question 2 : Zéros non significatifs On suppose que S est une ChaineChiffres déjà déclarée et définie.  Ecrire une fonction d'entête void supprimer_zeros() qui supprime les zéros à gauche de la chaine S (les zéros non significatifs dans un nombre) Exemple : Si S= "0009760004300", après l'appel de supprimer_zeros( ), S= "9760004300". -Devoir libre N° 1 page 2/3-  Question 3 : Somme de deux chaines de chiffres. Il s'agit de faire la somme de deux nombres entiers positifs représentés par leurs ChaineChiffres. Pour ce faire:  Écrire une fonction de prototype void additionner(char S1[ ], char S2[ ],char SOM[ ]); qui place dans la chaine SOM la somme des nombres représentés par les ChaineChiffres S1 et S2. Rappel : Les valeurs décimales des codes ASCII des caractères chiffres sont indiquées dans le tableau qui suit : Caractère '0' '1' '2' '3' '4' '5' '6' '7' '8' '9' Code ASCII 48 49 50 51 52 53 54 55 56 57 Exemple : si S1= "129782004977" et S2= "754022234930" alors après l'appel de la fonction additionner(S1,S2,SOM), on aura SOM= "883804239907". Problème II : Distance de Hamming 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. Dans ce problème, on se propose d'implémenter des fonctions pour calculer la distance de Hamming. Question 1 : Distance de Hamming entre deux chaînes de caractères La distance de Hamming entre deux chaînes de caractères de même 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. Écrire 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 chaînes de caractères de même longueur M et on suppose que le paramètre M est strictement positif) Question 2 : Distance de Hamming d'un langage On appellera langage, un tableau de chaînes de caractères toutes de memes longueurs. La distance de Hamming d'un langage est égale au minimum des distance de Hamming entre deux chaînes de ce langage différentes deux à deux. Exemple : Si langage={"aabb","xayy","tghy","xgyy"}, sa distance de Hamming est de 1 Ecrire une fonction d'entête : int distanceH_langage(char langage[NB][L]), qui retourne la distance de Hamming de son paramètre langage (le paramètre langage est un tableau de NB chaînes de caractères toutes de même longueur L, NB et L sont 2 constantes entières strictement positives déjà définies) -Devoir libre N° 1 page 3/3- Question 3 : Distance de Hamming entre 2 nombres entiers positifs La distance de Hamming entre 2 nombres entiers positifs est le nombre de bits distincts dans leurs représentations binaires (voir exemple) Exemple : la distance de Hamming entre les nombres 7 et 4 est 2 ( 7 est représenté en binaire sur un octet (8bits) par 00000111 et 4 est représenté en binaire par 00000100) Question 3-a: Écrire 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: Écrire une fonction d'entête : int distanceNombre(int A , int B) qui calcule et retourne la distance de Hamming entre les nombres A et B ( On suppose que 0<=A<256 et 0<=B<256) Problème III : Fusion de deux tableaux triés Ecrire le code de la fonction void fusioner( int T1[N1] , int T2[N2] , int T3[N1+N2]) qui permet de fusionner les deux tableaux T1 et T2 de telle sorte à obtenir un tableau T3 trié mais qui ne contient pas des doublons. Les dernières cases de T3 seront égales à -1. Exemple : T1 = 6 14 33 51 55 59 63 81 88 89 T2 = 4 19 51 56 63 200 T3 = 4 6 14 19 33 51 55 56 59 63 81 88 89 200 -1 -1 -Corrigé du Devoir libre N° 1 page 1/3- SMI -SMA/S4 Module : Structures de données 2014-2015 Prof : S.NOUH PROBLÈME I: REPRÉSENTATION DE GRANDS NOMBRES ENTIERS NATURELS #include<stdio.h> #include<conio.h> #include<string.h> #include<stdlib.h> char* S; int ChaineChiffres() {int i; if (strlen(S)==0) return(0); for(i=0;i<strlen(S);i++) if(S[i]<'0' && S[i]>'9')return(0); return(1); } void supprimer_zeros() {int i; while(S[0]=='0') for(i=0;i<strlen(S);i++)S[i]=S[i+1]; } void add(char a, char b, char c, char* r, char* s) {*s='0'+ (a+b+c-3*'0')%10; *r='0'+(a+b+c-3*'0'>=10);} void CompleterXPar0G(char X[], char Y[]) {char*Z=(char*)malloc(strlen(Y)+1); strcpy(Z,""); int i; for(i=0;i<strlen(Y)-strlen(X);i++) {strcat(Z,"0");} strcat(Z,X); strcpy(X,Z); } Corrigé -Corrigé du Devoir libre N° 1 page 2/3- void additionner(char S1[], char S2[], char S3[]) {char r,s; int max; if(strlen(S1)>strlen(S2)) {CompleterXPar0G(S2,S1); max=strlen(S1);} else {CompleterXPar0G(S1,S2); max=strlen(S2);} char*Z=(char*)malloc(max+2); int i=strlen(S1)-1, k=max+1; Z[k]='\0'; r='0'; k--; while(i>=0) {add(S1[i], S2[i], r, &r, &s); Z[k]=s; k--;i--; } Z[0]=r; strcpy(S3,Z); } main() {S=malloc(10); char S1[10]="6666", S2[20]="8888",S3[40]; additionner(S1,S2,S3); puts(S1);puts(S2);puts(S3); getch(); } Problème II : Distance de Hamming #include<stdio.h> #include<conio.h> #define L 20 #define NB 100 int distanceH(char S1[], char S2[], int M) {int s=0,i; for(i=0;i<M;i++)if(S1[i]!=S2[i])s++; return(s);} -Corrigé du Devoir libre N° 1 page 3/3- int distanceH_langage(char langage[NB][L]) {int d=L; int i,j; for(i=0;i<NB;i++) for(j=i+1;j<NB;j++) if(distanceH(langage[i],langage[j],L)<d) d=distanceH(langage[i],langage[j],L); } void binaire(char *bin ,int N) {int i=0; for(i=0;i<8;i++) bin[i]='0'; bin[7]='\0'; i=0; while(N!=0) {if((N%2)==0)bin[7-i]='0'; else bin[7-i]='1'; N=N/2; i++; }} int distanceNombre(int a, int b) {char ch1[8],ch2[8]; binaire(ch1,a);binaire(ch2,b); return(distanceH(ch1,ch2,L)); } Problème III : Fusion de deux tableaux triés #define N1 5 #define N2 5 int T[N1+N2]; void FusionerT1etT2dansT(int T1[N1],int T2[N2]) {int i=0,j=0,k=0; for(i=0;i<N1+N2;i++) T[i]=0; i=0; while(i<N1&&j<N2) { if(T1[i]<T2[j]){T[k]=T1[i];k++;i++;} if(T2[j]<T1[i]){T[k]=T2[j];k++;j++;} if(T2[j]==T1[i]){T[k]=T2[j];k++;j++;i++;} } while(i<N1) {T[k]=T1[i];k++;i++;} while(j<N2) {T[k]=T2[j];k++;j++;} } -Devoir libre N° 2 page 1/2 SMI /S4 Module : Structures de données 2014-2015 Prof : S.NOUH Exercice 1: Dans cet exercice on va gérer les nombres complexes qui sont des couples de réels, une partie réelle et une partie imaginaire. Déclarer le TYPE complexe. 1) Ecrire une procédure qui permet de lire un nombre complexe c. La variable c doit être passée par adresse pour que la procédure puisse affecter les valeurs lues à c. 2) Ecrire une fonction qui retourne le produit de deux complexes. 3) Ecrire une fonction qui retourne le module d’un nombre complexe. 4) Ecrire une procédure permettant l’affichage des nombres complexes sous la forme "ai+b". Exercice 2 : La structure Client contient les informations d’un client d’une banque (nom , numéro de compte et solde). Le nom peut contenir au maximum 31 caractères, le compte (numéro de compte) contient 24 caractères. struct date {int jour; int mois; int annee;} struct Client { char nom[32]; char compte[25]; float solde; struct date D ; }; uploads/Geographie/ exercices-re-solus-dalgorithmique-et-structures-de-donne-es.pdf