{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Texte d'oral de modélisation - Agrégation Option Informatique
1.1  Préparation à l'agrégation - ENS de Rennes, 2016-17
1.2  À propos de ce document
1.3  Question de programmation
1.4  Réponse à l'exercice requis
1.4.1  Une autre approche
1.4.2  Un mauvais exemple
1.4.3  Un bon exemple
1.4.4  Un exemple de Su Doku de taille $9 \\times 9$ au compte juste
1.4.5  Un exemple de Su Doku au comte faux
1.4.6  Un exemple de comte... Dooku ?
1.5  Vérifier les autres contraintes
1.6  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Texte d'oral de modélisation - Agrégation Option Informatique\n", "## Préparation à l'agrégation - ENS de Rennes, 2016-17\n", "- *Date* : 3 avril 2017\n", "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n", "- *Texte*: Annale 2006, \"Sudoku\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## À propos de ce document\n", "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n", "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n", "- L'implémentation sera faite en OCaml, version 4+ :" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.02.3\n" ] }, { "data": { "text/html": [ "
- : int = 0\n",
       "
" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Question de programmation\n", "La question de programmation pour ce texte était donnée au tout début, en page 2 :\n", "\n", "> « Écrire une fonction prenant pour paramètres un entier, $p \\geq 1$, et un tableau carré de côté $p$ (donc de taille $p^2$) d'entiers, $T$, et renvoyant un booléen disant si ce tableau est un carré latin, c'est-à-dire contenant dans chaque ligne et chaque colonne une et une seule fois chaque entier de $1$ à $p$.\n", "\n", "Mathématiquement, si $N_p := \\{1,\\dots,p\\}$, cela donne un prédicat $\\mathrm{estCarreLatin}_p(T)$ sur un tableau $T$ :\n", "$$\n", "\\mathrm{estCarreLatin}_p(T) \\Longleftrightarrow\n", "\\forall i \\in N_p, \\left\\{ T_{i,j} : j \\in N_p \\right\\} = N_p\n", "\\;\\text{and}\\;\n", "\\forall j \\in N_p, \\left\\{ T_{i,j} : i \\in N_p \\right\\} = N_p\n", "$$\n", "\n", "> « En prenant $p = n^2$ on obtient une partie des contraintes d'admissibilité d'une grille complète de Su Doku, mais il reste encore à vérifier la contrainte sur les petits carrés. »\n", "\n", "Pour l'annecdote historique, cette idée de carré latin date vraiment de l'époque romaine antique. On a trouvé à Pompeï des carrés latins de taille $4$ ou $5$ !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Réponse à l'exercice requis\n", "C'est assez rapide :\n", "\n", "1. On écrit une fonction qui permet d'extraire une ligne ou une colonne d'un tableau $T$,\n", "2. On écrit ensuite une fonction qui permet de vérifier si un tableau de $p$ entiers contient exactement $N_p = \\{1, \\dots, p\\}$,\n", "3. Enfin, on vérifie toutes les contraintes." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> *Remarque:* On suppose que tous les tableaux considérés sont :\n", "> - **non vides**\n", "> - et **carrés**\n", "> On ne vérifie pas ces deux points." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val ligne : int -> 'a array array -> int -> 'a array = <fun>\n",
       "
" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val colonne : int -> 'a array array -> int -> 'a array = <fun>\n",
       "
" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let ligne p t i = Array.init p (fun j -> t.(i).(j)) ;;\n", "(* t.(i) marche aussi bien ! *)\n", "\n", "let colonne p t j = Array.init p (fun i -> t.(i).(j)) ;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a besoin de savoir si un tableau de booléens sont tous vrais ou pas.\n", "On peut utiliser la fonction déjà existante, `Array.for_all`, ou bien un `Array.fold_left`, ou une implémentation manuelle." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val tousVrai : bool array -> bool = <fun>\n",
       "
" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let tousVrai tab =\n", " let res = ref true in\n", " for i = 0 to (Array.length tab) - 1 do\n", " res := !res && tab.(i)\n", " done;\n", " !res\n", ";;" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val tousVrai : bool array -> bool = <fun>\n",
       "
" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let tousVrai = Array.fold_left (&&) true;;\n", "(* Array.for_all marche aussi bien ! *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ca permet de facilement vérifier si un tableau `tab` de taille $p$ est exactement $N_p = \\{1,\\dots,p\\}$, en temps linéaire (c'est optimal) en $p$.\n", "\n", "1. On ajoute un test que tous les entiers soient bien entre $1$ et $p$,\n", "2. puis on fait ce test en $\\mathcal{O}(\\# tab)$, en créant est un tableau `estLa` de taille $p$, remplis de `false`. En bouclant sur $t$, on remplit $\\texttt{tab}[i]$ à `true` dans `estLa` (en fait, `tab(i) - 1` car les indices sont entre $0$ et $p-1$). A la fin, si le tableau `estLa` est rempli de `true`, alors on a vu tous les entiers de $N_p$ une et une seule fois." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val estNp : int -> int array -> bool = <fun>\n",
       "
" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let estNp p tab =\n", " if tousVrai (Array.map (fun x -> (1 <= x) && (x <= p)) tab) then begin \n", " let estLa = Array.make p false in\n", " for i = 0 to p - 1 do\n", " estLa.(tab.(i) - 1) <- true\n", " done;\n", " tousVrai estLa\n", " end\n", " else\n", " false\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va adopter une méthode naïve mais simple à écrire :\n", "\n", "- on construit deux tableaux de $p$ booléens,\n", "- on les remplit des contraintes pour les $p$ lignes et les $p$ colonnes,\n", "- et on les vérifie avec `tousVrai`." ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val contraintes_lignes : int -> int array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_lignes p t =\n", " tousVrai (Array.init p (fun i ->\n", " estNp p (ligne p t i)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val contraintes_colonnes : int -> int array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let contraintes_colonnes p t =\n", " tousVrai (Array.init p (fun j ->\n", " estNp p (colonne p t j)\n", " ))\n", ";;" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val carre_latin : int -> int array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let carre_latin p t =\n", " (contraintes_lignes p t) && (contraintes_colonnes p t)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Une autre approche\n", "Plutôt que d'écrire une fonction pour extraire une colonne, et deux fonction qui vérifies les contraintes sur les lignes et les colonnes, on remarque le fait suivant :\n", "\n", "> « Les colonnes de $t$ sont les lignes de $t^T$, la matrice transposée de $t$ ».\n", "\n", "Donc pas besoin de savoir extraire les colonnes, dès qu'on a écrit `contraintes_lignes`, on peut avoir les contraintes sur les colonnes facilement.\n", "\n", "Pour calculer la transposée, une approche simple utilise deux boucles `for` :" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val transpose_for : int -> int array array -> int array array = <fun>\n",
       "
" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let transpose_for p tab =\n", " let tab2 = Array.make_matrix p p 0 in\n", " for i = 0 to p - 1 do\n", " for j = 0 to p - 1 do\n", " tab2.(i).(j) <- tab.(j).(i);\n", " done;\n", " done;\n", " tab2\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut rapidement vérifier sur un exemple,\n", "$$ \\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix}^{T} = \\begin{bmatrix} 1 & 3 \\\\ 2 & 4 \\end{bmatrix}. $$" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : int array array = [|[|1; 3|]; [|2; 4|]|]\n",
       "
" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transpose_for 2 [| [|1; 2|]; [|3; 4|] |];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notez qu'on peut faire mieux, sans boucles `for`, avec deux `Array.init` imbriqués :" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val transpose : int -> 'a array array -> 'a array array = <fun>\n",
       "
" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let transpose p tab =\n", " Array.init p (fun i -> (Array.init p (fun j -> tab.(j).(i))));;" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : int array array = [|[|1; 3|]; [|2; 4|]|]\n",
       "
" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "transpose 2 [| [|1; 2|]; [|3; 4|] |];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et donc :" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val carre_latin2 : int -> int array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let carre_latin2 p t =\n", " (contraintes_lignes p t) && (contraintes_lignes p (transpose p t))\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un mauvais exemple\n", "On va prendre le premier carré de taille $p = 3$ dans le problème de Su Doku donné en figure 1 de l'énoncé.\n", "\n", "\"images/sudoku.png\"" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val p1 : int = 3\n",
       "
" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t1 : int array array = [|[|1; 2; 7|]; [|3; 4; 9|]; [|5; 8; 6|]|]\n",
       "
" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p1 = 3;;\n", "let t1 = [|\n", " [| 1; 2; 7; |];\n", " [| 3; 4; 9; |];\n", " [| 5; 8; 6; |];\n", "|];;" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = false\n",
       "
" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin p1 t1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\implies$ Ce sous-carré de taille $p = 3$ n'est évidemment pas un \"carré latin\" : il contient des chiffres hors de $\\{ 1, 2, 3 \\}$ !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un bon exemple" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut prendre un vrai exemple de taille $p = 3$, qui sera un carré latin." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val p2 : int = 3\n",
       "
" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t2 : int array array = [|[|1; 2; 3|]; [|2; 3; 1|]; [|3; 1; 2|]|]\n",
       "
" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p2 = 3;;\n", "let t2 = [|\n", " [| 1; 2; 3 |];\n", " [| 2; 3; 1 |];\n", " [| 3; 1; 2 |];\n", "|];;" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin p2 t2;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les deux implémentations, la 1ère à base d'extraction de colonnes, la 2ème à base de transposée, donnent bien-sûr le même résultat !" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin2 p2 t2;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de Su Doku de taille $9 \\times 9$ au compte juste\n", "\n", "Avec $p = n^2 = 9$, on reprend l'exemple du texte :\n", "\"images/sudoku.png\"\n", "\n", "Ça va être long un peu à écrire, mais au moins on vérifiera notre fonction sur un vrai exemple." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val p3 : int = 9\n",
       "
" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t3 : int array array =\n",
       "  [|[|1; 2; 7; 4; 6; 3; 9; 8; 5|]; [|3; 4; 9; 8; 7; 5; 2; 6; 1|];\n",
       "    [|5; 8; 6; 2; 9; 1; 4; 3; 7|]; [|7; 6; 5; 9; 4; 2; 3; 1; 8|];\n",
       "    [|8; 3; 4; 7; 1; 6; 5; 2; 9|]; [|9; 1; 2; 5; 3; 8; 7; 4; 6|];\n",
       "    [|2; 7; 8; 6; 5; 4; 1; 9; 3|]; [|4; 5; 3; 1; 8; 9; 6; 7; 2|];\n",
       "    [|6; 9; 1; 3; 2; 7; 8; 5; 4|]|]\n",
       "
" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p3 = 9 ;;\n", "let t3 = [|\n", " [| 1; 2; 7; 4; 6; 3; 9; 8; 5 |];\n", " [| 3; 4; 9; 8; 7; 5; 2; 6; 1 |];\n", " [| 5; 8; 6; 2; 9; 1; 4; 3; 7 |];\n", " [| 7; 6; 5; 9; 4; 2; 3; 1; 8 |];\n", " [| 8; 3; 4; 7; 1; 6; 5; 2; 9 |];\n", " [| 9; 1; 2; 5; 3; 8; 7; 4; 6 |];\n", " [| 2; 7; 8; 6; 5; 4; 1; 9; 3 |];\n", " [| 4; 5; 3; 1; 8; 9; 6; 7; 2 |];\n", " [| 6; 9; 1; 3; 2; 7; 8; 5; 4 |];\n", "|];" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin p3 t3;;" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin2 p3 t3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de Su Doku au *comte* faux\n", "\n", "Avec $p = n^2 = 9$, en modifiant seulement une case du tableau $T$ précédent." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val p4 : int = 9\n",
       "
" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
val t4 : int array array =\n",
       "  [|[|1; 2; 7; 4; 6; 3; 9; 8; 5|]; [|3; 4; 9; 8; 7; 5; 2; 6; 1|];\n",
       "    [|5; 8; 6; 2; 9; 1; 4; 3; 7|]; [|7; 6; 5; 9; 4; 2; 3; 1; 8|];\n",
       "    [|8; 2; 4; 7; 1; 6; 5; 2; 9|]; [|9; 1; 2; 5; 3; 8; 7; 4; 6|];\n",
       "    [|2; 7; 8; 6; 5; 4; 1; 9; 3|]; [|4; 5; 3; 1; 8; 9; 6; 7; 2|];\n",
       "    [|6; 9; 1; 3; 2; 7; 8; 5; 4|]|]\n",
       "
" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p4 = 9 ;;\n", "let t4 = [|\n", " [| 1; 2; 7; 4; 6; 3; 9; 8; 5 |];\n", " [| 3; 4; 9; 8; 7; 5; 2; 6; 1 |];\n", " [| 5; 8; 6; 2; 9; 1; 4; 3; 7 |];\n", " [| 7; 6; 5; 9; 4; 2; 3; 1; 8 |];\n", " [| 8; 2; 4; 7; 1; 6; 5; 2; 9 |]; (* Ligne non valable, 2 est là deux fois !*)\n", " [| 9; 1; 2; 5; 3; 8; 7; 4; 6 |];\n", " [| 2; 7; 8; 6; 5; 4; 1; 9; 3 |];\n", " [| 4; 5; 3; 1; 8; 9; 6; 7; 2 |];\n", " [| 6; 9; 1; 3; 2; 7; 8; 5; 4 |];\n", "|];" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = false\n",
       "
" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin p4 t4;;" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = false\n",
       "
" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "carre_latin2 p4 t4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\implies$ Notre fonction `carre_latin` semble bien marcher." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un exemple de comte... Dooku ?\n", "\n", "[![http://fr.starwars.wikia.com/wiki/Dooku ?](images/dooku.jpg)](http://fr.starwars.wikia.com/wiki/Dooku)\n", "\n", "> *Nan, je déconne*.\n", "> ... Bien-sûr, évitez les blagues pourries le jour de l'oral !\n", "> Mais une bonne blague peut être bien reçue..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Vérifier les autres contraintes\n", "En bonus, on peut écrire une fonction qui vérifie les contraintes sur les petits carrés en plus des contraintes sur les lignes et les colonnes.\n", "\n", "On a déjà tout ce qu'il faut, il suffit d'écrire une fonction qui extraie un petit carré de taille $n \\times n$ ($n = \\sqrt{p}$)." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val racine_carree : int -> int = <fun>\n",
       "
" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let racine_carree i = int_of_float (sqrt (float_of_int i));;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est moins facile à écrire, mais on peut extraire un \"petit carré\" de taille $n \\times n$, pour $t$ de taille $p \\times p$, si $p = n^2$.\n", "Ici, on extraie le $i$ème petit carré en ligne, et le $j$ème petit carré en colonne,\n", "- en jouant avec des modulos et des divisions entières sur $k$ qui sera de $0$ à $p-1$ (`k / n` et `k mod n` font parcourir $0 \\dots n-1$),\n", "- et en jouant avec des multiplications sur `i` et `j`." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val petit_carre : int -> int -> 'a array array -> int -> int -> 'a array =\n",
       "  <fun>\n",
       "
" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let petit_carre p n t i j =\n", " Array.init p (fun k ->\n", " t.(n*i + (k / n)).(n*j + (k mod n))\n", " )\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Bien-sûr, `p` et `n` pourraient ne pas être donnés à la fonction, mais autant se simplifier la vie !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple, avec le tableau `t3` défini plus haut, et $p = 9 = n^2$ pour $n = 3$, on vérifie que les $9$ petits carrés arrivent dans l'ordre :" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val n3 : int = 3\n",
       "
" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let n3 = racine_carree p3;;" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : int array = [|1; 2; 7; 3; 4; 9; 5; 8; 6|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|4; 6; 3; 8; 7; 5; 2; 9; 1|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|9; 8; 5; 2; 6; 1; 4; 3; 7|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|7; 6; 5; 8; 3; 4; 9; 1; 2|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|9; 4; 2; 7; 1; 6; 5; 3; 8|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|3; 1; 8; 5; 2; 9; 7; 4; 6|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|2; 7; 8; 4; 5; 3; 6; 9; 1|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|6; 5; 4; 1; 8; 9; 3; 2; 7|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/html": [ "
- : int array = [|1; 9; 3; 6; 7; 2; 8; 5; 4|]\n",
       "
" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petit_carre p3 n3 t3 0 0;;\n", "petit_carre p3 n3 t3 0 1;;\n", "petit_carre p3 n3 t3 0 2;;\n", "petit_carre p3 n3 t3 1 0;;\n", "petit_carre p3 n3 t3 1 1;;\n", "petit_carre p3 n3 t3 1 2;;\n", "petit_carre p3 n3 t3 2 0;;\n", "petit_carre p3 n3 t3 2 1;;\n", "petit_carre p3 n3 t3 2 2;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Enfin, la contrainte supplémentaire s'écrit exactement comme les deux autres :" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
val petits_carres_sont_latins : int -> int array array -> bool = <fun>\n",
       "
" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let petits_carres_sont_latins p t =\n", " let n = racine_carree p in\n", " (* Par flemme, on créé le tableau entier, qu'on vérifie après *)\n", " let contraintes_petits_carres =\n", " Array.init p (fun i ->\n", " estNp p (petit_carre p n t (i / n) (i mod n) )\n", " )\n", " in\n", " (* Mais on peut mieux faire, avec une boucle while par exemple, on sort dès qu'une contrainte est fausse *)\n", " tousVrai contraintes_petits_carres\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\implies$ Et on peut vérifier que le tableau `t3` satisfait bien cette contrainte :" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = true\n",
       "
" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petits_carres_sont_latins p3 t3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\implies$ Et on peut vérifier que le tableau `t4` ne satisfait pas cette contrainte :" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
- : bool = false\n",
       "
" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "petits_carres_sont_latins p4 t4;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Conclusion\n", "\n", "Voilà pour la question obligatoire de programmation :\n", "\n", "- on a décomposé le problème en sous-fonctions,\n", "- on a essayé d'être fainéant, en réutilisant les sous-fonctions,\n", "- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n", "- on a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte)\n", "\n", "Et on a essayé de faire *un peu plus*, en implémentant la vérification d'une contrainte de plus.\n", "\n", "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml", "language": "ocaml", "name": "iocaml-kernel" }, "language_info": { "name": "ocaml", "version": "4.1.0" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "289px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "704px", "left": "0px", "right": "1223px", "top": "124px", "width": "249px" }, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }