Programmation
Exercices de programmation fonctionnelle en OCaml
Une approche pédagogique par l'algorithmique, la preuve et la complexité
Fabienne Carrier
Pascal Lafourcade
Laurent Mounier
ellipses
I Définitions et notations9
1 Notations et rappels en OCaml9
2 Preuve de terminaison et de correction12
3 Complexité d'une fonction15
4 Notation des fonctions26
II Fonctions sur des entiers27
Exercice 1 Somme des n premiers entiers27
Exercice 2 Somme des n premiers entiers impairs27
Exercice 3 Somme des entiers entre p et q27
Exercice 4 Dernier chiffre de 2n27
Exercice 5 Y a-t-il un 0 dans la représentation binaire d'un entier ?28
Exercice 6 Division euclidienne28
Exercice 7 Factorielle28
Exercice 8 Coefficients binomiaux28
Exercice 9 Puissance d'un entier28
Exercice 10 Puissance d'une fonction28
Exercice 11 Suite de Fibonacci29
Exercice 12 Suite des nombres de Catalan29
Exercice 13 Pgcd de deux entiers29
Exercice 14 Suite de Syracuse29
Solution 1 Somme des n premiers entiers30
Solution 2 Somme des n premiers entiers impairs34
Solution 3 Somme des entiers entre p et q38
Solution 4 Dernier chiffre de 2n43
Solution 5 Y a-t-il un 0 dans la représentation binaire d'un entier ?46
Solution 6 Division euclidienne49
Solution 7 Factorielle51
Solution 8 Coefficients binomiaux53
Solution 9 Puissance d'un entier60
Solution 10 Puissance d'une fonction67
Solution 11 Suite de Fibonacci73
Solution 12 Suite des nombres de Catalan86
Solution 13 Pgcd de deux entiers93
Solution 14 Suite de Syracuse97
III Fonctions sur des listes99
Exercice 15 Longueur d'une liste99
Exercice 16 Somme des entiers d'une liste99
Exercice 17 La fonction fold99
Exercice 18 La fonction map100
Exercice 19 La fonction find100
Exercice 20 Maximum d'une liste non vide d'entiers100
Exercice 21 Nombre d'occurrences d'un élément dans une liste100
Exercice 22 Y a-t-il plus de 0 que de 1 dans une liste ?100
Exercice 23 Concaténer deux listes101
Exercice 24 Renverser une liste101
Exercice 25 Une liste d'entiers est-elle croissante ?101
Exercice 26 Plus longue sous-suite croissante101
Exercice 27 Égalité de séquences101
Exercice 28 Une liste est-elle un palindrome ?101
Exercice 29 Tri par insertion d'une liste102
Exercice 30 Tri par sélection d'une liste102
Exercice 31 Tri rapide d'une liste (Quicksort)102
Exercice 32 Tri fusion d'une liste102
Solution 15 Longueur d'une liste103
Solution 16 Somme des entiers d'une liste105
Solution 17 La fonction fold108
Solution 18 La fonction map115
Solution 19 La fonction find118
Solution 20 Maximum d'une liste non vide d'entiers121
Solution 21 Nombres d'occurrences d'un élément dans une liste125
Solution 22 Y a-t-il plus de 0 que de 1 dans une liste ?130
Solution 23 Concaténer deux listes135
Solution 24 Renverser une liste142
Solution 25 Une liste d'entiers est-elle croissante ?147
Solution 26 Plus longue sous-suite croissante156
Solution 27 Égalité de séquences163
Solution 28 Une liste est-elle un palindrome ?167
Solution 29 Tri par insertion d'une liste175
Solution 30 Tri par sélection d'une liste181
Solution 31 Tri rapide d'une liste (Quicksort)188
Solution 32 Tri fusion d'une liste198
IV Fonctions sur des arbres binaires211
Exercice 35 Nombre de noeuds d'un arbre binaire211
Exercice 36 Hauteur d'un arbre binaire ?211
Exercice 37 Un élément est-il présent dans un arbre binaire ?211
Exercice 38 Nombre de noeuds d'un niveau donné212
Exercice 39 Un arbre binaire est-il équilibré ?212
Exercice 40 Construire le symétrique d'un arbre212
Exercice 41 Ordre supérieur et arbres212
Solution 35 Nombre de noeuds d'un arbre binaire214
Solution 36 Un élément est-il présent dans un arbre binaire ?220
Solution 37 Hauteur d'un arbre binaire ?226
Solution 38 Nombre de noeuds d'un niveau donné231
Solution 39 Un arbre binaire est-il équilibré ?237
Solution 40 Construire le symétrique d'un arbre243
Solution 41 Ordre supérieur et arbres245
Bibliographie257
Index258