vAertissement au lecteurperin/enseignement/main.pdfcette technique n'est pas limitée par le nombre de cases du tableau. Elle n'utilise que 5 ariablev s (au lieu de TMAX cases du tableau)

Exercices fondamentaux de programmation

déclinés selon plusieurs paradigmes de programmation

et illustrés sur des langages usuels

�

�

�

�� programmation impérative en C

� programmation fonctionnelle en Caml

� programmation objet en Java

� programmation logique en Prolog

Université Joseph Fourier, Grenoble

Avertissement au lecteur

Comme pour le piano, avant de devenir un programmeur soliste, il faut travailler sesgammes sur un clavier pour acquérir des ré�exes de bon programmeur.Cet ouvrage est un recueil d'exercices fondamentaux, résolus de manière élégante dansplusieurs modèles de programmation (impératif, fonctionnel, à object, logique) et illustréssur un langage issu de chacun des modèles cités.Les exercices proposés sont simples, classiques. Ils sont incontournables dans le sens oùdans la majorité des problèmes que vous aurez à résoudre la solution sera une combinai-son des solutions aux exercices proposés.En�n, cet ouvrage vous o�re un moyen rapide d'apprendre un langage en étudiant lessolutions proposées par des programmeurs experts. Vous apprendrez ainsi le langage etla meilleure façon de l'utiliser.

Classi�cation des exercices

Chaque exercice est classé selon trois catégorie (l'importance / l'intérêt / la di�culté)

� L'importance : Le nombre de points d'exclamation indique l'importance des exercicespour la formation d'une scienti�que. Les exercices marqués d'un point d'exclamation( ! ) sont indispensables à tous étudiants scienti�ques. Les exercices marqués de ( ! ! )sont destinés aux étudiants qui se destinent à suivre des options informatiques. Toutinformaticien digne de ce nom doit être en mesure de résoudre les exercices jusqu'à( ! ! ! ). Au delà de ( ! ! ! ), il s'agit d'exercices pour ceux qui prétendent au titre d'experts.

� L'intérêt : Le nombre d'étoiles (*) correspond au nombre de notions abordées dansl'exercice. Plus l'exercice comporte d'étoiles, plus vous apprendrez en le faisant.

� La di�culté : Le chi�re romain indique la di�culté de l'exercice : de I à III pour lesdébutants, de IV à VI pour les avancés et jusqu'à X pour les experts.

Table des matières

1 Répétition d'opérations élémentaires 4

1.1 Exercice ( ! / * / I) : addition de deux entiers . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Exercice ( ! / * / I) : multiplication de deux entiers . . . . . . . . . . . . . . . . . . . . 5

1.3 Exercice ( ! / * / I) : Lecture de caractères entrés au clavier . . . . . . . . . . . . . . . 6

1.4 Exercice ( ! / ** / II) : Comparaison d'entiers entrés au clavier . . . . . . . . . . . . . 7

1.5 Exercice ( ! / ** / II) : Lecture d'entiers entrés au clavier . . . . . . . . . . . . . . . . 7

2 Les tableaux 8

2.1 Exercice ( ! / * / I) : a�chage d'un tableau à 1 dimension . . . . . . . . . . . . . . . . 8

2.2 Exercice ( ! / ** / II) : a�chage d'un tableau à 2 dimensions . . . . . . . . . . . . . . 9

2.3 Exercice ( ! / * / II) : maximum d'un tableau . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Exercice ( ! / ** / III) : indice du maximum d'un tableau . . . . . . . . . . . . . . . . 11

3 Les suites récurrentes 12

3.1 Exercice ( ! ! / ** / II) : calcul d'une suite récurrente . . . . . . . . . . . . . . . . . . . 12

3.2 Exercice ( ! / * / I) : calcul de xn, la neme puissance de x . . . . . . . . . . . . . . . . 15

3.3 Exercice ( ! / ** / III) : calcul du maximum d'une suite (ui)i∈N . . . . . . . . . . . . . 18

4 Les séquences 20

4.1 Représentation d'une séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 Exercice ( ! / * / I) : a�chage d'une séquence . . . . . . . . . . . . . . . . . . . . . . . 21

4.3 Exercice ( ! / * / I) : longueur d'une séquence . . . . . . . . . . . . . . . . . . . . . . . 22

4.4 Exercice ( ! / * / I) : insertion d'un élément en �n de séquence . . . . . . . . . . . . . 23

4.5 Exercice ( ! / * / I) : insertion d'un élément en début de séquence . . . . . . . . . . . 24

4.6 Exercice ( ! / * / I) : accès au neme élément d'une séquence. . . . . . . . . . . . . . . . 25

4.7 Exercice ( ! / * / I) : suppression du dernier élément d'une séquence . . . . . . . . . . 26

4.8 Exercice ( ! / * / I) : suppression du premier élément d'une séquence . . . . . . . . . . 27

4.9 Exercice ( ! / * / I) : recherche d'un élément dans une séquence . . . . . . . . . . . . . 28

4.10 Exercice ( ! / * / I) : recherche d'un élément dans une séquence triée . . . . . . . . . . 29

4.11 Exercice ( ! / * / I) : insertion d'un élément dans une séquence triée . . . . . . . . . . 30

4.12 Exercice ( ! / * / I) : copie d'une séquence . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.13 Exercice ( ! / * / I) : renversement d'une séquence . . . . . . . . . . . . . . . . . . . . 32

4.14 Exercice ( ! / * / I) : concaténation de deux séquences . . . . . . . . . . . . . . . . . . 34

4.15 Exercice ( ! / ** / III) : nombre d'occurence d'un élément dans une séquence . . . . . . 35

4.16 Exercice ( ! / ** / IV) : nombre d'occurence de chaque élément d'une séquence . . . . 36

4.17 Exercice ( ! / * / I) : élimination des bégaiements dans une séquence . . . . . . . . . . 38

4.18 Exercice ( ! / * / I) : éliminer les occurences multiples dans une séquence . . . . . . . 39

4.19 Exercice ( ! ! / *** / IV) : transformer chaque éléments d'une séquence . . . . . . . . . 40

4.20 Exercice ( ! / * / I) : produit des éléments d'une séquence . . . . . . . . . . . . . . . . 42

4.21 Exercice ( ! / * / I) : a�cher les éléments qui satisfont une propriété . . . . . . . . . . 43

5 Les ensembles représentés par des séquences 44

5.1 Exercice ( ! / * / I) : union de deux ensembles . . . . . . . . . . . . . . . . . . . . . . 44

5.2 Exercice ( ! / * / I) : intersection de deux ensembles . . . . . . . . . . . . . . . . . . . 45

6 Données non volatiles : lecture/écriture dans un �chier 46

6.1 Exercice ( ! / *** / V) : lecture d'un �chier . . . . . . . . . . . . . . . . . . . . . . . . 46

6.2 Exercice ( ! / *** / V) : suppression des blancs inutiles dans un texte . . . . . . . . . . 47

6.3 Exercice ( ! / *** / V) : écriture dans un �chier . . . . . . . . . . . . . . . . . . . . . . 48

7 E�ectuer un calcul jusqu'à stabilité 49

7.1 Exercice ( ! ! ! / ** / III) : racine carrée d'un nombre . . . . . . . . . . . . . . . . . . . 49

7.2 Exercice ( ! / * / III) : décomposition d'un entier n en base b . . . . . . . . . . . . . . 51

8 Énumération 52

8.1 énumérer les solutions ou les éléments d'un ensemble dénombrable E : fonction N→ E 52

8.2 Exercice ( ! ! / *** / IV) : énumérer les parties d'un ensemble . . . . . . . . . . . . . . 52

8.3 Exercice ( ! ! / *** / V) : numéroter des éléments d'un ensemble dénombrable E : fonctionE → N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

8.4 Exercice ( ! ! ! / ** / III) : énumérer tous les vecteurs d'un produit d'ensembles . . . . . 53

8.4.1 Dé�nition par des équations récurrentes du produit de deux ensembles . . . 53

8.4.2 Dé�nition par des équations récurrentes du produit de n ensembles . . . . . 53

9 Appliquer une transformation jusqu'à stabilité 55

9.1 Exercice ( ! ! ! / ** / III) : recherche de nombres premiers � crible d'Erathostème . . . . 55

9.2 Exercice ( ! ! ! / ** / III) : clôture transitive d'une relation . . . . . . . . . . . . . . . . 55

10 Représentation d'une fonction sur un domaine �ni 57

10.1 par un ensemble de couples (x, y) où y = f(x) . . . . . . . . . . . . . . . . . . . . . 57

1 Répétition d'opérations élémentaires

1.1 Exercice ( ! / * / I) : addition de deux entiers

Écrire l'addition de deux entiers n et m à l'aide des opérations d'incrément (+1), de décrément (-1),du test de nullité (

?

= 0) et de la négation d'une expression logique.

Idée

m + n = (m−1) + (n+1) = ((m−1)−1) + ((n+1)+1) = . . . = (m− 1 . . .− 1)︸︷︷︸0

+ (n + 1 . . . + 1)︸︷︷︸m + n

Principe de l'algorithme

Tant que m n'est pas nul, incrémenter n et décrémenter m.Lorsque m est nul, n est égal à la somme m + n.

• Réalisation en C :

Compétence

◦ Identi�er la nécessité d'utiliser une itération non bornée : boucle while

int add(int m, int n){while( !(m==0) ){m=m-1;n=n+1;

}return n;

}

• Réalisation en Caml :

Dé�nition par des équations récurrentes

E1) add 0 n = nE2) add m n = add (m− 1) (n + 1) si m 6= 0

Réalisation

let rec (add : int -> int -> int) =function m ->function n ->if (m=0) then n (* equation E1 *)

else add (m-1) (n+1) (* equation E2 *);;

1.2 Exercice ( ! / * / I) : multiplication de deux entiers

Écrire la multiplication de deux entiers n et m à l'aide des opérations d'incrément (+1), de décrément(−1), l'addition (+), le test de nullité (

?

= 0) et la négation logique.

Idée

m× n = n + n + . . . + n︸︷︷︸m fois

= n + n + . . . + n︸︷︷︸m−1 fois

= n + (m− 1)× n

Principe de l'algorithme

À partir de 0 (la somme de 0 fois n)Tant que m n'est pas nul, ajouter n au résultat et décrémenter m.Lorsque m est nul, le résultat contient l'addition de m fois la valeur n, c'est bien m× n


int mult(int m, int n){int res ;res = 0;while( !(m==0) ){res = res + n ;m = m-1 ;

};return res;

}



E1) mult 0 n = 0E2) mult m n = n + (mult (m− 1) n) si m 6= 0

Réalisation

let rec (mult : int -> int -> int) =function m ->function n ->if (m=0) then 0 (* equation E1 *)

else n + (mult (m-1) n) (* equation E2 *);;

1.3 Exercice ( ! / * / I) : Lecture de caractères entrés au clavier

Lire des caractères entrés au clavier jusqu'à ce que l'utilisateur entre un point et a�cher les caractèreslus en majuscule.


Compétence

◦ Les instructions scanf et printf◦ Le calcul sur les caractères : les caractères sont représentés par des entiers et ordonnées

dans l'ordre alphabétique.

char c, cmaj ;scanf("%c",&c);while(c != '.'){cmaj = 'A' + (c -'a') ;printf("%c",cmaj);scanf("%c",&c);

};printf(".");

1.4 Exercice ( ! / ** / II) : Comparaison d'entiers entrés au clavier

1.5 Exercice ( ! / ** / II) : Lecture d'entiers entrés au clavier

L'utilisation de tableau est interdite dans cet exercice.

Lire des entiers entrés au clavier jusqu'à ce que l'utilisateur entre un entier qui est la somme desdeux entiers lus précédemment ; le programme a�che alors les trois derniers entiers lus sous la forme�... + ... = ... � et le produit de tous les entiers lus.


Compétence

◦ ...

int n1,n2,n3,prod ;

prod = 1; // le produit d'aucun élément est 1 = l'élément neutre de la multiplication

scanf("%i",&n1);prod = prod * n1 ;

scanf("%i",&n2);prod = prod * n2 ;

scanf("%i",&n3);prod = prod * n3;

while(n3 != n1+n2){n1 = n2;n2 = n3;scanf("%i",&n3);prod = prod * n3;

};printf("arrêt car %i + %i = %i\n", n1, n2, n3);printf("produit = %i", prod);

2 Les tableaux

2.1 Exercice ( ! / * / I) : a�chage d'un tableau à 1 dimension


void afficher_tab(int tab[TMAX]){int i;for(i=0, i<TMAX, i=i+1){printf("%i, ",tab[i]);

};}

2.2 Exercice ( ! / ** / II) : a�chage d'un tableau à 2 dimensions


void afficher_tab(int tab[LMAX][CMAX]){int l,c;for(l=0, l<LMAX, l=l+1){for(c=0, c<CMAX, c=c+1){printf("%i, ",tab[l][c]);

};printf("\n");

};}

2.3 Exercice ( ! / * / II) : maximum d'un tableau


int max_tab(int tab[TMAX]){int i, max ;max = tab[0];for(i=1, i<TMAX, i=i+1){if (tab[i] > max){ max = tab[i]; };

};return max;

};

2.4 Exercice ( ! / ** / III) : indice du maximum d'un tableau

Écrire une fonction indice_max_tab qui retourne l'indice de l'élément de maximal d'un tableau.

Application ( ! / *** / IV) Écrire très simplement la fonction max_tab en utilisant la fonctionindice_max_tab.


Compétence

◦ Distinction entre l'indice d'une case d'un tableau et le contenu de la case

int indice_max_tab(int tab[TMAX]){int i, ind ;ind = 0;for(i=1, i<TMAX, i=i+1){if (tab[i] > tab[ind]){ ind = i; };

};return ind;

};

// Applicationint max_tab(int tab[TMAX]){return tab[indice_max_tab(tab)];

};

3 Les suites récurrentes

3.1 Exercice ( ! ! / ** / II) : calcul d'une suite récurrente

Calculer le neme terme de la suite de Fibonacci (fibi)i∈N dé�nie par les équations de récurrencessuivantes :

fib0 = 1fib1 = 1fibi = fibi−1 + fibi−2

• Réalisation en C : fibonacci.c

Version débutant ( ! ! / ** / II) : en utilisant un tableau pour mémoriser les termes dela suite. Pour appliquer cette technique il faut que n soit inférieur à la taille TMAX du tableau demémorisation des terme de la suite.

int fibonacci(int n){int i, fib[TMAX];

fib[0] = 1;fib[1] = 2;

i=2;while(i!=n){fib[i] = fib[i-1] + fib[i-2];i=i+1;

}; /* i==n */return fib[i];

}

Version standard ( ! / ** / III) : sans utilier de tableau Contrairement à la version précédentecette technique n'est pas limitée par le nombre de cases du tableau. Elle n'utilise que 5 variables (aulieu de TMAX cases du tableau) mais nécessite de faire des transferts de valeurs entre les variablesfib_i, fib_im1, fib_im2.

int fibonacci(int n){int i, fib_0, fib_1, fib_i, fib_im1, fib_im2;

fib_0 = 1;fib_1 = 2;

i=2;fib_im1 = fib_1;fib_im2 = fib_0;

while(i!=n){

fib_i = fib_im1 + fib_im2;i=i+1;fib_im2 = fib_im1;fib_im1 = fib_i;

}; /* i==n */return fib_i;

}

Version élégante et systématique ( ! ! ! ! / *** / X)

Compétence

◦ Utilisation d'un tableau de taille limitée à la distance entre les indices des termes del'équation de récurrence

◦ Utilisation de l'opérateur modulo (%)◦ Calcul sur les indices modulo la taille du tableau

int fibonacci(int n){int i, fib[3];

fib[0] = 1;fib[1] = 2;

i=2;while(i!=n){fib[i%3] = fib[(i-1)%3] + fib[(i-2)%3];i=i+1;

};return fib[i%3];

}


Version naïve ( ! / * / II)


E1) fib 0 = 1E2) fib 1 = 1E3) fib i = (fib (i− 1)) + (fib (i− 2)) si i > 1

Réalisation L'équation E3 comporte deux appels récursifs : le calcul de chaque fibi est faitplusieurs fois. Par exemple pour le calcul de fibn, la réalisation suivante fait 2n−1 fois appel aucalcul de fib1.

let rec (fib : int -> int) =function| 0 -> 1

| 1 -> 1| n -> (fib (n-1)) + (fib (n-2))

;;

Terminaison mesure(fib n

)def

= n diminue strictement à chaque appel récursif.

fib n︸︷︷︸mesure=n

appelle−−−−→>

fib (n-1)︸︷︷︸mesure=n-1

et fib n︸︷︷︸mesure=n


fib (n-2)︸︷︷︸mesure=n-2

Version optimisée ( / ** / IV) : chaque calcul de fibi n'est fait qu'une fois


E1) fib2 0 = (fib0, fib−1) = (1, 0)E2) fib2 1 = (fib1, fib0) = (1, 1)E3) fib2 i = (fibi, fibi−1) = (fibi−1 + fibi−2, fibi−1) si i > 1

sachant que (fibi−1, fibi−2) = fib2 (i− 1)

let rec (fib2 : int -> int * int) =function| 0 -> (1,0)| 1 -> (1,1)| i -> let (fib_im1,fib_im2) = fib2 (i-1) in

let fib_i = fib_im1 + fib_im2in (fib_i,fib_im1)

;;

let (fib : int -> int) =function n ->let (fib_n,fib_nm1) = fib2 nin fib_n

;;

Terminaison mesure(fib2 n

)def

= n diminue strictement à chaque appel récursif :

fib2 i︸︷︷︸mesure=i


fib2 (i-1)︸︷︷︸mesure=i-1

.

3.2 Exercice ( ! / * / I) : calcul de xn, la neme puissance de x

Dé�nir la neme puissance de x comme le neme terme d'une suite récurrente (xi)i∈N. En déduire unalgorithme qui e�ectue le calcul de xn.

Dé�nition standardx0 = 1x1 = xxi = xi−1 × x


version naïve : en utilisant un tableau

int puis(int x, int n){int i, xp[TMAX];xp[0] = 1;xp[1] = x;i=2;while(i!=n){xp[i] = xp[i-1] * x ;i=i+1;

};return xp[n];

}

version standard

int puis(int x, int n){int i, x_0, x_i, x_im1 ;x_0 = 1;i=1;x_i = x;while(i!=n){x_i = x_im1 * x ;i=i+1;x_im1 = x_i ;

};/* i=n */return x_i;

}


Dé�nition par des équations récurrentesE1) puis x 0 = 1E2) puis x n = x× (puis x (n− 1)) si n ≥ 1

Réalisation

let rec (puis : int -> int -> int) =function x ->function| 0 -> 1 (* equation E1 *)| n -> x * (puis (n-1)) (* equation E2 *)

;;

Version expert du cacul de xn

Dé�nition optimisée : changement de suite à chaque fois que le n de xn est pairx0 = 1x1 = x

x2k+1 = x2k × x1

x2k = (x2)k

(x2)k=x′i′

−−−−−−→avec x′=x2

i′=k

x′0 = 1x′1 = x2

x′2k+1 = x′2k × x′1

x′2k = (x′2)k

(x′2)k=x′′i′′

−−−−−−−→avec x′′=x′2

i′′=k

. . .


int puis_optimisée(int x, int n){int res ;res = 1;while(n>=1){if (n%2==0){ /* n pair = 2k : x^2k = (x^2)^k = x'^n' avec x' = x * x et n'= k = n/2 */x = x * x;n = n/2;

}else{ /* n impair */res = res * x ;n = n-1;

};};return res;

}



E1) puis x 0 = 1E2) puis x n = puis x2 k si n = 2kE3) puis x n = x× (puis x 2k) si n = 2k + 1

Réalisation

let rec (puis : int -> int -> int) =function x ->function| 0 -> 1 (* equation E1 *)| n -> if (n mod 2 = 0)

then puis (x*x) (n/2) (* equation E2 *)else x * (puis x (n-1)) (* equation E3 *)

;;

3.3 Exercice ( ! / ** / III) : calcul du maximum d'une suite (ui)i∈N

On considère une suite (ui)i∈N dé�nie par une fonction u de type N → N qui à i associe le termeui. Dé�nir le maximum de la suite (ui)i∈N comme une suite (maxi)i∈N. En déduire un algorithmequi calcul le maximum des n premiers termes de la suite (ui)i∈N.

Application ( / ** / V) La suite (ui)i∈N peut être dé�nie par un tableau U de TMAX valeurs et -1pour tous les termes ui avec i ≥ TMAX

Principe

Dé�nition du max par une suite récurrente :{max0 = u0

maxi = maximum(maxi−1, ui)


Compétence

◦ généralisation de l'algorithme du maximum d'un tableau◦ représentation d'une suite (ui)i∈N par une fonction u qui calcule le ieme terme◦ représentation d'une suite (ui)i∈N par le tableau U des termes U[i]◦ accès à un tableau au moyen d'une fonction

int maximum(int x, int y){if (x>y){ return x; }else{ return y; };

}

/* Déclaration du prototype de la fonction u pour que* la fonction max_suite puisse y faire référence* en attendant la définition de u.*/

int u(int i);

int max_suite(int n){int i, max_i, max_im1 ;i = 0;max_i = u(0);while(i<n){max_i = maximum(max_im1, u(i));i=i+1;max_im1 = max_i;

}; /* i==n */return max_i;

};

/* Application : définition de u, respectant le prototype déclaré */

int U[13] = {1,-3,5,-7,9,-11,-13,17,-19,23,-29,31,-37} ;

int u(int i){if (i<13){ return U[i]; }else{ return -1; }

}


Compétence

◦ ordre supérieur : passage de la fonction u en paramètre de la fonction max

Réalisation

let maximum : int * int -> int =function (x , y) -> if (x>y) then x else y

;;

let rec max_suite : (int -> int) -> int -> int =function u ->function| 0 -> (u 0)| i -> maximum ( u i , max_suite u (i-1) )

;;

let u : int -> int =function| 0 -> 1 | 1 -> ~-3 | 2 -> 5 | 3 -> ~-7 | 4 -> 9 | 5 -> ~-11 | 6 -> ~-13| 7 -> 17 | 8 -> ~-19 | 9 -> 23 | 10 -> ~-29 | 11 -> 31 | 12 -> ~-37 | _ -> ~-1

;;

Terminaison mesure(max_suite u n

)def

= n diminue strictement à chaque appel récursif :

max_suite u i︸︷︷︸mesure=i


max_suite u (i-1)︸︷︷︸mesure=i-1

.

4 Les séquences

4.1 Représentation d'une séquence

Construire une représentation de la séquence des entiers de 0 à 19.


Une séquence de taille connue peut être représentée par un tableau avec un marqueur de �n.

#define FIN -1int seq[20] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,FIN};

La séquence peut être construite automatiquement.

int i, seq[20];

for(i=0,i<20,i=i+1){seq[i]=i;

}seq[i]=FIN;


Une séquence peut être représentée par une liste.

let seq = [0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19] ;;

La séquence peut être construite automatiquement.

let rec (sequence : int -> int -> int list) =function bmin ->function bmax ->if (bmin=bmax)then [bmax]else bmin::(sequence (bmin+1) bmax)

;;

let seq = sequence 0 19 ;;

4.2 Exercice ( ! / * / I) : a�chage d'une séquence

4.3 Exercice ( ! / * / I) : longueur d'une séquence


int longueur(int seq[TMAX]){int i ;i=0;while(seq[i]!=FIN){i=i+1;

}; /* seq[i]==FIN */return i ;

}


let rec (longueur : 'e list -> int) =function| [] -> 0| e::s -> 1 + (longueur s)

;;

Remarque Le fonction longueur est déjà dé�nie. Tapez �include List ; ;� pour voir les fonc-tions prédé�nies dans la biliothèque List.

List.length : 'e list -> int

4.4 Exercice ( ! / * / I) : insertion d'un élément en �n de séquence


void insert_en_queue(int elt, int seq[TMAX]){int i;i=0;while(seq[i]!=FIN){i=i+1;

};seq[i]=elt;seq[i+1]=FIN;

}


let (insert_en_queue : 'elt -> 'elt list -> 'elt list) =function elt ->function seq ->seq @ [elt]

;;

4.5 Exercice ( ! / * / I) : insertion d'un élément en début de séquence


void insert_en_tete(int elt, int seq[TMAX]){int i;i=0;while(seq[i]!=FIN){i=i+1;

};/* seq[i]==FIN */i=i+1;while(i>=1){seq[i]=seq[i-1];i=i-1;

};seq[0]=elt;

}


let (insert_en_tete : 'elt -> 'elt list -> 'elt list) =function elt ->function seq ->elt::seq

;;

4.6 Exercice ( ! / * / I) : accès au neme élément d'une séquence.


int acces(int n, int seq[TMAX]){int i;i=0;while(i<n && seq[i]!=FIN){i=i+1;

};/* si la séquence a moins de n éléments, la fonction acces retourne FIN */return seq[i];

}


type 'elt succes_echec =| SUCCES of 'elt| ECHEC

;;

let rec (acces : int -> 'elt list -> 'elt) =function n ->function| [] -> ECHEC| e::s -> if (n=0)

then SUCCES eelse acces (n-1) s

;;

4.7 Exercice ( ! / * / I) : suppression du dernier élément d'une séquence


int supprimer_dernier(int seq[TMAX]){int i;i=0;while(seq[i]!=FIN){i=i+1;

};/* seq[i]==FIN */if (i!=0){ seq[i-1]=FIN; };

}


let rec (supprimer_dernier : 'elt list -> 'elt list) =function| [] -> []| [e] -> []| e::s -> e::(supprimer_dernier s)

;;

4.8 Exercice ( ! / * / I) : suppression du premier élément d'une séquence


int supprimer_premier(int seq[TMAX]){int i;i=0;while(seq[i]!=FIN){seq[i]=seq[i+1];i=i+1;

};}


let (supprimer_premier : 'elt list -> 'elt list) =function| [] -> []| e::s -> s

;;

4.9 Exercice ( ! / * / I) : recherche d'un élément dans une séquence


int present(int e, int seq[TMAX]){int i;i=0;while(seq[i]!=e && seq[i]!=FIN){i=i+1;

};return (seq[i]==e);

}

• Réalisation en Caml : present.ml


E1) present elt [ ] = falseE2) present elt e :: s = (e = elt) ∨ (present e s)

Réalisation

let rec (present : 'elt -> 'elt list -> bool) =function elt ->function| [] -> false| e::s -> if (e=elt)

then true (* equation E1 *)else present elt s (* equation E2 *)

;;

4.10 Exercice ( ! / * / I) : recherche d'un élément dans une séquence triée


int present_dans_tri(int elt, int seq[TMAX]){int i;i=0;while(elt>seq[i] && seq[i]!=FIN){i=i+1;

};return (elt==seq[i]);

}



E1) présent_dans_trié elt [ ] = falseE2) présent_dans_trié elt e :: s = présent_dans_trié elt s si elt > eE3) présent_dans_trié elt e :: s = (e = elt) si elt ≤ e

Réalisation

let rec (present_dans_trie : 'elt -> 'elt list -> bool) =function elt ->function| [] -> false (* equation E1 *)| e::s -> if (elt>e)

then present_dans_trie elt s (* equation E2 *)else (e=elt) (* equation E3 *)

;;

4.11 Exercice ( ! / * / I) : insertion d'un élément dans une séquence triée


void insert(int elt, int seq[TMAX]){int i;i=0;/* recherche de la position d'insertion */while(elt>=seq[i] && seq[i]!=FIN){i=i+1;

};/* recherche de la position du marqueur de fin */l=i;while(seq[l]!=FIN)l=l+1;

};/* seq[l]==FIN *//* décalage des cases pour faire une place à elt */l=l+1;while(l>i)seq[l]=seq[l-1];l=l-1;

};/* insertion de elt */seq[i]=elt;

}


let (insert : 'elt -> 'elt list -> 'elt list) =function elt ->function| [] -> [e]| e::s -> if (elt>=e)

then e::(insert elt s)else elt::(e::s)

;;

4.12 Exercice ( ! / * / I) : copie d'une séquence


int copier(int seq[TMAX], int copie[TMAX]){int i;i=0;while(seq[i]!=FIN){copie[i]=seq[i];i=i+1;

};/* seq[i]==FIN */copie[i]=seq[i];

}


let copie = seq ;;

4.13 Exercice ( ! / * / I) : renversement d'une séquence


int renverser(int seq[TMAX]){int i, temp, avance, recule;i=0;while(seq[i]!=FIN){i=i+1;

};/* seq[i]==FIN */avance = 0;recule = i-1;while(avance<recule){temp = seq[avance] ;seq[avance] = seq[recule];seq[recule] = temp ;avance = avance+1;recule = recule-1;

};}


version naïve

let rec (renverser : 'elt list -> 'elt list) =function| [] -> []| e::s -> (renverser s)@[e]

;;

version optimisée (niveau expert) Utilisation d'une continuation : plutôt au fur et à mesure desappels récursifs, la fonction renverser_par_reconstruction construit une fonction de constructionde l'inverse de la séquence et �nalement elle applique la fonction construite à la séquence vide.

let rec (renverser_par_reconstruction : ('e list -> 'e list) -> 'e list -> 'e list) =function construire_inverse ->function| [] -> construire_inverse []| e::s -> let

fonction_construire_inverse = (fun seq -> e::(construire_inverse seq))inrenverser_par_reconstruction fonction_construire_inverse s

;;

let (renverser : 'elt list -> 'elt list) =

function seq ->renverser_par_reconstruction (fun [] -> []) seq

;;

4.14 Exercice ( ! / * / I) : concaténation de deux séquences


void concatener(int seqA[TMAX], int seqB[TMAX], int res[TMAX]){int a,b,r;// copie de la séquence seqA dans en début de la séquence resr=0;a=0;while(seqA[a]!=FIN){res[r] = seq[a];a=a+1;r=r+1;

};// copie de la séquence seqB à la suite de la séquence seqAb=0;while(seqB[b]!=FIN){res[r] = seq[b];b=b+1;r=r+1;

};// fin de la séquence resres[r]=FIN;

}


let (concatener : 'e list -> 'e list -> 'e list) =function seqA ->function seqB ->seqA @ seqB

;;

4.15 Exercice ( ! / ** / III) : nombre d'occurence d'un élément dans une

séquence


int nb_occurence_dans(int elt, int seq[TMAX]){int i, occ ;occ=0;i=0;while(seq[i]!=FIN){if (seq[i]==elt) { occ=occ+1; };i=i+1;

};return occ ;

}

• Réalisation en Caml : nb_occurence.ml

let rec (nb_occurence_dans :'e -> 'e list -> int) =function elt ->function| [] -> 0| e::s -> (nb_occurence_dans elt s) + (if (e=elt) then 1 else 0)

;;

Version avancée ( / ** / V)

let (nb_occurence_dans :'e -> 'e list -> int) =function elt ->function seq ->List.length (List.filter (fun e -> e=elt) seq)

;;

4.16 Exercice ( ! / ** / IV) : nombre d'occurence de chaque élément d'une

séquence


void occurences(int seq[TMAX], int occ[ELTMAX]){int e ;for(e=0, e<ELTMAX, e=e+1){occ[e]=0;

};while(seq[i]!=FIN){e = seq[i];occ[e] = occ[e] + 1;i=i+1;

};};

• Réalisation en Caml : occurences.ml

Version 1 ( ! / ** / IV)

let rec (occurences_2 : 'e list -> 'e list -> ('e * int) list) =function seq ->function| [] -> []| e::s -> (e, nb_occurence e seq) :: (occurences_2 seq s)

;;

let (occurences : 'e list -> ('e * int) list) =function seq ->occurences_2 seq seq

;;

Version 2 ( / *** / V)

let rec (occurences : 'e list -> ('e * int) list) =function seq ->List.map (fun e -> (e, nb_occurence e seq) ) seq

;;

Version 3 ( / **** / X)

let rec(construction_de_nb_occurence : 'e list -> ('e -> int) -> 'e list -> ('e -> int)) =function seq ->function nb_occurence ->function

| [] -> nb_occurence| e::s -> let

occ_e = (nb_occurence e)in letocc_e_dans_seq =if (occ_e>0)then occ_eelse (nb_occurence_dans e seq)

in letnouvelle_fonction_nb_occurence =(fun x -> if (x=e)

then occ_e_dans_seqelse (nb_occurence x)

)inconstruction_de_nb_occurence seq nouvelle_fonction_nb_occurence s

;;

let (occurences : 'e list -> ('e -> int)) =function seq ->construction_de_nb_occurence seq (fun x -> 0) seq

;;

(* TESTlet nb_occurence = occurences [0;0;1;0;1;2;0;1;2;3;0;1;2;3;4];;nb_occurence 0;; nb_occurence 1;; nb_occurence 2;; nb_occurence 3;; nb_occurence 4;; nb_occurence 5;;

*)

4.17 Exercice ( ! / * / I) : élimination des bégaiements dans une séquence

4.18 Exercice ( ! / * / I) : éliminer les occurences multiples dans une sé-

quence


int eliminer_occurences_multiples(int seq[TMAX], int res[TMAX]){int i, r;res[0]=FIN;r=0;i=0;while(seq[i]!=FIN){if ( !present(seq[i],res) ){ res[r]=seq[i] ;r=r+1;

};i=i+1;

};res[r]=FIN;

}

• Réalisation en Caml : eliminer_occurences_multiples.ml

4.19 Exercice ( ! ! / *** / IV) : transformer chaque éléments d'une séquence


#define TMAX 100#define EOS '\0'

char transformation(int i){if (i<('Z'-'a')){ return 'a'+ i ; }else{ return '!' ; };

}

void appliquer_a_chaque(int seq_int[TMAX], char seq_char[TMAX]){int s ;s=0;while(seq_int[s]!=FIN){seq_char[s] = transformation(seq_int[s]) ;

};seq_char[s]=EOS;printf("%s",seq_char);

}

int entiers[TMAX] = {0,1,17,0,2,0,3,0,1,17,0,-1} ;char texte[TMAX];

appliquer_a_chaque(entiers,texte);


let transformation : int -> char =function i ->let alphabet =['a';'b';'c';'d';'e';'f';'g';'h';'i';'j';'k';'l';'m';'n';'o';'p';'q';'r';'s';'t';'u';'v';'w';'x';'y';'z';'A';'B';'C';'D';'E';'F';'G';'H';'I';'J';'K';'L';'M';'N';'O';'P';'Q';'R';'S';'T';'U';'V';'W';'X';'Y';'Z']

intry(List.nth alphabet i)

withFailure "nth" -> '!'

;;

let rec appliquer_a_chaque : ('type1 -> 'type2) -> 'type1 list -> 'type2 list =function f ->function

| [] -> []| e::s -> (f e)::(appliquer_a_chaque f s)

;;

appliquer_a_chaque transformation [0;1;17;0;2;0;3;0;1;17;0];;

Remarque La fonction appliquer_a_chaque est déjà dé�nie en Caml : map signi�e appliquer enanglais.

List.map : ('a -> 'b) -> 'a list -> 'b list

La transformation des entiers en caractères existe aussi :

char_of_int : int -> char

Version avancée ( ! ! ! / ** / IV)

List.map char_of_int [0;1;17;0;2;0;3;0;1;17;0];;

4.20 Exercice ( ! / * / I) : produit des éléments d'une séquence

4.21 Exercice ( ! / * / I) : a�cher les éléments qui satisfont une propriété

5 Les ensembles représentés par des séquences

5.1 Exercice ( ! / * / I) : union de deux ensembles


void union(int seqA[TMAX], int seqB[TMAX], int res[TMAX]){int seqAB[TMAX];concatener(seqA,seqB,seqAB);elimination_doublons(seqAB,res);

}


let rec (union : 'e list -> 'e list -> 'e list) =function seqA ->function seqB ->elimination_doublons (seqA @ seqB)

;;

5.2 Exercice ( ! / * / I) : intersection de deux ensembles


int renverser(int seqA[TMAX], int seqB[TMAX], int inter[TMAX]){int i, a;i=0;a=0;while(seqA[a]!=FIN){if (present(seqA[a],seqB)){ inter[i]=seqA[a] ;i=i+1;

};a=a+1;

};inter[a]=FIN;

}


let rec (inter : 'e list -> 'e list -> 'e list) =function seqA ->function seqB ->match seqA with| [] -> []| e::sA -> if (present e seqB)

then e::(inter sA seqB)else (inter sA seqB)

;;

6 Données non volatiles : lecture/écriture dans un �chier

6.1 Exercice ( ! / *** / V) : lecture d'un �chier

6.2 Exercice ( ! / *** / V) : suppression des blancs inutiles dans un texte

6.3 Exercice ( ! / *** / V) : écriture dans un �chier

Écrire dans un �chier la représentation au format html d'une tableau à deux dimensions remplid'entiers.

Notation html Un tableau est délimité par <TABLE options> ... </TABLE>. Une ligne est délimitéepar <TR> ... </TR>. Une colonne est délimitée par </TD> ... </TD>. L'épaisseur des bordures dutableau est indiqué par BORDER=nombre de pixels dans la partie option du tableau.


void generer_colonne_html(int c){ecrire(" <TD>%i</TD>",c);

}

void generer_ligne_html(int ligne[CMAX]){int c;

ecrire("\n<TR>\n");

for(c=0, c<CMAX, c=c+1){generer_colonne_html(ligne[c]);

};

ecrire("\n</TR>");}

void generer_tab_html(int tab[LMAX][CMAX]){int l;

ecrire("<TABLE BORDER=5>");

for(l=0, l<LMAX, l=l+1){generer_ligne_html(tab[l]);

};

ecrire("\n</TABLE>");}

7 E�ectuer un calcul jusqu'à stabilité

7.1 Exercice ( ! ! ! / ** / III) : racine carrée d'un nombre

Le grec Héron d'Alexandrie a proposé un algorithme pour calculer la racine carrée d'un nombre. Ilsu�t de calculer les termes de la suite (ri)i∈N qui converge vers la valeur

√x.

r0 = 1r1 = xri = 1

2(ri−1 + x

ri−1)

Principe

Si ri−1 =√

x alors ri = 12(√

x + x√x) =

√x+

√x

2=√

x.De même tous les termes suivants valent

√x. On dit que la suite se stabilise.

• Réalisation en C : racine_carree.c

#define PRECISION 1000

int stabilite(float r_im1, float r_i){return ( abs(PRECISION * r_i - PRECISION * r_im1) < 1.0);

}

float rac(float x){float r_i, r_im1;int i;i=1;r_im1 = 1;r_i = x;while( !stabilite(r_im1,r_i) ){i=i+1 ;r_im1 = r_i ;r_i = (r_im1 + x/r_im1)/2.0 ;

};printf("%i pas de calcul sont nécessaires pour calculer sqrt(%f) = %f",i,x,r_i);return r_i ;

}

• Réalisation en Caml : racine_carree.ml

let _PRECISION = 1000.0 ;;

let (stabilite : float * float -> bool) =function (r_im1, r_i) ->abs_float ((_PRECISION *. r_i) -. (_PRECISION *. r_im1)) < 1.0

;;

let rec (rac3 : float * float * float -> float) =function (x, r_im1, r_i) ->if (stabilite (r_im1,r_i))then r_ielse rac3 (x, r_i, (r_i +. x /. r_i) /. 2.0 )

;;

let (rac : float -> float) =function x ->let r_0 = 1.0and r_1 = xin rac3 (x, r_0, r_1)

;;

7.2 Exercice ( ! / * / III) : décomposition d'un entier n en base b

Donner l'écriture d'un entier n en base b sur la forme d'une séquence de chi�re.

8 Énumération

8.1 énumérer les solutions ou les éléments d'un ensemble dénombrable

E : fonction N→ E

8.2 Exercice ( ! ! / *** / IV) : énumérer les parties d'un ensemble

Énumérer les parties de l'ensemble {0; 1; 2; 3; 4}.


• Réalisation en Caml : parties.ml


E1) parties { } = {∅}E2) parties e ◦ ens = (parties ens) ∪

(ajouter e à chaque (parties ens)

)E ′

1) ajouter e à chaque { } = { }E ′

2) ajouter e à chaque ens ◦ autres-ens = (e ◦ ens) ◦ (ajouter e à chaque autres-ens)

type 'a ens = 'a list;;

let rec ajoute_element_a_chaque : 'elt -> ('elt ens) ens -> ('elt ens) ens =function e ->function| [] -> [] (* Équation E'1 *)| ens::autres_ens -> (* Équation E'2 *)

(e::ens)::(ajoute_element_a_chaque e autres_ens);;

let rec partie : 'elt ens -> ('elt ens) ens =function| [] -> [[]] (* Équation E1 *)| e::ens -> (* Équation E2 *)

let les_parties_de_ens_sans_e = (partie ens)in les_parties_de_ens_sans_e

@(ajoute_element_a_chaque e les_parties_de_ens_sans_e)

;;

8.3 Exercice ( ! ! / *** / V) : numéroter des éléments d'un ensemble dénom-

brable E : fonction E → N

8.4 Exercice ( ! ! ! / ** / III) : énumérer tous les vecteurs d'un produit d'en-

sembles

On considère trois ensembles A = {1, 2, 3}, B = {vrai, faux}, C = {a, b, c, d}.A�chez tous les vecteurs du produit d'ensembles A×B × C.


int i,b;char c;for(i=1; i<=3; i=i+1){for(b=0; b!=1; b=b+1){for(c='a'; c<='d'; c=c+1){printf("(%i,%i,%c) ",i,b,c);

};};

};

• Réalisation en Caml : produit_des_ensembles.ml

8.4.1 Dé�nition par des équations récurrentes du produit de deux ensembles

E1) { } × V ecteurs = { }E2) (e ◦ ens) × V ecteurs = {(e, x1, . . . , xn) | (x1, . . . , xn) ∈ V ecteurs} ∪ (ens× V ecteurs)

Traduction des équations mathématiques en représentation informatique

E1) produit [ ] V ecteurs = [ ]E2) produit e ◦ ens V ecteurs =

(ajouter e à chaque V ecteurs

)@ (produit ens V ecteurs)

8.4.2 Dé�nition par des équations récurrentes du produit de n ensembles

E ′1) Π { } = {∅}

E ′2) Π {E1, . . . , En} = E1 × E2 × . . .× En = E1 × (E2 × . . .× En) = E1 × Π {E2, . . . , En}

Traduction des équations mathématiques en représentation informatique

E ′1) produit_des_ensembles [ ] = [ [ ] ]

E ′2) produit_des_ensembles ens ◦ autres-ens = produit ens (produit_des_ensembles autres-ens)

Réalisation

type elt =| I of int| B of bool| C of char

;;

let rec produit: elt ensemble -> (elt list) ensemble -> (elt list) ensemble =function ensemble ->function vecteurS ->match ensemble with| [] -> []| e::ens -> (ajouter_element_a_chaque e vecteurS) @ (produit ens vecteurS)

;;

let rec produit_des_ensembles: (elt ensemble) list -> (elt list) ensemble =function| [] -> [[]]| ens::autres_ens -> produit ens (produit_des_ensembles autres_ens)

;;

produit_des_ensembles[ [I 1; I 2; I 3] ; [B true; B false]; [C 'a'; C 'b'; C 'c'; C 'd'] ]

;;

9 Appliquer une transformation jusqu'à stabilité

9.1 Exercice ( ! ! ! / ** / III) : recherche de nombres premiers � crible d'Era-

thostème

9.2 Exercice ( ! ! ! / ** / III) : clôture transitive d'une relation

On considère une relation R représentée par des couples (x, y). On souhaite rendre cette relationtransitive, c'est-à-dire que

si les couples (x, y) et (y, z) sont dans R alors il faut ajouter le couple (x, z).

On dé�nit donc une transformation qui considère tous les x, y, z et ajoute le couple (x, z) si (x, y)et (y, z) sont dans R. On applique cette transformation jusqu'à ce que l'ensemble R des couples soitstable, c'est-à-dire jusqu'au moment où la transformation n'ajoute plus de couple. On a�che alorsla relation R obtenue.

Application relation ancetre.

• Réalisation en C : cloture_transitive.c

Compétence

◦ Représentation d'un ensemble R de couples sous la forme d'un tableau R, de booléens,à 2 dimensions R[x][y]=1 signi�e (x, y) ∈ R et R[x][y]=0 signi�e (x, y) /∈ R

int transformation(int R[EMAX][EMAX]){int x, y, z, nb_modif;nb_modif=0;for(x=0; x<EMAX; x=x+1){for(y=0; y<EMAX; y=y+1){for(z=0; z<EMAX; z=z+1){if (R[x][y]==1 && R[y][z]==1 && R[x][z]==0){ R[x][z] = 1;nb_modif = nb_modif+1;

};};

};};return nb_modif;

}

void rendre_transitive(int R[EMAX][EMAX]){int nb_modif ;nb_modif = transformation(R);while( nb_modif>0 ){nb_modif = transformation(R);

};}


10 Représentation d'une fonction sur un domaine �ni

10.1 par un ensemble de couples (x, y) où y = f(x)

Documents

vAertissement au lecteurperin/enseignement/main.pdfcette technique n'est pas limitée par le nombre de cases du tableau. Elle n'utilise que 5 ariablev s (au lieu de TMAX cases du tableau)