{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 2 - Programmation pour la préparation à l'agrégation maths option info\n",
"- En OCaml."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"The OCaml toplevel, version 4.04.2\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"Sys.command \"ocaml -version\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Listes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 1 : `taille`"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille : 'a list -> int = \n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec taille (liste : 'a list) : int =\n",
" match liste with\n",
" | [] -> 0\n",
" | _ :: q -> (taille q) + 1\n",
";;\n",
"\n",
"taille [];;\n",
"taille [1; 2; 3];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pas sûr qu'elle soit récursive terminale, alors que celle là oui :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille : 'a list -> int = \n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let taille (liste : 'a list) : int =\n",
" let rec aux acc = function\n",
" | [] -> acc\n",
" | _ :: q -> aux (acc + 1) q\n",
" in\n",
" aux 0 liste\n",
";;\n",
"\n",
"taille [];;\n",
"taille [1; 2; 3];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Solution plus ésotérique :"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille : '_a list -> int = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let taille = List.fold_left (fun acc _ -> acc + 1) 0;;\n",
"\n",
"taille [];;\n",
"taille [1; 2; 3];;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"List.length [];;\n",
"List.length [1; 2; 3];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 2 : `concat`"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val concatene : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 4]\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec concatene (liste1 : 'a list) (liste2 : 'a list) : 'a list =\n",
" match liste1 with\n",
" | [] -> liste2\n",
" | h :: q -> h :: (concatene q liste2)\n",
";;\n",
"\n",
"concatene [1; 2] [3; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Autre approche, moins simple mais de même complexité en $\\mathcal{O}(n)$."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val miroir : 'a list -> 'a list = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let miroir (liste : 'a list) : 'a list =\n",
" let rec aux acc = function\n",
" | [] -> acc\n",
" | h :: q -> aux (h :: acc) q\n",
" in aux [] liste\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val concatene : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let concatene (liste1 : 'a list) (liste2 : 'a list) : 'a list =\n",
" let rec aux acc l1 l2 =\n",
" match l1 with\n",
" | [] when l2 = [] -> acc\n",
" | [] -> aux acc l2 []\n",
" | h :: q -> aux (h :: acc) q l2\n",
" in\n",
" miroir (aux [] liste1 liste2)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 4]\n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"concatene [1; 2] [3; 4];;"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 4]\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"List.append [1; 2] [3; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 3 : `appartient`"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val appartient : 'a -> 'a list -> bool = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val appartient2 : 'a -> 'a list -> bool = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec appartient x = function\n",
" | [] -> false\n",
" | h :: _ when h = x -> true\n",
" | _ :: q -> appartient x q\n",
";;\n",
"\n",
"\n",
"let rec appartient2 x = function\n",
" | [] -> false\n",
" | h :: q -> (h = x) || (appartient2 x q)\n",
";;\n",
"\n",
"appartient 1 [];;\n",
"appartient 1 [1];;\n",
"appartient 1 [1; 2; 3];;\n",
"appartient 4 [1; 2; 3];;\n",
"\n",
"appartient2 1 [];;\n",
"appartient2 1 [1];;\n",
"appartient2 1 [1; 2; 3];;\n",
"appartient2 4 [1; 2; 3];;"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"List.mem 1 [];;\n",
"List.mem 1 [1];;\n",
"List.mem 1 [1; 2; 3];;\n",
"List.mem 4 [1; 2; 3];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 4 : `miroir`"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val miroir : 'a list -> 'a list = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let miroir (liste : 'a list) : 'a list =\n",
" let rec aux acc = function\n",
" | [] -> acc\n",
" | h :: q -> aux (h :: acc) q\n",
" in aux [] liste\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [11; 7; 5; 3; 2]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [11; 7; 5; 3; 2]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"miroir [2; 3; 5; 7; 11];;\n",
"\n",
"List.rev [2; 3; 5; 7; 11];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 5 : `alterne`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val alterne : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let alterne (liste1 : 'a list) (liste2 : 'a list) : 'a list =\n",
" let rec aux acc l1 l2 =\n",
" match (l1, l2) with\n",
" | [], [] -> acc\n",
" | [], ll2 -> acc @ ll2\n",
" | ll1, [] -> acc @ ll1\n",
" | h1 :: q1, h2 :: q2 -> aux (h1 :: h2 :: acc) q1 q2\n",
" in List.rev (aux [] liste1 liste2)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 1; 4; 3; 6; 5]\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"alterne [1; 3; 5] [2; 4; 6];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La complexité est linéaire en $\\mathcal{O}(\\max(|\\text{liste 1}|, |\\text{liste 2}|)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Mais on manque souvent la version la plus simple :"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val alterne : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec alterne (l1 : 'a list) (l2 : 'a list) : 'a list =\n",
" match l1 with\n",
" | [] -> l2\n",
" | t::q -> t::(alterne l2 q)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 6 : `nb_occurrences`"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nb_occurrences : 'a -> 'a list -> int = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val nb_occurrences : 'a -> 'a list -> int = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 1\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 2\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* O(n) en temps, et en espace d'appel : pas récursif terminal ! *)\n",
"let rec nb_occurrences (x : 'a) (liste : 'a list) : int =\n",
" match liste with\n",
" | [] -> 0\n",
" | h :: q when h = x -> (nb_occurrences x q) + 1\n",
" | _ :: q -> nb_occurrences x q\n",
";;\n",
"\n",
"(* O(n) en temps, et O(1) en espace d'appel : récursif terminal ! *)\n",
"let nb_occurrences (x : 'a) (liste : 'a list) : int =\n",
" let rec aux acc x l =\n",
" match l with\n",
" | [] -> acc\n",
" | h :: q when h = x -> aux (acc + 1) x q\n",
" | _ :: q -> aux acc x q\n",
" in aux 0 x liste\n",
";;\n",
"\n",
"nb_occurrences 0 [1; 2; 3; 4];;\n",
"nb_occurrences 2 [1; 2; 3; 4];;\n",
"nb_occurrences 2 [1; 2; 2; 3; 3; 4];;\n",
"nb_occurrences 5 [1; 2; 3; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Autre approche, avec un `List.fold_left` bien placé :"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nb_occurrences : 'a -> 'a list -> int = \n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 1\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 2\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nb_occurrences (x : 'a) : 'a list -> int =\n",
" List.fold_left (fun acc y -> if x = y then (acc + 1) else acc) 0\n",
";;\n",
"\n",
"nb_occurrences 0 [1; 2; 3; 4];;\n",
"nb_occurrences 2 [1; 2; 3; 4];;\n",
"nb_occurrences 2 [1; 2; 2; 3; 3; 4];;\n",
"nb_occurrences 5 [1; 2; 3; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 7 : `pairs`\n",
"\n",
"C'est un filtrage :"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val pairs : int list -> int list = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let pairs = List.filter (fun x -> x mod 2 = 0);;"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 4; 6]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [2; 4; 6; 100000]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [2; 4; 6; 100000000000]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [2; 4; 6; 1000000000000000000]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pairs [1; 2; 3; 4; 5; 6];;\n",
"pairs [1; 2; 3; 4; 5; 6; 7; 100000];;\n",
"pairs [1; 2; 3; 4; 5; 6; 7; 100000000000];;\n",
"pairs [1; 2; 3; 4; 5; 6; 7; 1000000000000000000];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 8 : `range`"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val range : int -> int list = \n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let range (n : int) : int list =\n",
" let rec aux acc = function\n",
" | 0 -> acc\n",
" | n -> aux (n :: acc) (n - 1)\n",
" in aux [] n\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list =\n",
"[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;\n",
" 22; 23; 24; 25; 26; 27; 28; 29; 30]\n"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"range 30;;"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val entiers : int -> int -> int list = \n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Vous avez parfois eu du mal à construire la liste des entiers de a à b\n",
" ca serait bon de savoir le faire car ca peut vous donner des exemples\n",
" d'entree pour vos algos *)\n",
"\n",
"let entiers a b =\n",
" let rec construit x =\n",
" if x > b\n",
" then []\n",
" else x::(construit (x + 1))\n",
" in construit a\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val premiers_entiers : int -> int list = \n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [4; 5; 6; 7; 8; 9; 10]\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [0; 1; 2; 3; 4; 5; 6; 7]\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let premiers_entiers = entiers 0;; (* Bel exemple de currification *)\n",
"\n",
"entiers 4 10;;\n",
"premiers_entiers 7;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 9 : `premiers`\n",
"Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtration.\n",
"Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtration (filtrage ? *pattern matching*)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val racine : int -> int = \n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 4\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let racine (n : int) : int =\n",
" int_of_float (floor (sqrt (float_of_int n)))\n",
";;\n",
"\n",
"racine 17;;"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val estDivisible : int -> int -> bool = \n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let estDivisible (a : int) (b : int) : bool =\n",
" (a mod b) = 0\n",
";;\n",
"\n",
"estDivisible 10 2;;\n",
"estDivisible 10 6;;\n",
"estDivisible 10 5;;"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val range2 : int -> int -> int -> int list = \n"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let range2 (debut : int) (fin : int) (taille : int) : int list =\n",
" let rec aux acc = function\n",
" | n when n > fin -> acc\n",
" | n -> aux (n :: acc) (n + taille)\n",
" in\n",
" List.rev (aux [] debut)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 5; 8; 11]\n"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"range2 2 12 3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne (rappel : pas de `break` dans les boucles `for` en OCaml...)."
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val estPremier : int -> bool = \n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let estPremier (n : int) : bool =\n",
" List.fold_left (fun b k -> b && (not (estDivisible n k))) true (range2 2 (racine n) 1)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val premiers : int -> int list = \n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let premiers (n : int) : int list =\n",
" List.filter estPremier (range2 2 n 1)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 3; 5; 7]\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"premiers 10;;"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : int list =\n",
"[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;\n",
" 73; 79; 83; 89; 97]\n"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"premiers 100;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Quelques tris par comparaison"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On fera les tris en ordre croissant."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"text/plain": [
"val test : int list = [3; 1; 8; 4; 5; 6; 1; 2]\n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let test = [3; 1; 8; 4; 5; 6; 1; 2];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 10 : Tri insertion"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insere : 'a -> 'a list -> 'a list = \n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insere (x : 'a) : 'a list -> 'a list = function\n",
" | [] -> [x]\n",
" | t :: q ->\n",
" if x <= t then\n",
" x :: t :: q\n",
" else\n",
" t :: (insere x q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tri_insertion : 'a list -> 'a list = \n"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec tri_insertion : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | t :: q -> insere t (tri_insertion q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 1; 2; 3; 4; 5; 6; 8]\n"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_insertion test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Complexité en temps $\\mathcal{O}(n^2)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 11 : Tri insertion générique"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insere2 : ('a -> 'a -> bool) -> 'a -> 'a list -> 'a list = \n"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insere2 (ordre : 'a -> 'a -> bool) (x : 'a) : 'a list -> 'a list = function\n",
" | [] -> [x]\n",
" | t :: q ->\n",
" if ordre x t then\n",
" x :: t :: q\n",
" else\n",
" t :: (insere2 ordre x q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tri_insertion2 : ('a -> 'a -> bool) -> 'a list -> 'a list = \n"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec tri_insertion2 (ordre : 'a -> 'a -> bool) : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | t :: q -> insere2 ordre t (tri_insertion2 ordre q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val ordre_croissant : 'a -> 'a -> bool = \n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let ordre_croissant a b = a <= b;;"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 1; 2; 3; 4; 5; 6; 8]\n"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_insertion2 ordre_croissant test;;"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val ordre_decroissant : 'a -> 'a -> bool = \n"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let ordre_decroissant = (>=);;"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [8; 6; 5; 4; 3; 2; 1; 1]\n"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_insertion2 ordre_decroissant test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 12 : Tri selection"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val selectionne_min : 'a list -> 'a * 'a list = \n"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let selectionne_min (l : 'a list) : ('a * 'a list) =\n",
" let rec cherche_min min autres = function\n",
" | [] -> (min, autres)\n",
" | t :: q ->\n",
" if t < min then\n",
" cherche_min t (min :: autres) q\n",
" else\n",
" cherche_min min (t :: autres) q\n",
" in\n",
" match l with\n",
" | [] -> failwith \"Selectionne_min sur liste vide\"\n",
" | t :: q -> cherche_min t [] q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int list = (1, [2; 1; 6; 5; 4; 8; 3])\n"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"selectionne_min test;;"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tri_selection : 'a list -> 'a list = \n"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec tri_selection : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | l ->\n",
" let (min, autres) = selectionne_min l in\n",
" min :: (tri_selection autres)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 1; 2; 3; 4; 5; 6; 8]\n"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_selection test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Complexité en temps : $\\mathcal{O}(n^2)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercices 13, 14, 15 : Tri fusion"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print_list : int list -> unit = \n"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print_list (liste : int list) : unit =\n",
" print_string \"[\";\n",
" List.iter (fun i -> print_int i; print_string \"; \" ) liste;\n",
" print_endline \"]\";\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [3; 1; 8; 4; 5; 6; 1; 2]\n"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3; 1; 8; 4; 5; 6; 1; 2; ]\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test;;\n",
"print_list test;;"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val separe : 'a list -> 'a list * 'a list = \n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list * int list = ([3; 8; 5; 1], [1; 4; 6; 2])\n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec separe : 'a list -> ('a list * 'a list) = function\n",
" | [] -> ([], [])\n",
" | [x] -> ([x], [])\n",
" | x :: y :: q ->\n",
" (* n'est pas stable : on perturbe l'ordre des éléments en entrée *)\n",
" let (a, b) = separe q\n",
" in (x::a, y::b)\n",
";;\n",
"\n",
"separe test;;"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val fusion : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 3; 7; 8]\n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec fusion (l1 : 'a list) (l2 : 'a list) : 'a list =\n",
" match (l1, l2) with\n",
" | (l, []) | ([], l) -> l (* syntaxe concise pour deux cas identiques *)\n",
" | (h1::q1, h2::q2) ->\n",
" if h1 <= h2 then\n",
" h1 :: (fusion q1 l2)\n",
" else\n",
" h2 :: (fusion l1 q2)\n",
";;\n",
"\n",
"fusion [1; 3; 7] [2; 3; 8];;"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tri_fusion : 'a list -> 'a list = \n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* O(n log(n)) en temps et O(n) en mémoire *)\n",
"let rec tri_fusion : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | [x] -> [x] (* ATTENTION A NE PAS OUBLIER CE CAS *)\n",
" | l ->\n",
" let a, b = separe l in\n",
" fusion (tri_fusion a) (tri_fusion b)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 1; 2; 3; 4; 5; 6; 8]\n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tri_fusion test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Complexité en temps $\\mathcal{O}(n \\log n)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Comparaisons des tris"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Random.self_init();;"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 83\n"
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Random.int 100;;"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val random_tableau : int -> int array = \n"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val random_list : int -> int list = \n"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let random_tableau (n : int) : int array =\n",
" Array.init n (fun _ -> -1000 + (Random.int 2000))\n",
";;\n",
"\n",
"let random_list (n : int) : int list =\n",
" Array.to_list (random_tableau n)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array = [|260; 306; 965; -846; -458; -318; 873; -824; 662; 160|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"random_tableau 10;;"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val timeit : int -> ('a -> 'b) -> (unit -> 'a) -> float = \n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let timeit (nbrepetitions : int) (f : 'a -> 'b) (lazy_x : unit -> 'a) : float =\n",
" let debut = Sys.time () in\n",
" for _ = 1 to nbrepetitions do\n",
" ignore (f (lazy_x ()));\n",
" done;\n",
" let fin = Sys.time () in\n",
" (fin -. debut) /. (float_of_int nbrepetitions)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float * float * float =\n",
"(2.05600000000000234e-05, 2.2860000000000103e-05, 2.17200000000000733e-05)\n"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nbrepetitions = 100 in\n",
"let n = 10 in\n",
"let temps_insertion = timeit nbrepetitions tri_insertion (fun () -> random_list n) in\n",
"let temps_selection = timeit nbrepetitions tri_selection (fun () -> random_list n) in\n",
"let temps_fusion = timeit nbrepetitions tri_fusion (fun () -> random_list n) in\n",
"(temps_insertion, temps_selection, temps_fusion);;"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float * float * float =\n",
"(9.59599999999999283e-05, 0.000149540000000000225, 5.95600000000001684e-05)\n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nbrepetitions = 100 in\n",
"let n = 100 in\n",
"let temps_insertion = timeit nbrepetitions tri_insertion (fun () -> random_list n) in\n",
"let temps_selection = timeit nbrepetitions tri_selection (fun () -> random_list n) in\n",
"let temps_fusion = timeit nbrepetitions tri_fusion (fun () -> random_list n) in\n",
"(temps_insertion, temps_selection, temps_fusion);;"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float * float * float =\n",
"(0.0066230299999999985, 0.038065859999999993, 0.000916589999999999354)\n"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nbrepetitions = 100 in\n",
"let n = 1000 in\n",
"let temps_insertion = timeit nbrepetitions tri_insertion (fun () -> random_list n) in\n",
"let temps_selection = timeit nbrepetitions tri_selection (fun () -> random_list n) in\n",
"let temps_fusion = timeit nbrepetitions tri_fusion (fun () -> random_list n) in\n",
"(temps_insertion, temps_selection, temps_fusion);;"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float * float * float =\n",
"(0.873678000000012389, 4.58273399999998787, 0.0211730000000045493)\n"
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nbrepetitions = 1 in\n",
"let n = 10000 in\n",
"let temps_insertion = timeit nbrepetitions tri_insertion (fun () -> random_list n) in\n",
"let temps_selection = timeit nbrepetitions tri_selection (fun () -> random_list n) in\n",
"let temps_fusion = timeit nbrepetitions tri_fusion (fun () -> random_list n) in\n",
"(temps_insertion, temps_selection, temps_fusion);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On a pu vérifier **empiriquement** que les complexités des tris par insertion et sélection sont quadratiques (multiplier $n$ par $10$ multiplie le temps par en gros $10^2$), et que le tri fusion est quasiment linéaire (multiplier $n$ par $10$ multiplie le temps par en gros $10$)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Une petite question de culture camelistique :"
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"File \"[92]\", line 1, characters 23-24:\n",
"Warning 27: unused variable y.\n"
]
},
{
"data": {
"text/plain": [
"- : 'a -> 'b -> 'a = \n"
]
},
"execution_count": 92,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function x -> function y -> x;;"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : 'a -> 'b -> 'a = \n"
]
},
"execution_count": 93,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"File \"[93]\", line 1, characters 6-7:\n",
"Warning 27: unused variable y.\n"
]
}
],
"source": [
"fun x y -> x;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Listes : l'ordre supérieur\n",
"\n",
"Je ne corrige pas les questions qui étaient traitées dans le TP1."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 16 : `applique`"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val applique : ('a -> 'b) -> 'a list -> 'b list = \n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Temps O(n) pire des cas, et O(n) mémoire *)\n",
"let rec applique f = function\n",
" | [] -> []\n",
" | h :: q -> (f h) :: (applique f q)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 17"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val premiers_carres_parfaits : int -> int list = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let premiers_carres_parfaits (n : int) : int list =\n",
" applique (fun x -> x * x) (entiers 1 n)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100; 121; 144]\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"premiers_carres_parfaits 12;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 18 : `itere`"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val itere : ('a -> unit) -> 'a list -> unit = \n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec itere (f : 'a -> unit) = function\n",
" | [] -> ()\n",
" | h :: q -> begin\n",
" f h;\n",
" itere f q\n",
" end\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 19"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val f : int -> unit = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf\n",
"\n",
"let f x = print \"%i\\n\" x;;"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val affiche_liste_entiers : int list -> unit = \n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Debut\n",
"1\n",
"2\n",
"4\n",
"5\n",
"Fin\n"
]
}
],
"source": [
"let affiche_liste_entiers (liste : int list) =\n",
" print \"Debut\\n\";\n",
" itere (print \"%i\\n\") liste;\n",
" print \"Fin\\n\";\n",
" flush_all ();\n",
";;\n",
"\n",
"affiche_liste_entiers [1; 2; 4; 5];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 20 : `qqsoit` et `ilexiste`"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val qqsoit : ('a -> bool) -> 'a list -> bool = \n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Temps O(n) pire cas, et O(1) mémoire car récursif terminal *)\n",
"let rec qqsoit (pred : 'a -> bool) = function\n",
" | [] -> true (* piege ! *)\n",
" | h :: q -> (pred h) && (qqsoit pred q)\n",
" (* le && n'évalue pas le deuxième si le premier argument est false\n",
" donc ceci est efficace et récursif terminal.\n",
" *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val ilexiste : ('a -> bool) -> 'a list -> bool = \n"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec ilexiste (pred : 'a -> bool) = function\n",
" | [] -> false\n",
" | h :: q -> (pred h) || (ilexiste pred q)\n",
" (* le || n'évalue pas le deuxième si le premier argument est true\n",
" donc ceci est efficace et récursif terminal.\n",
" *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"qqsoit (fun x -> (x mod 2) = 0) [1; 2; 3; 4; 5];;\n",
"\n",
"ilexiste (fun x -> (x mod 2) = 0) [1; 2; 3; 4; 5];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 21 : `appartient` version 2"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val appartient : 'a -> 'a list -> bool = \n"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val appartient : 'a -> 'a list -> bool = \n"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let appartient x = ilexiste (fun y -> x = y);;\n",
"\n",
"let appartient x = ilexiste ((=) x);; (* syntaxe simplifiée par curification *)"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val toutes_egales : 'a -> 'a list -> bool = \n"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let toutes_egales x = qqsoit ((=) x);;"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"appartient 1 [1; 2; 3];;\n",
"appartient 5 [1; 2; 3];;\n",
"\n",
"toutes_egales 1 [1; 2; 3];;\n",
"toutes_egales 2 [2; 2; 2];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 22 : `filtre`"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val filtre : ('a -> bool) -> 'a list -> 'a list = \n"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec filtre (pred : 'a -> bool) : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | h :: q when pred h -> h :: (filtre pred q)\n",
" | _ :: q -> filtre pred q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 4]\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [1; 3; 5]\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [1; 3; 5]\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"filtre (fun x -> (x mod 2) = 0) [1; 2; 3; 4; 5];;\n",
"\n",
"filtre (fun x -> (x mod 2) != 0) [1; 2; 3; 4; 5];;\n",
"filtre (fun x -> (x mod 2) <> 0) [1; 2; 3; 4; 5];; (* syntaxe non conseillée *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 23\n",
"Je vous laisse trouver pour `premiers`."
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val pairs : int list -> int list = \n"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val impairs : int list -> int list = \n"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let pairs = filtre (fun x -> (x mod 2) = 0);;\n",
"let impairs = filtre (fun x -> (x mod 2) != 0);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 24 : `reduit`"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val reduit : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = \n"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec reduit (tr : 'a -> 'b -> 'a) (acc : 'a) (liste : 'b list) : 'a =\n",
" match liste with\n",
" | [] -> acc\n",
" | h :: q -> reduit tr (tr acc h) q\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Très pratique pour calculer des sommes, notamment."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 25 : `somme`, `produit`"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val somme : int list -> int = \n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 15\n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 15\n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let somme = reduit (+) 0;;\n",
"\n",
"somme [1; 2; 3; 4; 5];;\n",
"List.fold_left (+) 0 [1; 2; 3; 4; 5];;"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val produit : int list -> int = \n"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 120\n"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 120\n"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let produit = reduit ( * ) 1;;\n",
"\n",
"produit [1; 2; 3; 4; 5];;\n",
"List.fold_left ( * ) 1 [1; 2; 3; 4; 5];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 26 : `miroir` version 2"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val miroir : '_a list -> '_a list = \n"
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let miroir = reduit (fun a b -> b :: a) [];;"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [11; 7; 5; 3; 2]\n"
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [11; 7; 5; 3; 2]\n"
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"miroir [2; 3; 5; 7; 11];;\n",
"\n",
"List.rev [2; 3; 5; 7; 11];;"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [
{
"ename": "error",
"evalue": "error",
"output_type": "error",
"traceback": [
"\u001b[31mFile \"[77]\", line 1, characters 8-10:\nError: This expression has type float but an expression was expected of type\n int\n\u001b[0m"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001bM\u001bM\u001bM\u001bM\u001bM# miroir [\u001b[4m2.\u001b[24m; 3.; 5.; 7.; 11.];;\n",
"\u001b[24m\n",
"\n",
"\n",
"\n"
]
}
],
"source": [
"miroir [2.; 3.; 5.; 7.; 11.];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Arbres"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 27"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a arbre_bin0 =\n",
" Feuille0 of 'a\n",
" | Noeud0 of 'a arbre_bin0 * 'a * 'a arbre_bin0\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type 'a arbre_bin0 = Feuille0 of 'a | Noeud0 of ('a arbre_bin0) * 'a * ('a arbre_bin0);;"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_complet_entier : int -> int arbre_bin0 = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int arbre_bin0 =\n",
"Noeud0 (Noeud0 (Feuille0 0, 2, Feuille0 0), 4,\n",
" Noeud0 (Feuille0 0, 2, Feuille0 0))\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec arbre_complet_entier (n : int) : int arbre_bin0 =\n",
" match n with\n",
" | n when n < 2 -> Feuille0 0\n",
" | n -> Noeud0((arbre_complet_entier (n / 2)), n, (arbre_complet_entier (n / 2)))\n",
";;\n",
"\n",
"arbre_complet_entier 4;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Autre variante, plus simple :"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type arbre_bin = Feuille | Noeud of arbre_bin * arbre_bin\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type arbre_bin = Feuille | Noeud of arbre_bin * arbre_bin;;"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_test : arbre_bin =\n",
" Noeud (Noeud (Noeud (Feuille, Feuille), Feuille), Feuille)\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let arbre_test = Noeud (Noeud (Noeud (Feuille, Feuille), Feuille), Feuille);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 28"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compte le nombre de feuilles et de sommets."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille : arbre_bin -> int = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec taille : arbre_bin -> int = function\n",
" | Feuille -> 1\n",
" | Noeud(x, y) -> 1 + (taille x) + (taille y)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 7\n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"taille arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 29"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val hauteur : arbre_bin -> int = \n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec hauteur : arbre_bin -> int = function\n",
" | Feuille -> 0\n",
" | Noeud(x, y) -> 1 + (max (hauteur x) (hauteur y)) (* peut etre plus simple *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hauteur arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 30"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Bonus."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Parcours d'arbres binaires"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 31"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type element_parcours = F | N\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type parcours = element_parcours list\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type element_parcours = F | N;;\n",
"\n",
"type parcours = element_parcours list;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 32 : Parcours naifs (complexité quadratique)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_prefixe : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [N; N; N; F; F; F; F]\n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec parcours_prefixe : arbre_bin -> element_parcours list = function\n",
" | Feuille -> [F]\n",
" | Noeud (g, d) -> [N] @ (parcours_prefixe g) @ (parcours_prefixe d)\n",
";;\n",
"\n",
"parcours_prefixe arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_postfixe : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [F; F; N; F; N; F; N]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec parcours_postfixe : arbre_bin -> element_parcours list = function\n",
" | Feuille -> [F]\n",
" | Noeud(g, d) -> (parcours_postfixe g) @ (parcours_postfixe d) @ [N]\n",
";;\n",
"\n",
"parcours_postfixe arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_infixe : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [F; N; F; N; F; N; F]\n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec parcours_infixe : arbre_bin -> element_parcours list = function\n",
" | Feuille -> [F]\n",
" | Noeud(g, d) -> (parcours_infixe g) @ [N] @ (parcours_infixe d)\n",
";;\n",
"\n",
"parcours_infixe arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pourquoi ont-ils une complexité quadratique ? La concaténation (`@`) ne se fait pas en temps constant mais linéaire dans la taille de la première liste."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 33 : Parcours linéaires\n",
"\n",
"On ajoute une fonction auxiliaire et un argument `vus` qui est une liste qui stocke les élements observés dans l'ordre du parcours"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_prefixe2 : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [N; N; N; F; F; F; F]\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parcours_prefixe2 a =\n",
" let rec parcours vus = function\n",
" | Feuille -> F :: vus\n",
" | Noeud(g, d) -> parcours (parcours (N :: vus) g) d\n",
" in List.rev (parcours [] a)\n",
";;\n",
"\n",
"parcours_prefixe2 arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_postfixe2 : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [F; F; N; F; N; F; N]\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parcours_postfixe2 a =\n",
" let rec parcours vus = function\n",
" | Feuille -> F :: vus\n",
" | Noeud(g, d) -> N :: (parcours (parcours vus g) d)\n",
" in List.rev (parcours [] a)\n",
";;\n",
"\n",
"parcours_postfixe2 arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_infixe2 : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [F; N; F; N; F; N; F]\n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parcours_infixe2 a =\n",
" let rec parcours vus = function\n",
" | Feuille -> F :: vus\n",
" | Noeud(g, d) -> parcours (N :: (parcours vus g)) d\n",
" in List.rev (parcours [] a)\n",
";;\n",
"\n",
"parcours_infixe2 arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 34 : parcours en largeur et en profondeur"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_largeur : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [N; N; F; N; F; F; F]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parcours_largeur a =\n",
" let file = Queue.create () in\n",
" (* fonction avec effet de bord sur la file *)\n",
" let rec parcours () =\n",
" if Queue.is_empty file\n",
" then []\n",
" else match Queue.pop file with\n",
" | Feuille -> F :: (parcours ())\n",
" | Noeud(g, d) -> begin\n",
" Queue.push g file;\n",
" Queue.push d file;\n",
" N :: (parcours ())\n",
" end\n",
" in\n",
" Queue.push a file;\n",
" parcours ()\n",
";;\n",
"\n",
"parcours_largeur arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"En remplaçant la file par une pile (`Stack`), on obtient le parcours en profondeur, avec la même complexité."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parcours_profondeur : arbre_bin -> element_parcours list = \n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : element_parcours list = [N; F; N; F; N; F; F]\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parcours_profondeur a =\n",
" let file = Stack.create () in\n",
" (* fonction avec effet de bord sur la file *)\n",
" let rec parcours () =\n",
" if Stack.is_empty file\n",
" then []\n",
" else match Stack.pop file with\n",
" | Feuille -> F :: (parcours ())\n",
" | Noeud(g, d) -> begin\n",
" Stack.push g file;\n",
" Stack.push d file;\n",
" N :: (parcours ())\n",
" end\n",
" in\n",
" Stack.push a file;\n",
" parcours ()\n",
";;\n",
"\n",
"parcours_profondeur arbre_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 35 et fin"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val test_prefixe : element_parcours list = [N; N; N; F; F; F; F]\n"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Reconstruction depuis le parcours prefixe *)\n",
"\n",
"let test_prefixe = parcours_prefixe2 arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val reconstruit_prefixe : element_parcours list -> arbre_bin = \n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_bin = Noeud (Noeud (Noeud (Feuille, Feuille), Feuille), Feuille)\n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
},
{
"ename": "error",
"evalue": "error",
"output_type": "error",
"traceback": [
"\u001b[31mException: Failure \"parcours invalide\".\nRaised at file \"pervasives.ml\", line 32, characters 22-33\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m"
]
}
],
"source": [
"(* L'idée de cette solution est la suivante :\n",
" j'aimerais une fonction récursive qui fasse le travail;\n",
" le problème c'est que si on prend un parcours prefixe, soit il commence\n",
" par F et l'arbre doit être une feuille; soit il est de la forme N::q\n",
" où q n'est plus un parcours prefixe mais la concaténation de DEUX parcours\n",
" prefixe, on ne peut donc plus appeler la fonction sur q.\n",
" On va donc écrire une fonction qui prend une liste qui contient plusieurs\n",
" parcours concaténé et qui renvoie l'arbre correspondant au premier parcours\n",
" et ce qui n'a pas été utilisé : *)\n",
"\n",
"let reconstruit_prefixe parcours =\n",
" let rec reconstruit = function\n",
" | F :: p -> (Feuille, p)\n",
" | N :: p ->\n",
" let (g, q) = reconstruit p in\n",
" let (d, r) = reconstruit q in\n",
" (Noeud(g, d), r)\n",
" | [] -> failwith \"pacours invalide\"\n",
" in\n",
" match reconstruit parcours with\n",
" | (a, []) -> a\n",
" | _ -> failwith \"parcours invalide\"\n",
";;\n",
"\n",
"reconstruit_prefixe test_prefixe;;\n",
"reconstruit_prefixe (N :: F :: F :: test_prefixe);; (* échoue *)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val largeur_test : element_parcours list = [N; N; F; N; F; F; F]\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Reconstruction depuis le parcours en largeur *)\n",
"\n",
"(* Ce n'est pas évident quand on ne connait pas. L'idée est de se servir d'une file\n",
" pour stocker les arbres qu'on reconstruit peu à peu depuis les feuilles. La file\n",
" permet de récupérer les bons sous-arbres quand on rencontre un noeud *)\n",
"\n",
"let largeur_test = parcours_largeur arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val reconstruit_largeur : element_parcours list -> arbre_bin = \n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_bin = Noeud (Noeud (Noeud (Feuille, Feuille), Feuille), Feuille)\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let reconstruit_largeur parcours =\n",
" let file = Queue.create () in\n",
" (* Fonction avec effets de bord *)\n",
" let lire_element = function\n",
" | F -> Queue.push Feuille file\n",
" | N ->\n",
" let d = Queue.pop file in\n",
" let g = Queue.pop file in\n",
" Queue.push (Noeud(g, d)) file\n",
" in\n",
" List.iter lire_element (List.rev parcours);\n",
" if Queue.length file = 1 then\n",
" Queue.pop file\n",
" else\n",
" failwith \"parcours invalide\"\n",
";;\n",
"\n",
"reconstruit_largeur largeur_test;;"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val reconstruit_prefixe2 : element_parcours list -> arbre_bin = \n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_bin = Noeud (Noeud (Noeud (Feuille, Feuille), Feuille), Feuille)\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Le même algorithme (enfin presque, modulo interversion de g et d)\n",
" avec une pile donne une autre version de la reconstruction du parcours prefixe *)\n",
"\n",
"let reconstruit_prefixe2 parcours =\n",
" let pile = Stack.create () in\n",
" let lire_element = function\n",
" | F -> Stack.push Feuille pile\n",
" | N ->\n",
" let g = Stack.pop pile in\n",
" let d = Stack.pop pile in\n",
" Stack.push (Noeud(g, d)) pile\n",
" in\n",
" List.iter lire_element (List.rev parcours);\n",
" if Stack.length pile = 1 then\n",
" Stack.pop pile\n",
" else\n",
" failwith \"parcours invalide\"\n",
";;\n",
"\n",
"reconstruit_prefixe2 test_prefixe;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Conclusion\n",
"\n",
"Fin. À la séance prochaine."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "OCaml 4.04.2",
"language": "OCaml",
"name": "ocaml-jupyter"
},
"language_info": {
"codemirror_mode": "text/x-ocaml",
"file_extension": ".ml",
"mimetype": "text/x-ocaml",
"name": "OCaml",
"nbconverter_exporter": null,
"pygments_lexer": "OCaml",
"version": "4.04.2"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "11px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_position": {
"height": "523px",
"left": "0px",
"right": "1026px",
"top": "116px",
"width": "254px"
},
"toc_section_display": "block",
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}