Quelques exercices de programmation

Implémenter deux fonctions min_lst et max_lst dont l’appel sur une liste non vide s’évalue en le min et le max des éléments de cette liste. Sur une liste vide, une exception sera levée. Par exemple min_list [0;1;2;3] s’évalue en 0.

Implémenter une fonction array_iter prenant en entier une fonction à effet de bord ('a -> unit' ) et appliquant cette fonction successivement à tous les éléments d’un tableau passé en argument en commençant au premier élément.

Par exemple array_iter (fun x -> print_int x) [|1;2;3|] affichera 123.

Cette fonction réplique le comportement de la fonction Array.iter du module Array que vous n’utilisez pas dans cet exercice.

Implémentez une fonction is_greater de comparaison stricte de liste s’appuyant sur l’ordre lexicographique (ordre du dictionnaire). Par exemple is_greater [] [1] s’évalue en false, is_greater [1.2] [1.1; 1.5] s’évalue en true et is_greater [1.1] [1.1; 1.5] s’évalue en false.

Implémenter une fonction rev dont l’appel sur une liste s’évalue en cette liste dont l’ordre des éléments a été changé. Par exemple rev [0;1;2;3] s’évalue en [3;2;1;0].

Implémentez une fonction array_mem qui s’évalue à vrai si un tableau passé en argument contient un élément passé en argument. Par exemple array_mem 5 [|1;2;3|] s’évalue en false et array_mem [|3;5;6|] s’évalue en true.

Cette fonction réplique le comportement de la fonction Array.mem du module Array que vous n’utilisez pas dans cet exercice.

Implémentez une fonction base_b qui s’évalue en la liste des coefficients de la décomposition en base \(b\) de son argument \(n\). Les coefficients de poids le plus faible seront en tête de liste. Par exemple, base_b 2 10 s’évalue en [0;1;0;1] car \(10 = 2^1 + 2^3\).

Implémenter une fonction array_rev prenant en entier un tableau array et s’évaluant en un tableau [|a.(n); a.(n-1); ...|] Par exemple array_rev [|3;2;1|] s’évalue en [|1;2;3|].

Implémentez une fonction exp qui prend deux entiers a et n et s’évalue en \(a^n\). La complexité sera en \(O(\log(n))\) et vous n’utiliserez pas de boucle. Par exemple exp 5 3 s’évalue en 125

Implémenter une fonction array_map prenant en entrée une fonction f et un tableau array et s’évaluant en un tableau [|f array.(0); f array.(1); ...|] Par exemple array_map (fun x -> x + x) [|1;2;3|] s’évalue en [|2;4;6|].

Cette fonction réplique le comportement de la fonction Array.map du module Array que vous n’utilisez pas dans cet exercice.

Implémentez une fonction list_length qui s’évalue en la longueur d’une liste passée en argument. Par exemple list_length [0;1;2] s’évalue en 3.

Implémentez une fonction sorted_merge qui fusionne les éléments de deux listes triées dans l’ordre croissant en une seule liste triée.

Par exemple sorted_merge [0;2;3;6] [1;4] s’évalue en [0;1;2;3;4;6].

Implémentez une fonction matrix_product qui réalise le produit de deux matrices représentées par des float array array dont les dimensions conviennent.

Si les dimensions ne conviennent pas, une exception sera levée.

Par exemple matrix_product [|[|1.; 0.|];[|0.; 1.|]|] [|[|5.; 6.|];[|7.; 8.|]|] s’évalue en [|[|5.; 6.|];[|7.; 8.|]|]

Implémenter une fonction list_mem prenant en entrée un élément e et une liste lst et déterminant si e est une élément de lst. Par exemple list_mem 5 [1;2;3] s’évalue en false.

Cette fonction réplique le comportement de la fonction List.mem du module List que vous n’utilisez pas dans cet exercice.

Implémenter une fonction list_map prenant en entrée une fonction f et une liste lst et s’évaluant en une liste des images des éléments de lst par f. Par exemple list_map (fun x -> x + x) [1;2;3] s’évalue en [2;4;6].

Cette fonction réplique le comportement de la fonction List.map du module List que vous n’utilisez pas dans cet exercice.

On considère une liste d’entiers lst et un prédicat sur les entiers p. Implémentez une fonction sum_if qui s’évalue en la somme des éléments de la liste qui vérifient le prédicat. Par exemple sum_if (fun x -> x mod 2 = 0) [1;3;5] s’évalue en 0

Implémentez une fonction min_and_argmin qui s’évalue en un couple du plus petit élément d’une liste et de son indice dans la liste. Dans le cas d’une liste vide, une exception sera levée. Si la liste contient des doublons, min_and_argmin choisira le min avec l’indice le plus faible.

Par exemple min_and_argmin [1;2;5;0;7] s’évalue en (0,3).

Vous n’utiliserez pas de boucle.

Implémentez une fonction zip qui prend en argument deux listes en s’évalue en une liste des couples des éléments de même rang de ces deux listes. Si les listes sont de taille différente, une exception sera levée.

Par exemple zip [1;2;3] [4;5;6] s’évalue en [(1,4);(2,5);(3,6)].

Implémenter une fonction array_inplace_rev prenant en entier un tableau array et inversant l’ordre de ses cases. Par exemple array_inplace_rev [|3;2;1|] modifiera le contenu du tableau en [|1;2;3|].

On considère la suite \(u_n\) définit récursivement pour \(n > 0\) par

• \(u_{2n} = u_n\)
• \(u_{2n+1} = u_{2n-1} + u_{n}\)
• \(u_0 = 1\), \(u_1 = 1\)

Implémentez une fonction u s’évaluant en le terme de rang n de la suite quand on lui passe n en argument. Pour minimiser le temps de calcul nécessaire tout en gardant une consommation mémoire raisonnable vous prendrez soit de mémoïser le calcul des termes nécessaires pour \(u_n\) à l’aide d’un dictionnaire tel qu’implémenté par le module Hashtbl de la bibliothèque standard d’OCaml. Par exemple, \(u_{70} = 87\)

On s’intéresse à des arbres d’arité non bornée, implémentés de la manière suivante:

• Soit une feuille
• Soit un nœud contenant une liste de fils

On suppose que les arbres sont implémentés par le type OCaml suivant:

type tree = Leaf | Node of tree list

Ici, on pourra considérer qu’un nœud qui n’est pas une feuille a au moins un fils, donc la liste associée n’est pas vide. Le nombre de Strahler d’un arbre \(t\), noté $s(t)est défini inductivement de la manière suivante:

• \(s(t) = 1\) si \(t\) est une feuille
• \(s(t)\) est le plus grand nombre de Strahler des enfants de \(t\) si un de ces enfants possède un nombre de Strahler plus grand que tous les autres
• \(s(t)\) est 1 + le plus grand nombre de Strahler des enfants de \(t\) si au moins deux enfants ont un plus grand nombre de Strahler que tous les autres.

Par exemple l’arbre t = Node ([Node ([Leaf; Leaf]); Leaf; Leaf]) a un nombre de Strahler de 2. Implémenter une fonction strahler qui calcule le nombre de Strahler d’un arbre.

Le chiffrement de César consiste modifier le contenu d’un message de manière en décalant chaque lettre d’un nombre de positions fixe dans l’alphabet. Par exemple, pour un décalage de 1, le mot « HAL » devient « IBM ». Implémentez une fonction caesar_encrypt qui chiffre une chaîne de caractère représentant un message à l’aide d’une clé de décalage. Par exemple caesar_encrypt "HAL" 1 s’évalue en "IBM". Attention, il vous est rappelé que les chaînes de caractère en OCaml sont immutables, il n’est pas possible de modifier une chaîne. Il est possible de convertir un caractère c en chaîne via String.make 1 c. Seules les lettres seront modifiées, les autres caractères seront laissés inchangés, et la casse sera conservée. caesar_encrypt "HaL" 1 s’évalue en "IbM".

On s’intéresse au nombre de 0 présents en fin d’écriture décimale de \(n!\). Implémentez une fonction qui compte ces 0. Vous éviterez de passer par le calcul direct de \(n!\) afin de ne pas vous exposer aux dépassent de capacité sur les entiers. Afin de rendre la fonction aussi efficace que possible vous pourrez exploiter la relation \(n! = n × (n-1)!\) et le fait qu’un 0 dans une écriture décimale correspond à l’existence d’un facteur \(10 = 2 × 5\) et vous mémoïserez les calculs intermédiaires.

Implémentez une fonction alternate_split_list qui prend en argument une liste et s’évalue en un couple de liste, la première contenant les éléments de rang pair et la seconde les éléments de rang impair. Vous n’utiliserez pas de boucle dans cette fonction. Par exemple alternate_split_list [1;2;3] s’évaluera en ([1;3], [2])

On considère un polynôme à coefficients float représenté par le tableau de ses coefficients. La case i contient le coefficient de degré i. Implémentez une fonction eval_at_array qui prend ce polynôme et un flottant et évalue ce polynôme en ce flottant.

La complexité sera linéaire en le degré du polynôme.

Par exemple eval_at_array [|5.;6.|] 1. s’évalue en 11.0.

On considère un polynôme à coefficients float représenté par la listes de ses coefficients. Le terme de rang i contient le coefficient de degré i. Implémentez une fonction diff_p_list qui prend ce polynôme et un flottant et s’évalue en la dérivée formelle de ce polynôme.

La complexité sera linéaire en le degré du polynôme.

Par exemple diff_p_list [5.; 6.; 7.] s’évalue en [6.; 14.].

Implémentez une fonction div qui calcule le nombre de diviseurs d’un entier n donné.

Par exemple div 5 s’évalue en 2 (1 et 5).

Dans le cas \(n=0\), div lèvera une exception.

On considère des expression arithmétiques représentées par le type suivant

type expr = Value of int
          | Plus of expr * expr
          | Minus of expr * expr
          | Product of expr * expr
          | Div of expr * expr

Implémentez une fonction eval_expr qui évalue une telle expression. Vous utiliserez un type option pour gérer le cas des expressions dont la valeur n’est pas définie. Par exemple eval_expr (Plus (Value 1, Minus (Value 0, Value 1))) s’évalue en Some 0 et eval_expr (Div (Value 1, Value 0)) s’évalue en None.

Implémentez une fonction exp qui prend deux entiers a et n et s’évalue en \(a^n\). La complexité sera en \(O(\log(n))\) et vous n’utiliserez pas de fonction récursive. Par exemple exp 5 3 s’évalue en 125

On considère une chaîne de caractères ne contenant que des '(' et ')'. Implémentez une fonction is_well_braced vérifiant s’il s’agit ou non d’une expression bien parenthésée. Par exemple is_well_braced "()(())" s’évalue à true, mais is_well_braced ")((())" s’évalue à false. Vous n’utiliserez pas de fonction récursive.

On considère une chaîne de caractères ne contenant que des caractères parmi "()[]{}". Implémentez une fonction is_well_braced_multi vérifiant s’il s’agit ou non d’une expression bien parenthésée. Par exemple is_well_braced_multi "({})[]" s’évalue à true, mais is_well_braced_multi "([)]{}" s’évalue à false. Vous pourrez vous aider du module Stack de la bibliothèque standard OCaml.

On considère une liste d’entiers lst. Implémentez une fonction sum_odd qui s’évalue en la somme des éléments de la liste de rang impair. Par exemple sum_odd [1;3;5] s’évalue en 3

On considère des arbres ternaires implémentés via le type suivant:

type ternary_tree = Leaf | Node of ternary_tree * ternary_tree * ternary_tree

Implémentez une fonction tree_height qui s’évalue en la hauteur d’un tel arbre. Par exemple

tree_height (Node (Leaf, Node (Leaf,Leaf,Leaf), Leaf))

s’évalue en 2.

On considère une liste de liste lst. Implémentez une fonction flatten_lst qui transforme cette liste en une liste de tous les éléments. Par exemple flatten [[1;2];[1;5;6];[1]] s’évalue en [1;2;1;5;6;1]. La complexité sera linéaire en le nombre d’éléments du résultat.

On considère deux vecteurs de même dimension implémentés sous forme de float array. Implémentez une fonction dot qui réalise le produit scalaire de ces deux vecteurs.

Par exemple dot [|1.; 0.|] [|0.; 1.|] s’évalue en 0. car les deux vecteurs sont orthogonaux.

On considère une chaîne de caractère s. Implémentez une fonction split_on_char qui découpe s en plusieurs sous chaînes délimitées par un caractère passé en argument.

Par exemple, split_on_char "this is a sentence " ' ' s’évalue en ["this"; "is"; "a"; "sentence"; ""], le découpage des sous chaînes délimitées par des espaces. Ici le dernier espace de la chaîne a pour conséquence une chaîne vide à la fin de la liste.

Vous pourrez utiliser String.make 1 c qui crée une chaîne de longueur 1 ne contenant que le caractère c.

Implémentez une fonction size_k_split qui découpe une liste en une liste de blocs de termes consécutifs de taille donnée k. Par exemple, size_k_split 3 [0;1;2;3;4;5;6;7] s’évalue en [[0;1;2];[3;4;5][6;7]], le dernier bloc est éventuellement de taille inférieures à k s’il n’y a pas assez de termes.

Implémentez une fonction insertion_sort qui réalise le tri par insertion d’une liste.

Par exemple insertion_sort ['a'; 'c'; 'b'; 'z'; 'a'] s’évalue en ['a'; 'a'; 'b'; 'c'; 'z']. Vous n’utiliserez par de boucle.

Implémenter une fonction list_filter prenant en entrée un prédicat p et une liste lst et filtrant en une liste des éléments de lst vérifiant p. Par exemple list_filter (fun x -> x > 5) [1;7;3;8] s’évalue en [7;8].

Cette fonction réplique le comportement de la fonction List.filter du module List que vous n’utilisez pas dans cet exercice.

Implémenter une fonction list_rev dont l’appel sur une liste s’évalue en cette liste dont l’ordre des éléments a été changé. Par exemple list_rev [0;1;2;3] s’évalue en [3;2;1;0]. Vous n’utiliserez pas de fonction récursive.

On considère un polynôme à coefficients float représenté par la listes de ses coefficients. Le terme de rang i contient le coefficient de degré i. Implémentez une fonction eval_at_list qui prend ce polynôme et un flottant et évalue ce polynôme en ce flottant.

La complexité sera linéaire en le degré du polynôme.

Par exemple eval_at_list [5.;6.] 1. s’évalue en 11.0.

Implémentez une fonction alternate_merge qui fusionne les éléments de deux listes en une seule en alternant un élément d’une liste puis un de la suivante tant que c’est possible.

Par exemple alternate_merge [0;2;4;6] [1;3] s’évalue en [0;1;2;3;4;6]. La première liste étant plus longue, on termine avec uniquement des éléments de celle ci (4 et 6).

On considère une liste lst dont on cherche le deuxième plus grand élément. Implémentez une fonction second_max qui renvoie, s’il existe cet élément. Vous utiliserez un type option pour gérer les cas où cet élément n’existe pas.

Par exemple, second_max [1; 1; 1] s’évalue en None et second_max [2; 23; 6] s’évalue en Some 6.

Implémentez une fonction list_gcd qui calcule le PGCD de tous les éléments d’une liste.

Par exemple list_gcd [12; 18; 27] s’évalue en 3.

On s’intéresse à des fractions implémentées à l’aide d’un enregistrement dont les champs sont numerator et denominator. Implémentez le type fraction correspondant, puis implémentez une fonction make_fraction a b qui s’évalue en la fraction \(\frac{a}{b}\) et implémentez une fonction simplify : fraction -> unit qui modifie en place la fraction de manière à la rendre irréductible.

Par exemple, si on pose let f = make_fraction 6 9 puis qu’on évalue simplify f, on aura une fraction dont le numérateur et le dénominateur sont 2 et 3.

Implémenter une fonction list_iter prenant en entrée une fonction à effet de bord f et une liste lst et appelant la fonction f sur chaque élément de lst dans l’ordre. Par exemple list_map (fun x -> print_int x) [1;2;3] affiche 123.

Cette fonction réplique le comportement de la fonction List.iter du module List que vous n’utilisez pas dans cet exercice.

On considère un tableau trié d’éléments a et un élément de même type e. Implémentez une fonction dicho_search qui recherche l’élément e dans a et renvoie son indice s’il existe. On utilisera un type option pour gérer le cas où cet indice n’existe pas.

Par exemple, dicho_search 7 [|1;2;3;4;5;6|] s’évaluera en None.

On considère un graphe représenté par listes d’adjacences implémentées par le type (int list) array. Implémentez une fonction k_reachable qui détermine la liste des sommets accessibles en exactement k étape à partir d’une liste de sommets initiaux.

Par exemple pour le graphe let g = [|[2;3];[2];[4];[4];[1]|], k_reachable g 2 [0;1] s’évalue en [4], qui est la liste des sommets accessibles à partir des sommets 0 et 1 en exactement 2 étapes dans g.

Implémentez une fonction ctrl_f qui recherche un mot w dans un texte t et renvoie son indice s’il est dans le texte. Vous utiliserez un type option pour gérer le cas où le mot n’est pas dans le texte.

Par exemple ctrl_f "test" "conteste" s’évalue en Some 3.

On s’intéresse à une implémentation des arbres binaires de recherche à l’aide d’un type récursif dont le constructeur pour un arbre vide est nommé Empty et le constructeur pour un noeud est nommé Node et prend un triplet (fils gauche, (couple clé, valeur), fils droit) en paramètre. Implémentez le type récursif abr correspondant, les clés seront des string et les valeurs de int.

Implémentez une fonction abr_search qui recherche une valeur v associée à une clé k dans un ABR t. L’absence de l’élément sera gérée à l’aide d’un type option.

Par exemple =

abr_search "key" (Node (
                      Node (Empty, ("hey", 0), Empty),
                      ("jey",1),
                      (Node (Empty, ("key",2),Empty))
                    )
                 )

s’évaluera en 2 et

abr_search "ley" (Node (
                      Node (Empty, ("hey", 0), Empty),
                      ("jey",1),
                      (Node (Empty, ("key",2),Empty))
                    )
                )

s’évaluera en None.

On considère deux vecteurs de même dimension implémentés sous forme de float list. Implémentez une fonction dot qui réalise le produit scalaire de ces deux vecteurs.

Par exemple dot [1.; 0.] [0.; 1.] s’évalue en 0. car les deux vecteurs sont orthogonaux.

Implémentez une fonction gcd_and_lcm qui s’évalue en le couple du PGCD et PPCM des deux entiers passés en argument.

Par exemple gcd_and_lcm 15 9 s’évalue en (3,45).

On s’intéresse à une implémentation des arbres binaires de recherche à l’aide d’un type récursif dont le constructeur pour un arbre vide est nommé Empty et le constructeur pour un noeud est nommé Node et prend un triplet (fils gauche, (couple clé, valeur), fils droit) en paramètre. Implémentez le type récursif abr correspondant, les clés seront des string et les valeurs de int.

Implémentez une fonction abr_insert qui insère à la bonne place une valeur v associée à une clé k dans un ABR t. Si k est déjà dans l’ABR, on remplacera la valeur associée.

Par exemple

abr_insert "key" 2 (Node (
                        Node (Empty, ("hey", 0), Empty),
                        ("jey",1),
                        Empty))

s’évaluera en:

(Node (
     Node (Empty, ("hey", 0), Empty),
     ("jey",1),
     (Node (Empty, ("key",2),Empty))))

Implémentez une fonction matrix_turn qui prend en argument une matrice carrée et s’évalue en cette matrice tournée d’un quart de tour dans le sens positif.

Par exemple matrix_turn [|[|1;2;3|];[|4;5;6|];[|7;8;9|]|] s’évalue en [|[|3;6;9|];[|2;5;8|];[|1;4;7|]|]

On s’intéresse au problème suivant: étant donné une liste lst d’entiers positifs et un entier positifs n, est-il possible de trouver un ensemble d’éléments de lst dont la somme est n ? Implémentez une fonction subset_sum qui renvoie la liste des éléments de lst qui somment à n si elle existe. Vous utiliserez un type option pour gérez le cas où une telle liste n’existe pas.

Par exemple subset_sum 6 [1;2;3;4;5] s’évalue en Some [2;4] (même si on pourrait aussi avoir Some [1;5]).

Quelle est la complexité d’une telle fonction par rapport au nombre d’éléments de la liste ? Comment pourrait-on améliorer cette complexité ?

On considère une chaîne de caractères constituée uniquement de lettre et d’espaces. Implémentez une fonction search_largest_word qui s’évalue en la position de début et de fin du mot le plus long de cette chaîne.

Par exemple search_largest_word "ceci est une phrase vide" s’évalue en (13,18).

Implémentez une fonction is_palindrome qui s’évalue en true si la chaîne passée en argument est un palindrome et false autrement. Les espaces seront ignorés.

Par exemple is_palindrome "ab ce cba" s’évalue en true.