tp3_sol.pdf

ESIEE IGI-3005 TP no 3 (deux séances) (corrigé) 2014-2015

Tableaux (corrigé)

Table des matières1 Utilitaires 2

1.1 Affichage d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Mise à zéro d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Remplissage d’un tableau aléatoire (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Remplissage d’un tableau aléatoire trié (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Calcul sur les éléments d’un tableau 32.1 Somme des éléments d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Moyenne des éléments d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Résistance équivalente (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.4 Recherche d’éléments sur critère (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.5 Maximum d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.6 Indice du maximum d’un tableau (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.7 Un tableau est-il trié ? (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.8 Recherche séquentielle dans un tableau trié (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.9 Recherche dichotomique dans un tableau trié (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.10 Tests (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Copie et décalage de tableaux (**) 93.1 Copie simple de tableaux (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Copie sécurisée de tableaux (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 Décalage droite d’un tableau de réels (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.4 Décalage gauche d’un tableau de réels (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Les chaînes de caractères 124.1 Répétition (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2 Retournement d’une chaîne(*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.3 Recherche de motif (1) (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4 Recherche de motif (2) (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.5 Chercher/remplacer (*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.6 Fréquence (1) (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.7 Fréquence (2) (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.8 Conversion chaîne de caractères en entier (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Pour aller plus loin 155.1 Mise en majuscules (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155.2 Classement alphabétique (***) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.3 Des chiffres en lettres (**) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.4 Des nombres en lettres (****) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.5 Compteur de mots (***) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.6 Les huit reines (***) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Tous les exercices sont à faire.Sont à rendre (par binôme) :

– le programme de l’exercice 1.3– les programme des exercices 2.7, 2.8 et 2.9– les programme des exercices 3.3 et 3.4– les programmes des exercices 4.2 et 4.8

Les exercices sont à envoyer à l’adresse [email protected] objet obligatoire : IGI-3005 CR TP3 nom1 nom2- fonctions C commentées en pièces jointes (pas de zip)

–1/25–

mailto:[email protected]


Note : sauf spécification contraire, dans tous les exercices, on considérera que les tableaux contiennentau moins un élément.

1 Utilitaires

1.1 Affichage d’un tableau (*)

Exercice 1. Écrivez la fonction qui affiche les n premiers éléments d’un tableau de réels.Prototype : void affiche_tab(double t[], int n);

Corrigé

***************************************************************************void affiche(double t[], int n) {

int i;for (i=0;i<n;++i) {

printf("%10.5lf ",t[i]);}printf("\n");

}

***************************************************************************

1.2 Mise à zéro d’un tableau (*)

Exercice 2. Écrivez la fonction qui remplit un tableau de n réels par des zéros ( 0.0 ).

Prototype : double * raz(double t[], int n);Note : on retourne souvent pour une fonction opérant sur un tableau l’adresse de ce tableau, ce qui

permet d’enchaîner les appels dans une seule ligne. Par exemple :affiche(raz(t, n), n);

Corrigé

***************************************************************************double * raz(double t[], int n) {


t[i]=0.0;}return t;

}

***************************************************************************

–2/25–


1.3 Remplissage d’un tableau aléatoire (*)

Exercice 3. Écrivez la fonction qui remplit un tableau de n réels par des nombres pseudo-aléatoirescompris entre 0 et 1

Prototype : double * remplit_alea (double t[], int n);

Note : on se documentera sur la fonction C rand() déclarée dans stdlib.h .

Corrigé

***************************************************************************double * remplit_alea(double t[], int n) {


t[i]=rand()/(double)RAND_MAX;}return t;

}

***************************************************************************

1.4 Remplissage d’un tableau aléatoire trié (*)

Exercice 4. Écrivez la fonction qui remplit un tableau de n réels par des nombres pseudo-aléatoiresen ordre croissant.

Prototype : double * remplit_trie (double t[], int n);

Corrigé

***************************************************************************double * remplit_trie(double t[], int n) {

int i;t[0]=rand()/(double)RAND_MAX;for (i=1;i<n;++i) {

t[i]=t[i-1]+rand()/(double)RAND_MAX;}return t;

}

***************************************************************************

2 Calcul sur les éléments d’un tableau

2.1 Somme des éléments d’un tableau (*)

Exercice 5. Écrivez une la fonction qui calcule la somme des n premiers éléments d’un tableaude réels

Prototype : double somme (double t[], int n);

Corrigé

***************************************************************************Le principe est de parcourir le tableau pour en calculer la somme : dans une boucle, on accumulera dans

une variable les valeurs des éléments du tableau. Ce genre de boucle est appelé schéma d’accumulation.L’écriture mathématique Σb

i=aexpr(i) s’écrira en C :

–3/25–


var=0.0;for (i=a;i<=b;++i)

var += expr(i);

Le parcours séquentiel d’un tableau de n éléments en langage C se fait par une boucle allant de l’indice0 à l’indice n-1 (inclus). Il vaut mieux écrire la condition de répétition sous la forme i < n que sous laforme i <= n-1 , ce qui permet d’une part de gagner une soustraction par tour de boucle, et d’autre part degarder sous forme explicite le nombre d’éléments à traiter dans l’écriture du programme.

Ce qui donne la solution possible suivante :double somme(double t[], int n) {

int i;double total=0.0;for (i = 0 ; i < n ; ++i) {

total += t[i];}return total;

}

***************************************************************************

2.2 Moyenne des éléments d’un tableau (*)

Exercice 6. Écrivez une la fonction qui calcule la moyenne des n premiers éléments d’un tableaude réels

Prototype : double moyenne (double t[], int n);

Corrigé

***************************************************************************Il faut évidemment utiliser la fonction de l’exercice précédent (réutilisation) :

double moyenne(double t[], int n) {return somme(t,n)/n;

}

***************************************************************************

2.3 Résistance équivalente (**)

Exercice 7. Écrivez une fonction qui calcule la résistance équivalente d’un nombre quelconque derésistances en parallèle

Rappel :1

Réq=

n∑i=1

1

Ri

Prototype : double resistance (double r[], int n);

Corrigé

***************************************************************************C’est un schéma classique d’accumulation (somme des inverses des éléments du tableau), puis retour de

l’inverse de l’accumulateur.Un écueil à éviter est l’oubli du cas où un des éléments est nul, ce qui conduirait à une division par 0. La

solution consiste à retourner directement 0 si l’un des éléments est nul.

–4/25–


double resistance (double r[], int n) {double req=0.0;int i;for (i=0;i<n;++i) {

if (r[i]==0.0)return 0.0;

req += 1/r[i];}return 1/req;

}

***************************************************************************

2.4 Recherche d’éléments sur critère (*)

Exercice 8. Écrivez la fonction qui retourne l’indice du premier élément strictement négatif parmiles n premiers éléments d’un tableau de réels (-1 si aucun élément n’est négatif).

Prototype : int indice_premier_negatif (double t[], int n);

Corrigé

***************************************************************************Ici, l’analyse du problème nous conduit à la solution suivante :— on parcourt le tableau— si l’on rencontre un élément négatif, on termine la fonction en retournant l’indice courant— si l’on a parcouru l’intégralité du tableau sans avoir rencontré d’élément négatif, on retourne -1 comme

indiqué dans la spécification.Attention : c’est après la boucle que l’on peut constater l’absence d’élément négatif. Une erreur courante deprogrammation consiste à retourner -1 trop tôt, avec un test du style

if (t[i]<0) return i; else return -1;ce qui conduit à retourner -1 si le premier un élément n’est pas négatif.C’est toute la différence entre une recherche existentielle (∃i t[i] < 0) et une recherche universelle (∀i t[i] ≥

0).

–5/25–


int indice_premier_negatif (double t[], int n) {int i;for (i=0; i<n ; ++i) {

if (t[i]<0)return i;

}return -1;

}

***************************************************************************

2.5 Maximum d’un tableau (*)

Exercice 9. Écrivez la fonction qui retourne la valeur du plus grand des n premiers éléments d’untableau de réels

Prototype : double valeur_plus_grand (double t[], int n);

Corrigé

***************************************************************************Un parcours du tableau s’impose, avec une mémorisation du plus grand élément rencontré. En effet, le

plus grand élément du tableau peut se situer n’importe où (en début, en cours ou en fin de tableau) et doncon ne peut le connaître qu’après avoir examiné tous les éléments du tableau, et le mémoriser permettra de leretourner en fin de parcours.

L’initialisation de ce maximum pourra se faire par le premier élément du tableau ( t[0] ), et la boucle peutcommencer par l’indice 1.

Le corps de la boucle consistera à comparer l’élément courant au maximum, et, s’il lui est supérieur, à lemémoriser dans le maximum.

Ce qui conduit à la solution suivante :double valeur_plus_grand (double t[], int n) {

int i;double maxi=t[0];for (i=1;i<n;++i) {

if (t[i]>maxi)maxi=t[i];

}return maxi;

}

***************************************************************************

2.6 Indice du maximum d’un tableau (*)

Exercice 10. Écrivez la fonction qui retourne l’indice du plus grand des n premiers éléments d’untableau de réels (en cas d’ex-æquo, l’indice du premier d’entre eux)

Prototype : int indice_plus_grand (double t[], int n);

Corrigé

***************************************************************************Le programme est semblable au précédent. Un parcours du tableau s’impose, avec une mémorisation de

l’indice du plus grand élément rencontré. En effet, le plus grand élément du tableau peut se situer n’importeoù (en début, en cours ou en fin de tableau) et donc on ne peut le connaître qu’après avoir examiné tous leséléments du tableau ; mémoriser sa position permettra de la retourner en fin de parcours.

L’initialisation de cet indice maximum pourra se faire par l’indice du premier élément du tableau (0), et laboucle peut commencer par l’indice 1.

Ce qui conduit à la solution suivante :

–6/25–


int indice_plus_grand (double t[], int n) {int i;int imax=0;for (i=1;i<n;++i) {

if (t[i]>t[imax])imax=i;

}return imax;

}

***************************************************************************

2.7 Un tableau est-il trié ? (*)

Exercice 11. Écrivez la fonction qui retourne 1 si les n premiers éléments du tableau sont en

ordre croissant (au sens large) et 0 sinon

Prototype : int est_trie(double t[], int n);

Corrigé

***************************************************************************Un parcours de tableau à partir de l’indice 1 pour vérifier la propriété ∀i ∈ [1;n[t[i] ≥ t[i − 1] Ce qui

conduit à la solution suivante :int est_trie(double t[], int n) {


if (t[i]<t[i-1])return 0;

}return 1;

}

***************************************************************************

2.8 Recherche séquentielle dans un tableau trié (*)

Exercice 12. Écrivez la fonction qui retourne la position d’insertion éventuelle d’une valeur dansun tableau supposé trié (recherche séquentielle).

Note : La fonction doit retourner la place du premier x dans le tableau s’il est présent, ou la placeoù devrait se trouver x dans le tableau s’il est absent.

Prototype : int rech_seq_tab_trie(double x, double t[], int n);

Corrigé

***************************************************************************Comme le tableau est trié, le programme revient à un parcours de tableau sur n éléments, mixé à une

recherche de sentinelle généralisée : le premier élément du tableau ≥ x. Ce qui conduit à la solution suivante :int rech_seq_tab_trie(double x, double t[], int n) {

int i;for (i=0 ; i<n; ++i) {

if (t[i] >= x)return i;

}return n;

}

***************************************************************************

–7/25–


2.9 Recherche dichotomique dans un tableau trié (**)

Exercice 13. Écrivez la fonction qui retourne la position d’insertion éventuelle d’une valeur dansun tableau supposé trié (recherche dichotomique).

Note : La fonction doit retourner la place du premier x dans le tableau s’il est présent, ou la placeoù devrait se trouver x dans le tableau s’il est absent.

Prototype : int rech_dicho_tab_trie(double x, double t[], int n);

Corrigé

***************************************************************************Comme vu en cours, l’invariant du programme peut être debut < pos ≤ fin. L’algorithme du cours se

traduit immédiatement en C :int rech_dicho_tab_trie(double x, double t[], int n) {

int d, f, m;/* pos doit être comprise entre 0 (x<=t[0]) et n (x>t[n-1]) *//* Invariant logique : d < pos <=f */d = -1; /* d < pos */f = n; /* pos<= f */while (d+1 < f) {

m = (d+f)/2;if (t[m] < x) { /* x est forcément après m */

d = m; /* d<pos */}else { /* x est avant ou en m */

f = m; /* pos <= f */}

}/* d < pos <=f et d+1==f ==> pos = f */return f;

}

***************************************************************************

2.10 Tests (*)

Exercice 14. Écrivez la fonction qui teste les deux fonctions précédentes.Note : La fonction doit créer des données de tests (tableau trié, taille, valeur cherchée), des résul-

tats attendus, puis pour chaque donnée de test, appeler rech_seq_tab_trie et rech_dicho_tab_trie etsignaler (messages) la non égalité du résultat obtenu avec le résultat attendu.

Prototype : void test_seq_et_dicho_tab_trie(void);

Corrigé

***************************************************************************Par exemple :

void test_seq_et_dicho_tab_trie() {double tab[] = {1.0, 1.0, 2.0, 2.0, 3.0, 4.0, 5.0, 5.0};double test_x[] = {0.0, 1.0, 1.1, 2.0, 3.0, 3.5, 5.0, 6.0};int res[] = { 0 , 0, 2, 2, 4, 5, 6, 8 };int i, poss, posd;int pbs=0, pbd = 0;for (i=0; i<sizeof(test_x)/sizeof(test_x[0]);++i) {

poss = rech_seq_tab_trie(test_x[i], tab, sizeof(tab)/sizeof(tab[0]));posd = rech_dicho_tab_trie(test_x[i], tab, sizeof(tab)/sizeof(tab[0]));if (poss != res[i]) {

printf("Probleme seq test no %d. Res attendu :%d, res obtenu : %d\n",i, res[i], poss);

–8/25–


pbs+=1;}if (poss != res[i]) {

printf("Probleme dicho test no %d. Res attendu :%d, res obtenu : %d\n",i, res[i], posd);

pbd+=1;}

}if (pbs+pbd==0) {

printf("\n\nTest passe avec succes\n");}else {

printf("\n\nTest echoue : %d erreur(s)\n",pbs+pbd);}

}

***************************************************************************

3 Copie et décalage de tableaux (**)

3.1 Copie simple de tableaux (*)

Exercice 15. Écrivez la fonction qui copie les n premiers éléments d’un tableau source de réelsdans le tableau destination et retourne l’adresse du tableau destination

Prototype : double * copie (double destination[], double source[], int n);

Corrigé

***************************************************************************La solution naturelle est basée sur le principe : on parcourt parallèlement les deux tableaux et on copie

élément par élément le contenu du tableau source dans le tableau destination, ce qui donne :double *copie(double destination[], double source[], int n) {/* Attention : ne fonctionne que si* les tableaux ne se recouvrent pas

*/int i;for (i=0 ; i<n ; ++i) {

destination[i] = source[i];}return destination;

}

ou en plus concis :double *copie(double destination[], double source[], int n) {/* Attention : ne fonctionne que si* les tableaux ne se recouvrent pas

*/double *ret = destintation;while (n--) {

*destination++ = *source++;}return ret;

}

***************************************************************************

3.2 Copie sécurisée de tableaux (**)

–9/25–


Exercice 16. Écrivez la fonction qui copie de manière sécurisée les n premiers éléments d’untableau source de réels dans le tableau destination et retourne l’adresse du tableau destination

Attention : On devra prendre en compte le fait que les deux tableaux peuvent se recouvrir partiel-lement.

Prototype : double * copie_sec (double destination[], double source[], int n);

Corrigé

***************************************************************************Dans la solution précédente, une erreur peut survenir lorsque l’on appelle cette fonction avec deux tableaux

se recouvrant. Par exemple, avec le morceau de programme suivant :double tab[]={8,2,103,-4,5,8};copie(&tab[1],tab,5);/* tentative de decalage droite */

On voudrait décaler d’une position vers la fin de tableau les cinq premiers éléments. Or la fonction va écrasersuccesivement les éléments du tableau qu’elle n’a pas encore copiés, ce qui conduira au résultat suivant :8 8 8 8 8 8

alors que l’on aurait voulu obtenir :8 8 2 103 -4 5

Faire la boucle dans l’autre sens (de la fin vers le début) poserait le même problème pour un décalage versla gauche.

Une solution consiste à tester la position en mémoire de la source par rapport à la destination :— si source est avant destination, on copie de la fin vers le début— si source est après destination, on copie du début vers la finPour tester le positionnement des deux tableaux, il suffit de les soustraire. La différence de deux pointeurs

de même type donne le nombre d’éléments de ce type situés entre ces deux pointeurs. Ainsi, quel que soit letype de t :

&t[5] - &t[3] vaut 2&t[3] - &t[5] vaut -2Ce qui conduit à :

double *copie_sec(double destination[], double source[], int n) {/* fonctionne meme si les tableaux se recouvrent */

int i;if (destination - source < 0 ) {

for (i=0 ; i<n ; ++i) {destination[i] = source[i];

}}else {

for (i=n-1 ; i>=0 ; --i) {destination[i] = source[i];

}}return destination;

}

Attention : les fontions memcpy (copie de zones mémoires) et strcpy (copie de chaînes de caractères) dela librairie libc ne gèrent pas les recouvrements. Ci-dessous, un extrait de la documentation de memcpy :

If the regions overlap, the behavior is undefined.

***************************************************************************

–10/25–


3.3 Décalage droite d’un tableau de réels (*)

Exercice 17. Écrivez la fonction qui décale de k éléments vers la droite les éléments d’un tableaude réels compris entre l’indice d (inclus) et l’indice f (inclus) et retourne l’adresse du tableau.

Prototype : double *decale_droite (double t[], int k, int d, int f);

Corrigé

***************************************************************************Attention à l’ordre de copie.

double *decale_droite(double t[], int k, int d, int f) {int i;for (i=f ; i>=d ; --i) {

t[i+k] = t[i];}return t;

}

ou à l’aide de copie_sec :

double *decale_droite(double t[], int k, int d, int f) {copie_sec(t+d+k, t+d, f-d+1);return t;

}

***************************************************************************

3.4 Décalage gauche d’un tableau de réels (*)

Exercice 18. Écrivez la fonction qui décale de k éléments vers la gauche les éléments d’un tableaude réels compris entre l’indice d (inclus) et l’indice f (inclus) et retourne l’adresse du tableau.

Prototype : double *decale_gauche (double t[], int k, int d, int f);

Corrigé

***************************************************************************Attention à l’ordre de copie.

double *decale_gauche (double t[], int k, int d, int f) { int i;for (i=d ; i<=f ; ++i) {

t[i-k] = t[i];}return t;

}

ou à l’aide de copie_sec :

double *decale_gauche(double t[], int k, int d, int f) {copie_sec(t+d-k, t+d, f-d+1);return t;

}

***************************************************************************

–11/25–


4 Les chaînes de caractères

4.1 Répétition (*)

Exercice 19. Écrivez une fonction qui prend en argument une chaîne de caractères et l’affiche enrépétant chaque caractère n fois

Prototype : void * repete (char * s, int n);

L’appel repete("toto", 3) affichera tttoootttooo .

Corrigé

***************************************************************************void repete (char * s, int n) {

int i,j;for (i=0;s[i]!=0;++i)

for (j=0;j<n;++j)printf("%c",s[i]);

}

***************************************************************************

4.2 Retournement d’une chaîne(*)

Exercice 20. Écrivez une fonction qui prend en argument une chaîne de caractères, la renversesur elle-même ("toto→"otot") et retourne l’adresse de cette chaîne

Prototype : char * miroir (char * s);

Corrigé

***************************************************************************Il faut déjà parcourir la chaîne pour accéder à son dernier caractère. Puis permuter les couples de caractères

symétriques en évitant de le faire deux fois, ce qui laisserait la chaîne inchangée.char * miroir (char * s) {

int g,d; /* indice gauche et droit de parcours */char c;for (d=0;s[d]!=0;++d){

/* on ne fait rien : on se contente de parcourir la chaîne */}

for (g=0,--d ; g<d ; ++g,--d) {c=s[g];s[g]=s[d];s[d]=c;

}return s;

}

***************************************************************************

4.3 Recherche de motif (1) (**)

Exercice 21. Écrivez une fonction qui prend en argument deux chaînes de caractères et retourne1 si la première chaîne de caractères commence par la seconde et 0 sinon. Écrivez un programmepour tester cette fonction.

–12/25–


Prototype : int debute_par (char * chaine1, char * chaine2);

Par exemple, debute_par ("ESIEE","ES") → 1

Corrigé

***************************************************************************Il suffit de regarder pour chaque caractère de chaine2 s’il est égal au caractère correspondant de chaine1 .

Dès qu’il y a inégalité, on retourne 0 (faux). Si on arrive en bout de chaine2 sans avoir détecté d’inégalité,on retourne 1 (vrai).

Note : ce programme renvoie toujours 1 si la chaine2 est vide.int debute_par (char * chaine1, char * chaine2) {

int i;for (i=0;chaine2[i]!='\0';++i)

if (chaine1[i]!=chaine2[i])return 0;

return 1;}

***************************************************************************

4.4 Recherche de motif (2) (**)

Exercice 22. Écrivez une fonction qui prend en argument deux chaînes de caractères et retournela position de la première occurrence de la chaîne2 dans la chaîne1 si elle y est présente et −1 sinon.

Prototype : int presence (char * chaine1, char * chaine2);

Corrigé

***************************************************************************Une boucle contenant un appel à debute_par permettra de détecter la présence de la sous-chaîne.Note : ce programme considère que la chaîne vide débute toute chaîne (retour 0).

int presence (char * chaine1, char * chaine2) {int i;for (i=0;chaine1[i]!='\0';++i) {

if (debute_par(&chaine1[i],chaine2)) {return i;

}}return -1;

}

***************************************************************************

4.5 Chercher/remplacer (*)

Exercice 23. Écrivez une fonction qui recherche dans une chaîne chaque caractère c pour leremplacer par un caractère r et retourne l’adresse de la chaîne.

Prototype : char * cherche_remplace (char c, char r, char * s);

Corrigé

***************************************************************************C’est un parcours simple avec remplacement lorsque l’on tombe sur le caractère à remplacer :

–13/25–


char * cherche_remplace (char c, char r, char * s) {int i;for (i=0;s[i]!='\0';++i)

if (s[i]==c)s[i]=r;

return(s);}

***************************************************************************

4.6 Fréquence (1) (**)

Exercice 24. Écrivez une fonction qui compte le nombre d’occurrences d’un caractère c dans unechaîne s. La fonction pourra être récursive. Écrivez un programme pour tester cette fonction.

Prototype : int compte(char c, char * s);

Corrigé

***************************************************************************C’est encore un accumulateur :

int compte (char c, char * s) {int i,acc=0;for (i=0;s[i]!='\0';++i)

if (s[i]==c)++acc;

return(acc);}

Une fonction récursive peut être écrite selon le principe suivant :int compte2 (char c, char * s) {

if (*s=='\0') /* s[0] == '\0' */return 0;

return ((*s==c)?1:0)+compte2(c,s+1);}

***************************************************************************

4.7 Fréquence (2) (**)

Exercice 25. Écrivez une fonction qui prend en argument un tableau de n char , remplit untableau d’entiers avec les fréquences des 256 caractères ASCII et retourne l’adresse de ce tableau.

Prototype : int * frequence (char t[], int n ,int freq[]);

Attention : on parle ici de tableau de n caractères, qui peut contenir le célèbre '0' .

Corrigé

***************************************************************************C’est un parcours simple avec incrémentation dans le tableau du compteur indicé par le caractère courant.

int *frequence (char t[], int n ,int f[]) {int i;for (i=0;i<256;++i)

f[i]=0;for (i=0;i<n;++i)

++f[(unsigned char)t[i]];return f;

}

***************************************************************************

–14/25–


4.8 Conversion chaîne de caractères en entier (**)

Exercice 26. Écrivez une fonction qui prend en argument une chaîne de caractères représentantun entier en décimal et retourne l’entier équivalent ("123" → 123)

Note : on supposera que la chaîne est correcte et représente bien un entier.Prototype : int chaine_vers_entier (char * s);

Corrigé

***************************************************************************Une chaîne représentant un entier est composée d’une suite de caractères chiffres (compris entre '0' et

'9' ), éventuellement précédée d’une caractère '-' ou '+' .La valeur entière correspondant à un caractère chiffre est égal à ce caractère moins le caractère '0' .

( '2'-'0' vaut 2).S’il y a un signe, on le mémorise sous le forme d’une variable valant -1 ou +1. Puis, on accumule dans

un résultat le nombre représenté selon le principe suivant : pour chaque chiffre, on multiplie par 10 la valeuraccumulée et on ajoute la valeur du chiffre.

En fin de calcul, on retourne le résultat multiplé par le signe.int chaine_vers_entier (char * s) {

int i=0, signe=1, res=0;if (s[i]=='+')

++i;else if (s[i]=='-') {

signe=-1;++i;

}for(;s[i]!='\0';++i) {

res=res*10+s[i]-'0';}return signe*res;

}

Note : c’est ainsi que les fontions du genre atoi (conversion d’une chaîne en int ) de la librairie libcopèrent. Elles permettent également la conversion d’une chaîne exprimant un nombre en base 8 (commençantpar un 0 ) ou en base 16 (commençant par 0x ou 0X ). De plus, elles interrompent le calcul lorsqu’ellesparviennent à un caractère non autorisé et retournent le résultat courant.

***************************************************************************

5 Pour aller plus loin

5.1 Mise en majuscules (**)

Exercice 27. Écrivez une fonction qui prend en argument une chaîne de caractères, la transformeen majuscules ("toto" → "TOTO") et retourne son adresse

On laissera inchangés les caractères non lettre. On prendra en compte les caractères accentués oucédillés en les transformant en leurs majuscules sans accent ou sans cédille. Réfléchissez au problème queposent les ligatures (æ, œ) et proposez une solution.

Prototype : char * majuscule (char * s);

Corrigé

***************************************************************************Cet exercice (et les suivants qui s’en servent) avait pour but de vous sensibiliser aux problèmes de l’en-

codage das caractères selon les plate-formes et les langues. Il y a trop bien réussi. À l’ESIEE, sur une mêmemachine, l’encodage de l’éditeur de texte et de la console peuvent différer. Pour ceux que cela intéresse,

–15/25–


la page http://pagesperso-systeme.lip6.fr/Jean-Francois.Perrot/inalco/cours11/index.htmldonne une présentation très complète du sujet.

Concernant le programme proprement dit (mise en majuscule d’une chaîne de caractères), il faut déjà écrireune fonction utilitaire de majuscule d’un caractère.

Prototype : int maj(int c);

La fonction est déclarée avec le type int pour son retour et son paramètre, pour permettre le passage oule retour des caractères classiques, plus EOF (end of file), en général défini par −1.

Les caractères lettres non accentuées ont les majuscules précédant de 32 (20 hexa) leurs minusculescorrespondantes, ce qui peut donner comme code pour traiter les minuscules :

if ('a'<=c && c<='z') return c-32;Il vaut toutefois mieux écrire :if ('a'<=c && c<='z') return c-'a'+'A';ce qui évite le magic number 32.Concernant les lettres accentuéess, une solution consiste à les lister toutes, avec leurs majuscules asscociées,

et les programmer à l’aide d’un switch , ce qui est pénible et peu efficace.Une meilleure solution, tout aussi pénible, mais plus efficace, consiste à créer un tableau indicé par les

caractères, initialisée une fois pour toutes, comme par exemple :

static int TABMAJ[256];

void inittabmaj() {int i;

for (i=0;i<256;++i) {TABMAJ[i]=i;

}for (i='a';i<='z';++i) {

TABMAJ[i]=i+'A'-'a';}TABMAJ[(unsigned char)'à']='A';TABMAJ[(unsigned char)'é']='E';/* etc ... */

}

De plus, cette solution peut être adaptée à plusieurs types de majuscules (’é’ → ’E’ pour un classementalphabétique, ’é’ → ’É’ pour un traitement de texte)

int maj(int c) {if (0<=c && c<=255)

return TABMAJ[c];return c;

}

Note : Il existe des fonctions int tolower(int) , int isdigit(int) , etc. déclarées dans ctype.h quipermettent de gérer tout ce qui concerne les lettres non accentuées. Ces fonctions faisant référence à unetable indicée par les caractères, il faut transtyper un argument char en unsigned char pour éviter les indicesnégatifs générant une sortie du tableau.

La fonction majuscule demandée s’écrit alors simplement :

char * majuscule (char * s) {int i;for (i=0;s[i]!='\0';++i) {

s[i]=maj((unsigned char)s[i]);}return s;

}

Le cas des ligatures (æ, œ) est plus délicat. La normalisation "æ" → "AE" change le nombre de caractèreet nécessite alors un buffer de réception de la chaîne normalisée (qui ne sera pas de même taille que la chaîneinitiale).

***************************************************************************

–16/25–

http://pagesperso-systeme.lip6.fr/Jean-Francois.Perrot/inalco/cours11/index.html


5.2 Classement alphabétique (***)

Exercice 28. Écrivez une fonction qui prend en argument deux chaînes de caractères et retourne -1si la première (mise en majuscule) est avant la seconde (mise en majuscule) par ordre alphabétique,0 si elles sont identiques (mises en majuscules) et 1 si la première est après la seconde. Prenez encompte les lettres accentuées et les ligatures (bœuf)

On pourra utiliser strcmp (déclaré dans string.h ). Par exemple,

compare("chat", "chien") → −1

compare("zèbre","éléphant") → 1

compare("corne","COR") → 1

compare("relevé","relève") → 0

Prototype : int compare (char * s1, char * s2);

Corrigé

***************************************************************************Attention : on suppose ici que l’on dispose d’une fonction majuscule permettant de normaliser une chaîne

de caractères.int compare (char * s1, char * s2) {

int i;majuscule(s1);majuscule(s2);for(i=0;s1[i]==s2[i];++i) /* ou utiliser strcmp */

if (s1[i]==0)return 0;

return (s1[i]<s2[i])?-1:1;}

***************************************************************************

5.3 Des chiffres en lettres (**)

Exercice 29. Écrivez une fonction qui prend en argument un nombre de un chiffre et remplitune chaîne avec l’écriture en lettres de ce chiffre(par exemple, 8 → "huit"). On supposera que lamémoire allouée pour la chaîne est suffisante.

Prototype : char * chiffre_vers_chaine (int n, char * s);

Corrigé

***************************************************************************Une table static suffira pour cette fonction.

#include <string.h>

char * chiffre_vers_chaine (int n, char * s) {static char *chiffres[10]={

"zéro", "un", "deux", "trois", "quatre","cinq", "six", "sept", "huit", "neuf"};

return strcpy(s,chiffres[n]);}

***************************************************************************

–17/25–


5.4 Des nombres en lettres (****)

Exercice 30. Généralisez le programme précédent pour faire afficher les nombres entiers en touteslettres (par exemple, 895 → "huit cent quatre-vingt-quinze").

Renseignez-vous sur les règles d’écriture des nombres en français.Prototype : void affiche_en_lettres (int n);

Corrigé

***************************************************************************Ci-dessous un programme écrit il y a plusieurs années qui semble encore fonctionner.

#include <stdio.h>#include <string.h>/********************************************************* Calcul et retour de : l'écriture en toutes lettres ** d'un petit nombre entier ** fonctionne pour 0-999 ** les règles d'écriture d'un nombre en lettres sont ** tirées de "Grévisse Le bon usage" (p.572 & suivantes)** *********************************************************/

char* nb_en_lettres(char *buffer, int nombre) {static char *nom_simple[]={"zéro", "un","deux","trois","quatre", "cinq","six","sept","huit","neuf","dix","onze","douze","treize","quatorze","quinze","seize"};

char txt[128]; /* pour les écritures intermédiaires(le 17 de 77 p.ex.) */

if (nombre<=16) { /* 0 - 16 */strcpy(buffer,nom_simple[nombre]);

/* en dessous de 17, trivial */return(buffer);

}if (nombre<=59) { /* 17-59 */

switch(nombre/10) {case 1 : strcpy(buffer,"dix");

break; /* 17 - 19 */case 2 : strcpy(buffer,"vingt");

break; /* 20 - 29 */case 3 : strcpy(buffer,"trente");

break; /* 30 - 39 */case 4 : strcpy(buffer,"quarante");

break; /* 40 - 49 */case 5 : strcpy(buffer,"cinquante");

break; /* 50 - 59 */}if (nombre%10==0) /* 20, 30, 40, 50 */

return(buffer);if (nombre%10==1) /* 21,31,41,51 */

strcat(buffer," et ");else /* 17-19,22-29,32-39,42-49,52-59 */

strcat(buffer,"-");return(strcat(buffer,nom_simple[nombre%10])) ;

}if (nombre<=79) { /* 60-79 */

strcpy(buffer,"soixante");if (nombre==60) /* 60 */

return (buffer);if (nombre%10==1)

strcat(buffer," et "); /*61, 71*/else

strcat(buffer,"-"); /* 62-69 72-79 */return (strcat(buffer,nb_en_lettres(txt,nombre-60)));

–18/25–


}if (nombre<=99) { /* 80-99 */

strcpy(buffer,nb_en_lettres(txt,4));strcat(buffer,"-");strcat(buffer,nb_en_lettres(txt,20));if (nombre==80) /* 80 */

return (strcat(buffer,"s"));strcat(buffer,"-"); /* 81-99 */return (strcat(buffer,nb_en_lettres(txt,nombre-80)));

}if (nombre<1000) { /*100-999 */

if (nombre>=200) { /*200-999 */strcpy(buffer,nb_en_lettres(buffer,nombre/100));strcat(buffer," ");

}else {

strcpy(buffer,"");}strcat(buffer,"cent");if (nombre%100==0) {

/* 100,200,300,400,500,600,700,800,900 */if (nombre>=200)

/* 200,300,400,500,600,700,800,900 */strcat(buffer,"s");

return(buffer);}strcat(buffer," ");/*101-199 201-299 etc */return(strcat(buffer,nb_en_lettres(txt,nombre%100)));

}return("Erreur");

}

/* nombre = md (milliard(s)) mn (million(s)) m (mille) n1234567890= 1 234 567 890*/

/* Règle :md, mn, m, n sont des nombres inférieurs à 1000md, mn, n s'écrivent de la même facon (voir la règle

des nombres <1000)m suit la meme règle sauf :si m=1, il ne s'écrit pas (mille deux, pas un mille deux)si m=c80(avec c un chiffre quelconque) ou c00 (avec c>=2),le s final de l'écriture de m disparait(deux cents, mais deux cent mille)

*/

char *nombre_en_lettres(char *buffer, unsigned long nombre) {int md,mn,m,n;char txt[80];md=(int)(nombre/1000000000L); /* milliards */mn=(int)((nombre%1000000000L)/1000000L); /* millions */m = (int)((nombre%1000000L)/1000); /* mille */n=(int)(nombre%1000); /* unités (<1000) */strcpy(buffer,"");if (md!=0) {

nb_en_lettres(txt,md);strcat(buffer,txt);strcat(buffer, " milliard");if (md>1)

strcat(buffer,"s");}

if (mn!=0) {if (md!=0)

–19/25–


strcat(buffer," ");nb_en_lettres(txt,mn);strcat(buffer,txt);strcat(buffer, " million");if (mn>1)

strcat(buffer,"s");}

if (m!=0) {if (md!=0 || mn!=0)

strcat(buffer," ");if (m>1) {

nb_en_lettres(txt,m);if (m%100==80 || m%100==0 && m>100)

/* suppression du 's' pour 200000 ou 80000*/txt[strlen(txt)-1]='\0';

strcat(buffer,txt);strcat(buffer," ");

}strcat(buffer, "mille"); /* toujours invariable */

}if (n!=0) {

if (md!=0 || mn!=0 || m!=0)strcat(buffer," ");

nb_en_lettres(txt,n);strcat(buffer,txt);

}if (nombre==0) { /* cas particulier de 0 tout seul */

nb_en_lettres(txt,0);strcat(buffer,txt);

}return buffer;

}

int test(void) {

/* à vérifier :1) les orthographes des noms simples 0 à 16 et des nomsservant à composer des noms complexesRègle 01000 0 zéro

01001 1 un01002 2 deux01003 3 trois01004 4 quatre01005 5 cinq01006 6 six01007 7 sept01008 8 huit01009 9 neuf01010 10 dix01011 11 onze01012 12 douze01013 13 treize01014 14 quatorze01015 15 quinze01016 16 seize01017 20 vingt01018 30 trente01019 40 quarante01020 50 cinquante01021 60 soixante01022 100 cent01023 1000 mille01024 1 000 000 million01025 1 000 000 milliard

2) les rèles pour les nombres entre 17 et 5902000 Les multiples de 10 s'écrivent seuls

(sans - ou 'et' ou zéro)02001 Les nombres se terminant par 1 s'écrivent

<dizaine>" et un"

–20/25–


02002 Les autes nombres s'écrivent<dizaine>"-"<unité>

3) les règles pour les nombres de 60 à 7903000 60 s'écrit "soixante"03001 61 s'écrit "soixante et un"03002 71 s'écrit "soixante et onze"03003 Les autres nombres s'écrivent

"soixante-"<nom de (nombre-60)>

4) les règles pour les nombres de 80 à 9904000 80 s'écrit "quatre-vingts" s'il termine

le nombre04001 80 s'écrit "quatre-vingt" s'il ne termine

pas le nombre04002 81 s'écrit "quatre-vingt-un"04003 91 s'écrit "quatre-vingt-onze"04004 Les autres nombres s'écrivent

"quatre-vingt-"<nom de (nombre-80)>

5) les règles pour les nombres de 100 à 19905000 100 s'écrit "cent"05001 Les autres nombres s'écrivent

"cent "<nom du mombre-100>

6) les règles pour les nombres de 200 à 99906000 Les multiples de 100 s'écrivent

<nom du chiffre des centaines>" cents"s'ils terminent le nombre

06001 Les multiples de 100 s'écrivent<nom du chiffre des centaines>" cent"

s'ils ne terminent le nombre06002 Les autres nombres s'écrivent

<nom du chiffre des centaines>" cent "<nom du nombre modulo 100>

7) les règles pour les nombres de 1000 à 199907000 1000 s'écrit "mille"

07001 Les autres nombres s'écrivent"mille "<nom du nombre modulo 1000>

8) les règles pour les nombres de 2000 à 999 99908000 Les multiples de 1000 s'écrivent

<nom du nombres de milliers>" mille"08001 Les autres nombres s'écrivent

<nom du nombre de milliers>" mille "<nom du nombre modulo 1000>

9) les règles pour les nombres de 1 000 000 à 1 999 99909000 1 000 000 s'écrit "un million"09001 Les autres nombres s'écrivent

"un million "<nom du nombre modulo 1 000 000>

10) les règles pour les nombres de 2 000 000 à 999 999 99910000 Les multiple de 1 000 000 s'écrivent

<nom du nombre de millions>" millions"10001 Les autres nombres s'écrivent

<nom du nombre de millions>" millions "<nom du nombre modulo 1 000 000>

11) les règles pour les nombres de 1 000 000 000à 1 999 999 999

11000 1 000 000 000 s'écrit "un millard"11001 Les autres nombres s'écrivent

"un millard "<nom du nombre modulo 1 000 000 000>

12) les règles pour les nombres de 2 000 000 000à 999 999 999 999

12000 Les multiple de 1 000 000 000 s'écrivent<nom du nombre de milliards>" milliards"

12001 Les autres nombres s'écrivent<nom du nombre de milliards>" milliards "

–21/25–


<nom du nombre modulo 1 000 000 000>*/

struct test {unsigned long n;char *l;

} t[]={{0,"zéro"},/*01000 */

{2345678900, "deux milliards trois cent quarante-cinq \millions six cent soixante-dix-huit mille neuf cents"},

{4000000000, "quatre milliards"},/* 12000, 01002 */

{1600000000,"un milliard six cents millions"},/* 12001, 10000, 01003 01004 01024*/

{1000000000, "un milliard"},/* 11001, 09000 */

{1110000,"un million cent dix mille"},/*10001,08001,06001,06002,04004,0123,01022 */

{1000000,"un million"},{1192,"mille cent quatre-vingt-douze"},{1000,"mille"},{100,"cent"},{91081080,"quatre-vingt-onze millions \

quatre-vingt-un mille quatre-vingts"},{80071061,"quatre-vingts millions soixante \

et onze mille soixante et un"},{60059031,"soixante millions cinquante-neuf \

mille trente et un"},{20016015,"vingt millions seize mille quinze"},{14013012,"quatorze millions treize mille douze"},

{84,"quatre-vingt-quatre"},{180,"cent quatre-vingts"},{2123,"deux mille cent vingt-trois"},{1001001100L,"un milliard un million mille cent"},{80,"quatre-vingts"},{2,"deux"},{21,"vingt et un"}

};char buffer[1024];

int i,c=0;for (i=0;i<sizeof(t)/sizeof(t[0]);++i)

if (strcmp(t[i].l,nombre_en_lettres(buffer,t[i].n))!=0) {printf("Problème pour : %lu\nAttendu : <%s>\n\

Obtenu : <%s>\n",t[i].n,t[i].l,buffer);++c;

}printf("%d problème(s) dans les tests inclus\n",c);return c;

}

int main() {unsigned int n; char b[1024];test();do {

–22/25–


printf("Entrez un entier positif (0 pour finir) : ");scanf("%d",&n);printf("%s\n",nombre_en_lettres(b,n));

} while (n!=0);getchar();return 0;

}

***************************************************************************

5.5 Compteur de mots (***)

Exercice 31. Écrivez une fonction qui compte le nombre de mots dans une chaîne de caractères(la documentation devra définir exactement ce que l’on entend par mot). Écrivez un programmepour tester cette fonction.

Prototype : int compte_mots (char * s);

Corrigé

***************************************************************************Pour ce programme, on considérera comme mot toute suite continue de une ou plusieurs lettres. Un

parcours de la chaîne, avec mémorisation d’état, permet d’écrire la fonction. Lors du parcours de la chaîne,deux états sont possibles :

— on est dans un mot (état MOT)— on n’est pas dans un mot (état NONMOT)

Les transitions d’état sont les suivantes :— si on est dans l’état MOT :

— si on rencontre une lettre : on reste dans l’état MOT— si on rencontre un caractère non-lettre : on entre dans l’état NONMOT

— si on est dans l’état NONMOT— si on rencontre une lettre : on rentre dans l’état MOT— si on rencontre un caractère non-lettre : on reste dans l’état NONMOT

On comptera le nombre de mots en incrémentant une variable à chaque fois que l’on entrera dans l’état MOT.

#include <ctype.h>

#define MOT 1#define NONMOT 0int compte_mots (char * s) {

int etat=NONMOT;int cpt=0;for(;*s!='\0';++s) {

switch(etat) {case MOT :

if (! isalpha(*s))etat=NONMOT;

break;case NONMOT :

if (isalpha(*s)) {etat=MOT;++cpt;

}break;

}}return cpt;

}

***************************************************************************

–23/25–


5.6 Les huit reines (***)

Exercice 32. Écrivez une fonction calculant et affichant toutes les solutions au problème des huitreines.

Huit reines doivent être placées sur un échiquier 8× 8 sans que deux d’entre elles soient en prise, c’està dire sur une même ligne, même colonne ou même diagonale.

Prototype : int huit_reines (void);

Corrigé

***************************************************************************Une solution qui utilise un tableau des hauteurs des reines sur l’échiquier.

/* les huit reines */#include <stdio.h>

#define abs(a) (a>=0?a:-(a))

void affiche(int e[],int n) {int i;printf("\n[%d",e[0]);for (i=1;i<n;++i) {

printf(",%d",e[i]);}printf("]\n");

}

void affiche_complet(int e[],int n) {int l,c;printf("\n\n");for (l=0;l<n;++l) {

for (c=0;c<n;++c) {if (e[c]==l)

printf("X ");else

printf(". ");}printf("\n");

}}

int compatible(int l[], int n) {int i;for (i=n-1;i>=0;--i) {

if ((l[i]==l[n]) || abs(l[i]-l[n])==n-i) {return 0;

}}return 1;

}

int reines(int n) {int ech[n];int col,s;ech[0]=-1;col=0;s=0;while (col>=0) {

++ech[col];

if (ech[col]>=n) {--col;

}else {

if (compatible(ech,col)) {

–24/25–


if (col==n-1) {++s;affiche_complet(ech,n);

}else {

++col;ech[col]=-1;

}}else {}

}}return s;

}

int main() {int i;for (i=1;i<=8;++i) {

printf("echiquier %2dx%2d : %10d solution(s) \n",i,i, reines(i));

}getchar();return 0;

}

/*début de l'affichage

Xechiquier 1x 1 : 1 solutionsechiquier 2x 2 : 0 solutionsechiquier 3x 3 : 0 solutions

. . X .X . . .. . . X. X . .

. X . .

. . . XX . . .. . X .echiquier 4x 4 : 2 solutions

................................

fin de l'affichage. . X . . . . .. . . . . X . .. . . X . . . .. X . . . . . .. . . . . . . X. . . . X . . .. . . . . . X .X . . . . . . .echiquier 8x 8 : 92 solutions

*/

***************************************************************************

–25/25–

Documents

tp3_sol.pdf