{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Ce fichier est un notebook Python.\n", "\n", "Il comporte deux types de cellules :\n", "\n", "* les cellules d'édition dans lesquelles vous pouvez saisir du texte éventuellement enrichi de mises en formes ou de liens hypertextes avec la syntaxe du langage HTML simplifié qui s'appelle Markdown. Voir http://daringfireball.net/projects/markdown/ pour la syntaxe de Markdown.\n", "\n", "* les cellules de code où l'on peut saisir du code Python3 puis le faire exécuter avec la combinaison de touches `CTRL + RETURN`\n", "\n", "Une cellule peut être éditée de deux façons différentes :\n", "\n", "* en mode _commande_ lorsqu'on clique sur sa marge gauche qui est surlignée alors en bleu, on peut alors :\n", "\n", " - changer le type de la cellule en appuyant sur `m` pour passer en cellule Markdown ou sur `y` pour passer en cellule de code\n", " \n", " - insérer une cellule juste au-dessus en appuyant sur `a`\n", " \n", " - insérer une cellule juste en-dessous en appuyant sur `b`\n", " \n", " - couper la cellule en appuyant sur `x` etc ...\n", " \n", "* en mode _édition_ lorsqu'on clique sur l'intérieur de la cellule.\n", "\n", "L'aide complète sur les raccourcis claviers est accessible depuis le bouton `Help` dans la barre d'outils ci-dessus.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Outils pour l'affichage\n", "\n" ] }, { "cell_type": "code", "execution_count": 193, "metadata": {}, "outputs": [], "source": [ "from PIL import Image\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from copy import deepcopy\n", "\n", "def dimensions(pix):\n", " \"\"\"Retourne les dimensions (Largeur, Hauteur) d'une matrice\n", " de pixels\"\"\"\n", " return len(pix[0]), len(pix) \n", "\n", "\n", "def laby_to_image(pix_source, mode = '1', fichier='image.png', res=1):\n", " \"\"\"Convertit en image une matrice de pixels pix \n", " de dimensions (ligne, colonnes)=(nline, ncol)\n", " en représentant sur l'écran chaque case de pix\n", " par un carré de coté resolution pixels.\n", " Le mode de l'image peut être :\n", " '1' : binaire 0 ou 1\n", " 'L' : niveaux de gris entre 0 et 255\n", " 'RGB' : triplet de valeurs (Rouge, Vert, Bleu) entre 0 et 255\n", " \"\"\"\n", " #on force la conversion en type np.uint8 si pix est un tableau numpy\n", " pix = deepcopy(pix_source)\n", " if isinstance(pix, np.ndarray):\n", " pix = pix.astype(np.uint8)\n", " #précondition 1 : list doit être une matrice de pixels\n", " precondition1 = isinstance(pix, (list, np.ndarray)) \\\n", " and len(pix) > 0 \\\n", " and all(isinstance(pix[k], (list, np.ndarray)) \\\n", " and len(pix[k]) == len(pix[0]) \\\n", " for k in range(len(pix)))\n", " assert precondition1, \"Il faut passer en paramètre une matrice de pixels\"\n", " #dimensions de la matrice de pixels\n", " largeur_pix, hauteur_pix = dimensions(pix)\n", " #transformations des pixels : 0,2,3 -> 1 et 1 -> 0\n", " for i in range(hauteur_pix):\n", " for j in range(largeur_pix):\n", " if pix[i][j] in [0, 2,3]:\n", " pix[i][j] = 1\n", " else:\n", " pix[i][j] = 0\n", " #préconditions sur la matrice de pixels pour respecter les contraintes du mode de l'image \n", " precondition2 = mode == '1' and \\\n", " all(isinstance(pix[y][x], (int, np.uint8)) and 0 <= pix[y][x] <= 1 \\\n", " for y in range(hauteur_pix) for x in range(largeur_pix))\n", " precondition3 = mode == 'L' and \\\n", " all(isinstance(pix[y][x], (int, np.uint8)) and 0 <= pix[y][x] <= 255 \\\n", " for y in range(hauteur_pix) for x in range(largeur_pix))\n", " precondition4 = mode == 'RGB' and \\\n", " all(isinstance(pix[y][x], (list, np.ndarray)) \\\n", " and len(pix[y][x]) == 3 \\\n", " and all(isinstance(pix[y][x][k], (int, np.uint8)) \\\n", " and 0 <= pix[y][x][k] <= 255 \\\n", " for k in range(3)) \\\n", " for y in range(hauteur_pix) for x in range(largeur_pix))\n", " assert precondition2 or precondition3 or precondition4, \"matrice de pixels et mode incompatibles !\" \n", " #dimensions de la matrice de pixels\n", " hauteur_newpix, largeur_newpix = res * hauteur_pix, res * largeur_pix\n", " #copie de pix sous forme de tableau numpy agrandi d'un coefficient res \n", " if mode != 'RGB':\n", " newpix = np.zeros((hauteur_newpix, largeur_newpix), dtype='uint8')\n", " else:\n", " newpix = np.zeros((hauteur_newpix, largeur_newpix, 3), dtype='uint8')\n", " #initialsation des blocs de taille res * res de newpix\n", " #avec des 0 si pix[i][j] == 0 et 1 sinon\n", " for y in range(hauteur_newpix):\n", " for x in range(largeur_newpix):\n", " ypix = y // res\n", " xpix = x // res\n", " newpix[y][x] = pix[ypix][xpix] \n", " if mode != 'RGB':\n", " #création d'un objet image PIL en mode binaire (pixel de valeur 0 ou 1)\n", " im = Image.new(mode, (largeur_newpix, hauteur_newpix)) #Image.new(mode, (Largeur, Hauteur)) \n", " #on remplit l'image avec les valeurs de newpix\n", " im.putdata(newpix.flatten())\n", " else:\n", " im = Image.fromarray(newpix)\n", " #enregistrement de l'image sur le disque\n", " im.save(fichier)\n", " #affichage de l'image\n", " #plt.axis('off') #to disable xticks and yticks\n", " #cas des images binaires \n", " if mode == '1':\n", " plt.imshow(newpix,cmap=plt.cm.gray, vmin= 0, vmax = 1)\n", " # cas des images en niveaux de gris\n", " elif mode == 'L':\n", " plt.imshow(newpix,cmap=plt.cm.gray, vmin= 0, vmax = 255)\n", " #cas des images RGB\n", " else:\n", " plt.imshow(newpix)\n", " \n", "def image_to_laby(fichier):\n", " #ouverture de l'image avec PIL\n", " im = Image.open(fichier)\n", " #conversion de l'image en matrice de pixels / tableau numpy\n", " pix = np.array(im, dtype = np.uint8)\n", " #conversion de la matrice de pixels en liste Python\n", " pix = pix.tolist()\n", " return pix\n", "\n", "def laby_vide(ncol, nlig, mode):\n", " \"\"\"Retourne une matrice de pixels de n lignes et m colonnes\n", " représentant une image noire dans le mode d'image choisi\"\"\"\n", " assert mode in ['1', 'L', 'RGB'], \"mode doit appartenir à ['1', 'L', 'RGB']\"\n", " if mode in ['1', 'L']:\n", " return [[0 for x in range(ncol)] for y in range(nlig)]\n", " else: \n", " return [[[0,0,0] for x in range(ncol)] for y in range(nlig)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![laby](../exo4_laby.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les labyrinthes : " ] }, { "cell_type": "code", "execution_count": 194, "metadata": {}, "outputs": [], "source": [ "lab1 = [ [1,1,1,1,1,0,0,0,0,0,1],\n", " [1,0,0,0,1,0,1,0,1,0,1],\n", " [1,0,1,0,1,0,1,0,1,0,1],\n", " [1,0,1,0,1,0,1,0,1,0,1],\n", " [1,0,1,0,1,0,1,0,1,0,1],\n", " [2,0,1,0,0,0,1,0,1,0,3],\n", " [1,1,1,1,1,1,1,0,1,0,1],\n", " [1,0,1,0,1,0,1,1,1,0,1],\n", " [1,0,0,0,1,0,0,0,1,0,1],\n", " [1,0,1,1,1,0,1,0,0,0,1],\n", " [1,0,0,0,0,0,1,1,0,1,1] \n", " ]" ] }, { "cell_type": "code", "execution_count": 195, "metadata": {}, "outputs": [], "source": [ "lab2 = [[1, 1, 1, 1, 1, 1, 1],\n", "[1, 0, 0, 0, 0, 0, 1],\n", "[1, 1, 1, 1, 1, 0, 1],\n", "[1, 0, 1, 0, 0, 0, 1],\n", "[1, 0, 1, 0, 1, 0, 1],\n", "[1, 0, 0, 0, 1, 0, 1],\n", "[1, 1, 1, 1, 1, 3, 1]]" ] }, { "cell_type": "code", "execution_count": 196, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP8AAAD8CAYAAAC4nHJkAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAACzFJREFUeJzt3V+opAd5x/Hvr7sG3aioSNu4G00CwT8IbdyDREOLJAqxCcaLFiIoIoW9qTVKi8TeeNsLEb0owrKJFZQEWUMbghiLCl415OzGYjZHa4g2WbOalLYq3sTg48UZ69mT/TPOvDPve/b5fmDZcyaz7zyZs99935n3z6SqkNTPH4w9gKRxGL/UlPFLTRm/1JTxS00Zv9SU8UtNGb/UlPFLTe1f54Ml8XDCiTh8+PDYI2jmxIkTgy6vqjLP/bLOw3uNfzo8rHs6krlandu88bvZLzVl/FJTxi81ZfxSU8YvNbVU/EluTvL9JI8nuXOooSSt3sK7+pLsA/4TeBdwGngYeF9VPXaBP+P+pYlwV9907MVdfW8FHq+qJ6rqOeBe4LYllidpjZaJ/yDw1I7vT89uO0uSI0k2k2wu8ViSBrbM4b3n2rR4wbZkVR0FjoKb/dKULLPmPw1cueP7Q8DTy40jaV2Wif9h4NokVye5DLgduH+YsSSt2sKb/VX1fJIPAw8C+4C7q+rUYJNJWinP6mvKXX3TsRd39Unaw4xfasr4paaMX2pqrdfwG1qnN62GflNoaCt402rQ5Q0536Xy9841v9SU8UtNGb/UlPFLTRm/1JTxS00Zv9SU8UtNGb/UlPFLTRm/1JTxS00Zv9SU8UtNGb/UlPFLTRm/1JTxS00Zv9TUnr6G39C8zps6cc0vNWX8UlPGLzVl/FJTxi81tXD8Sa5M8q0kW0lOJbljyMEkrVYW3SWV5Argiqo6meRlwAngvVX12AX+zKD7vzp9pFOnj8OCac835dkAqmquBS685q+qM1V1cvb1L4At4OCiy5O0XoO85k9yFXAd8NAQy5O0eksf4ZfkpcBXgI9W1c/P8d+PAEeWfRxJw1r4NT9AkhcBDwAPVtWn57i/r/kX1Ok1NUx7vinPBmt4zZ/tie8CtuYJX9K0LPOa/wbgA8CNSb4z+/UXA80lacWW2uz/vR/Mzf6FddqshmnPN+XZYA2b/ZL2NuOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pqaXjT7IvySNJHhhiIEnrMcSa/w5ga4DlSFqjpeJPcgi4BTg2zDiS1mXZNf9ngI8Dvz7fHZIcSbKZZHPJx5I0oIXjT3Ir8ExVnbjQ/arqaFVtVNXGoo8laXjLrPlvAN6T5EfAvcCNSb44yFSSVi5VtfxCkncAf19Vt17kfss/2A5DzL5TksGWNeXZwPmWMeXZAKpqrgW6n19qapA1/9wP5pp/YZ3WrDDt+aY8G7jml3QRxi81ZfxSU8YvNbV/nQ92+PBhNjc90G8R63xjVus15M92Y2P+Y+lc80tNGb/UlPFLTRm/1JTxS00Zv9SU8UtNGb/UlPFLTRm/1JTxS00Zv9SU8UtNGb/UlPFLTRm/1JTxS00Zv9SU8UtN7ekP7dCla8ofjDHl2cAP7ZB0EcYvNWX8UlPGLzVl/FJTS8Wf5BVJjif5XpKtJG8bajBJq7Xsx3V9FvhaVf1lksuAAwPMJGkNFt7Pn+TlwH8A19ScC3E/v+Y15X3pU54N1rOf/xrgWeDzSR5JcizJ5UssT9IaLRP/fuAtwOeq6jrgl8Cdu++U5EiSzSR+PK80Icts9v8x8O9VddXs+z8D7qyqWy7wZ9zs11ymvGk95dlgDZv9VfUT4Kkkr5/ddBPw2KLLk7ReS53Yk+RPgWPAZcATwIeq6n8vcH/X/JrLlNeuU54N5l/ze1afJmnKgU15NvCsPkkXYfxSU8YvNWX8UlPGLzW17Ik9o5ryu65Tng2mP9/Qy9MLueaXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmtrT1/Ab2jo/vehSM/XnzmsCvpBrfqkp45eaMn6pKeOXmjJ+qaml4k/ysSSnkjya5J4kLx5qMEmrtXD8SQ4CHwE2qurNwD7g9qEGk7Ray2727wdekmQ/cAB4evmRJK3DwvFX1Y+BTwFPAmeAn1XV13ffL8mRJJtJNhcfU9LQltnsfyVwG3A18Brg8iTv332/qjpaVRtVtbH4mJKGtsxm/zuBH1bVs1X1K+A+4O3DjCVp1ZaJ/0ng+iQHsn3g9E3A1jBjSVq1ZV7zPwQcB04C350t6+hAc0lasazzbKwkgz7Y1M8kG9LQZ6V1eu5g2Odv6OduBT/buRboEX5SU8YvNWX8UlPGLzXlZbx28FJPi5v6G5Ld3uCch2t+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSnjl5oyfqkp45eaMn6pKeOXmjJ+qSmv4beD13mbjilfE/BSudaja36pKeOXmjJ+qSnjl5oyfqmpi8af5O4kzyR5dMdtr0ryb0l+MPv9lasdU9LQ5lnz/zNw867b7gS+UVXXAt+YfS9pD7lo/FX1beB/dt18G/CF2ddfAN478FySVmzR1/x/VFVnAGa//+FwI0lah5Uf4ZfkCHBk1Y8j6fez6Jr/p0muAJj9/sz57lhVR6tqo6o2FnwsSSuwaPz3Ax+cff1B4F+HGUfSuuRiJzwkuQd4B/Bq4KfAJ4F/Ab4MvBZ4Evirqtr9puC5ljXomTOeiDMdUz/ZpdOJPVU114AXjX9Ixn/p2gNBDLasPfD/OteAHuEnNWX8UlPGLzVl/FJTxi81te5r+P038F9z3O/Vs/te0Ejvus4124imPN9os835d2XKzx3MN9/r5l3YWnf1zSvJ5lSPCJzybDDt+aY8G/Sbz81+qSnjl5qaavxHxx7gAqY8G0x7vinPBs3mm+RrfkmrN9U1v6QVm1T8SW5O8v0kjyeZ1HUBk1yZ5FtJtpKcSnLH2DPtlmRfkkeSPDD2LLsleUWS40m+N3sO3zb2TL+V5GOzn+mjSe5J8uKR51nLRXMnE3+SfcA/Ae8G3gS8L8mbxp3qLM8Df1dVbwSuB/5mYvMB3AFsjT3EeXwW+FpVvQH4EyYyZ5KDwEeAjap6M7APuH3cqdZz0dzJxA+8FXi8qp6oqueAe9m+UOgkVNWZqjo5+/oXbP/lPTjuVL+T5BBwC3Bs7Fl2S/Jy4M+BuwCq6rmq+r9xpzrLfuAlSfYDB4CnxxxmXRfNnVL8B4Gndnx/mgnFtVOSq4DrgIfGneQsnwE+Dvx67EHO4RrgWeDzs5clx5JcPvZQAFX1Y+BTbF+U5gzws6r6+rhTndPgF82dUvznOv5ycrsikrwU+Arw0ar6+djzACS5FXimqk6MPct57AfeAnyuqq4DfslEPuth9tr5NuBq4DXA5UneP+5U6zGl+E8DV+74/hAjb37tluRFbIf/paq6b+x5drgBeE+SH7H9cunGJF8cd6SznAZOV9Vvt5SOs/2PwRS8E/hhVT1bVb8C7gPePvJM5zL3RXPnNaX4HwauTXJ1ksvYftPl/pFn+n/ZPjPkLmCrqj499jw7VdUnqupQVV3F9vP2zaqazNqrqn4CPJXk9bObbgIeG3GknZ4Erk9yYPYzvomJvBm5y+AXzV33WX3nVVXPJ/kw8CDb77jeXVWnRh5rpxuADwDfTfKd2W3/UFVfHXGmveRvgS/N/mF/AvjQyPMAUFUPJTkOnGR7j84jjHyk386L5iY5zfZFc/8R+HKSv2Z20dylH8cj/KSeprTZL2mNjF9qyvilpoxfasr4paaMX2rK+KWmjF9q6jfb3z81cRJ76AAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "laby_to_image(lab1)" ] }, { "cell_type": "code", "execution_count": 197, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPgAAAD8CAYAAABaQGkdAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAACmhJREFUeJzt3V+oZWUdh/Hn26hYpnhhxeRIFkQ3XmgMA2GElYWhlBddFNSFBHOTMRIRJUR01U1EXQWiltEfiUwQCU3IsCBtnFHxz5iIGB6mmMJCxxtRf13MEiabc84az15r7/md5wPDnD3ufd734Dyz1tp7rfWmqpDU01uWPQFJ0zFwqTEDlxozcKkxA5caM3CpMQOXGjNwqTEDlxo7bYpvmsTT46SJVVU2e45bcKkxA5caM3CpMQOXGjNwqTEDlxozcKkxA5caM3CpMQOXGjNwqbFRgSe5Islfkzyd5BtTT0rSYmSz2yYn2QE8BXwCWAP2A5+vqic2eI0Xm0gTW9TFJnuAp6vqmap6GbgV+MxWJydpemMCPx947rjHa8OfSVpxY64HP9FuwP/tgifZC+zd8owkLcyYwNeAC457vAs4/MYnVdUNwA3gMbi0Ksbsou8H3p/kvUnOAD4H3DHttCQtwqZb8Kp6Jcm1wN3ADuDmqnp88plJ2rJNPyZ7U9/UXXRpct6TTdrmDFxqzMClxgxcaszApcYMXGrMwKXGDFxqzMClxgxcamyS5YOXaYpTb6X1JJueLbpUbsGlxgxcaszApcYMXGrMwKXGDFxqzMClxgxcaszApcYMXGrMwKXGNg08yc1JjiR5bI4JSVqcMVvwnwBXTDwPSRPYNPCqug94foa5SFowj8GlxhZ2PbjLB0urZ9TaZEkuBO6sqotGfdMlrk3mDR80p2Xe8MG1yaRtbszHZL8E/gx8IMlaki9NPy1Ji9Bu+WB30TUnd9ElLY2BS40ZuNSYgUuNGbjUmIFLjRm41JiBS40ZuNSYgUuNtVs+eNWXc9XieXry+tyCS40ZuNSYgUuNGbjUmIFLjRm41JiBS40ZuNSYgUuNGbjUmIFLjY25L/oFSe5NcijJ40n2zTExSVu36X3Rk+wEdlbVwSRnAweAq6vqiQ1e49n/ms0yLzY55e+LXlV/r6qDw9cvAoeA87c+PUlTO6lj8GERwkuAB6aYjKTFGn09eJK3A7cB11XVCyf47y4fLK2YscsHnw7cCdxdVd8f8XyPwTUbj8HXN+ZNtgC3AM9X1XVjBjZwzcnA1zcm8A8DfwQeBV4b/vj6qvrtBq8xcM3GwNfXbvlgbT8Gvj7PZJMaM3CpMQOXGjNwqTEDlxozcKkxA5caM3CpMQOXGjNwqbF2ywdv49MWlza2VpdbcKkxA5caM3CpMQOXGjNwqTEDlxozcKkxA5caM3CpMQOXGjNwqbExywefmeQvSR4Zlg/+zhwTk7R1Y1c2Oauqjg5LGP0J2FdV92/wmqVd+eDFJprTqt8XfdOryerY35yjw8PTh1/+bZJOAaOOwZPsSPIwcAS4p6pcPlg6BYwKvKperaqLgV3AniQXvfE5SfYmeTDJg4uepKQ356TXJkvybeClqvreBs/xGHxmHoMvx6ofg495F/0dSc4dvn4rcDnw5NanJ2lqY27ZtBO4JckOjv2D8KuqunPaaUlahHbLB7uLrjmd8rvokk5dBi41ZuBSYwYuNWbgUmMGLjVm4FJjBi41ZuBSYwYuNWbgUmPt1gfXcnge/mpyCy41ZuBSYwYuNWbgUmMGLjVm4FJjBi41ZuBSYwYuNWbgUmOjAx/WJ3soifdEl04RJ7MF3wccmmoikhZv7Oqiu4ArgRunnY6kRRq7Bf8B8HXgtQnnImnBxiw+eBVwpKoObPI8lw+WVsyma5Ml+S7wReAV4EzgHOA3VfWFDV7j2mQzW/Y10dv1Z1/1tclOavHBJJcBX6uqqzZ5noHPzMCXY9UD93NwqTGXD16g7boVg+37s7sFl7Q0Bi41ZuBSYwYuNWbgUmMGLjVm4FJjBi41ZuBSYwYuNWbgUmMuH7xAyz4fXHojt+BSYwYuNWbgUmMGLjVm4FJjBi41ZuBSYwYuNWbgUmMGLjVm4FJjo85FT/Is8CLwKvBKVe2eclKSFuNkLjb5aFX9a7KZSFo4d9GlxsYGXsDvkhxIsvdET3D5YGn1jFqbLMm7q+pwkncC9wBfqar7Nnj+tlybbDtzbbL5LWxtsqo6PPx+BLgd2LO1qUmaw6aBJzkrydmvfw18Enhs6olJ2rox76K/C7h92BU5DfhFVd016awkLYTrg2shPAafn+uDS9ucgUuNGbjUmIFLjRm41JiBS40ZuNSYgUuNGbjUmIFLjbVbPniZpw5Kq8YtuNSYgUuNGbjUmIFLjRm41JiBS40ZuNSYgUuNGbjUmIFLjRm41NiowJOcm+TXSZ5McijJh6aemKStG3uxyQ+Bu6rqs0nOAN424ZwkLcimCx8kOQd4BHhfjbzD/DIXPtD248IH6xuzi/4+4J/Aj5M8lOTGYY2y/+HywdLqGbMF3w3cD1xaVQ8k+SHwQlV9a4PXuAXXbNyCr2/MFnwNWKuqB4bHvwY+uJWJSZrHpoFX1T+A55J8YPijjwNPTDorSQsxanXRJBcDNwJnAM8A11TVvzd4vrvomo276Otrt3ywth8DX59nskmNGbjUmIFLjRm41JiBS40ZuNSYgUuNGbjUmIFLjRm41NhUywf/C/jbm3ztecPrl8GxT8Gxt3C66Kn8c79nzJMmORd9K5I8WFW7HduxHXvr3EWXGjNwqbFVDPwGx3Zsx16MlTsGl7Q4q7gFl7QgKxV4kiuS/DXJ00m+MeO4Nyc5kuSxucY8buwLktw7rBjzeJJ9M459ZpK/JHlkGPs7c4193Bx2DLfjvnPmcZ9N8miSh+e+1fecKwWtzC56kh3AU8AnOHYn1/3A56tq8hs8JvkIcBT4aVVdNPV4bxh7J7Czqg4mORs4AFw9088d4KyqOprkdOBPwL6qun/qsY+bw1eB3cA5VXXVjOM+C+yuqtk/B09yC/DHqrrx9ZWCquo/U4y1SlvwPcDTVfVMVb0M3Ap8Zo6Bq+o+4Pk5xjrB2H+vqoPD1y8Ch4DzZxq7quro8PD04dds/+In2QVcybEbem4Lw0pBHwFuAqiql6eKG1Yr8POB5457vMZMf9FXRZILgUuABzZ+5kLH3JHkYeAIcM9x97+fww+ArwOvzTjm6wr4XZIDSfbOOO6olYIWZZUCP9H5hqtx/DCDJG8HbgOuq6oX5hq3ql6tqouBXcCeJLMcoiS5CjhSVQfmGO8ELq2qDwKfAr48HKbN4TSOLRzyo6q6BHgJmOz9plUKfA244LjHu4DDS5rLrIbj39uAn1fVb5Yxh2E38Q/AFTMNeSnw6eFY+FbgY0l+NtPYVNXh4fcjwO0cO0Scw6wrBa1S4PuB9yd57/DGw+eAO5Y8p8kNb3TdBByqqu/PPPY7kpw7fP1W4HLgyTnGrqpvVtWuqrqQY/+vf19VX5hj7CRnDW9oMuwefxKY5ROUuVcKmupqspNWVa8kuRa4G9gB3FxVj88xdpJfApcB5yVZA75dVTfNMTbHtmRfBB4djoUBrq+q384w9k7gluETjLcAv6qqWT+uWpJ3AbcPV6GdBvyiqu6acfyvAD8fNmTPANdMNdDKfEwmafFWaRdd0oIZuNSYgUuNGbjUmIFLjRm41JiBS40ZuNTYfwH3pD8f1pMi8QAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "laby_to_image(lab2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Correction du codage de l'entrée, __codez votre réponse dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 198, "metadata": {}, "outputs": [], "source": [ "# saisir votre code ici\n", "lab2[1][0] = 2" ] }, { "cell_type": "code", "execution_count": 199, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "#test\n", "assert lab2 == [[1, 1, 1, 1, 1, 1, 1],\n", " [2, 0, 0, 0, 0, 0, 1],\n", " [1, 1, 1, 1, 1, 0, 1],\n", " [1, 0, 1, 0, 0, 0, 1],\n", " [1, 0, 1, 0, 1, 0, 1],\n", " [1, 0, 0, 0, 1, 0, 1],\n", " [1, 1, 1, 1, 1, 3, 1]]\n", "print(\"Tests réussis\")" ] }, { "cell_type": "code", "execution_count": 200, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPgAAAD8CAYAAABaQGkdAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAACoZJREFUeJzt3U2oXPUdxvHnMYloo+LCVNIkVAVx04UvIVAsYluVFEN10YWCLqRwN1UipYgVirjqpoiuCiGmTakviBoQEV+gFhVqzI0vaIxKCBYvsSRii8aNRJ8ucgJpmnvnxDnnzNzf/X4g5M51Zv7/i/ebc87MnPN3EgGo6bRJTwBAfwgcKIzAgcIIHCiMwIHCCBwojMCBwggcKIzAgcKW9/Gktvl4HNCzJB51H7bgQGEEDhRG4EBhBA4URuBAYQQOFEbgQGEEDhRG4EBhBA4URuBAYa0Ct73R9ge299m+u+9JAeiGR1022fYySR9KulbSnKRdkm5O8t4Cj+FkE6BnXZ1sskHSviT7k3wl6TFJN4w7OQD9axP4GkkfH3d7rvkegCnX5nzwk+0G/N8uuO0ZSTNjzwhAZ9oEPidp3XG310o6cOKdkmyRtEXiGByYFm120XdJutj2hbZPl3STpKf7nRaALozcgic5Yvt2Sc9LWiZpW5I9vc8MwNhGvk32rZ6UXXSgd1yTDVjiCBwojMCBwggcKIzAgcIIHCiMwIHCCBwojMCBwggcKKyX5YOvuOIKzc7O9vHUwFSxR35adKLYggOFEThQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhRE4UBiBA4WNDNz2NtsHbb87xIQAdKfNFvzPkjb2PA8APRgZeJKXJX02wFwAdIxjcKCwzgK3PWN71vbsoUOHunpaAGPoLPAkW5KsT7J+1apVXT0tgDGwiw4U1uZtskcl/UPSJbbnbP+y/2kB6EKb9cFvHmIiALrHLjpQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhRE4UBiBA4U5SfdPanf/pMA8+vgdbmuSywcnGTk4W3CgMAIHCiNwoDACBwojcKAwAgcKI3CgMAIHCiNwoDACBwojcKCwNtdFX2f7Jdt7be+xvXmIiQEY38iTTWyvlrQ6yRu2z5a0W9KNSd5b4DGcbILBcLLJ/NosH/xJkjear7+QtFfSmvGnB6Bvp3QMbvsCSZdJ2tnHZAB0a+TSRcfYPkvSk5LuTPL5Sf77jKSZDucGYEytLvhge4WkZyQ9n+T+FvfnGByD4Rh8fm1eZLOk7ZI+S3Jnm4EJHEMi8Pm1CfxHkl6R9I6kb5pv35Pk2QUeQ+AYDIHPj2uyYdEj8PnxSTagMAIHCiNwoDACBwojcKAwAgcKI3CgMAIHCiNwoDACBwprfbroYrGEP7Y4sbExvdiCA4UROFAYgQOFEThQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhbVZPvgM26/bfrtZPvi+ISYGYHxtVzZZmeRws4TRq5I2J3ltgcdM7MwHTjbBkKb9uugjzybL0d+cw83NFc0ffpuARaDVMbjtZbbfknRQ0otJWD4YWARaBZ7k6ySXSloraYPtH5x4H9sztmdtz3Y9SQDfzimvTWb7XklfJvnDAvfhGHxgHINPxrQfg7d5FX2V7XObr8+UdI2k98efHoC+tblk02pJ220v09F/EB5P8ky/0wLQhXLLB7OLjiEt+l10AIsXgQOFEThQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhRE4UFi59cExGXwOfzqxBQcKI3CgMAIHCiNwoDACBwojcKAwAgcKI3CgMAIHCiNwoLDWgTfrk71pm2uiA4vEqWzBN0va29dEAHSv7eqiayVdL2lrv9MB0KW2W/AHJN0l6Zse5wKgY20WH9wk6WCS3SPux/LBwJQZuTaZ7d9LulXSEUlnSDpH0lNJblngMaxNNrBJnxO9VH/2aV+b7JQWH7R9taTfJNk04n4EPjACn4xpD5z3wYHCWD64Q0t1KyYt3Z+dLTiAiSFwoDACBwojcKAwAgcKI3CgMAIHCiNwoDACBwojcKAwAgcKY/ngDk368+DAidiCA4UROFAYgQOFEThQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhbX6LLrtjyR9IelrSUeSrO9zUgC6cSonm/w4yae9zQRA59hFBwprG3gkvWB7t+2Zk92B5YOB6dNqbTLb30tywPZ3Jb0o6Y4kLy9w/yW5NtlSxtpkw+tsbbIkB5q/D0raIWnDeFMDMISRgdteafvsY19Luk7Su31PDMD42ryKfr6kHc2uyHJJjyR5rtdZAegE64OjExyDD4/1wYEljsCBwggcKIzAgcIIHCiMwIHCCBwojMCBwggcKIzAgcLKLR88yY8OAtOGLThQGIEDhRE4UBiBA4UROFAYgQOFEThQGIEDhRE4UBiBA4UROFBYq8Btn2v7Cdvv295r+4d9TwzA+NqebPKgpOeS/ML26ZK+0+OcAHRk5MIHts+R9Laki9LyCvOTXPgASw8LH8yvzS76RZIOSfqT7Tdtb23WKPsfLB8MTJ82W/D1kl6TdGWSnbYflPR5kt8t8Bi24BgMW/D5tdmCz0maS7Kzuf2EpMvHmRiAYYwMPMm/JH1s+5LmWz+V9F6vswLQiVari9q+VNJWSadL2i/ptiT/XuD+7KJjMOyiz6/c8sFYegh8fnySDSiMwIHCCBwojMCBwggcKIzAgcIIHCiMwIHCCBwojMCBwvpaPvhTSf/8lo89r3n8JDD2Ihx7jI+LLuaf+/tt7tTLZ9HHYXs2yXrGZmzGHh+76EBhBA4UNo2Bb2FsxmbsbkzdMTiA7kzjFhxAR6YqcNsbbX9ge5/tuwccd5vtg7bfHWrM48ZeZ/ulZsWYPbY3Dzj2GbZft/12M/Z9Q4193ByWNZfjfmbgcT+y/Y7tt4a+1PeQKwVNzS667WWSPpR0rY5eyXWXpJuT9H6BR9tXSTos6S9JftD3eCeMvVrS6iRv2D5b0m5JNw70c1vSyiSHba+Q9KqkzUle63vs4+bwa0nrJZ2TZNOA434kaX2Swd8Ht71d0itJth5bKSjJf/oYa5q24Bsk7UuyP8lXkh6TdMMQAyd5WdJnQ4x1krE/SfJG8/UXkvZKWjPQ2ElyuLm5ovkz2L/4ttdKul5HL+i5JDQrBV0l6SFJSvJVX3FL0xX4GkkfH3d7TgP9ok8L2xdIukzSzoXv2emYy2y/JemgpBePu/79EB6QdJekbwYc85hIesH2btszA47baqWgrkxT4Cf7vOF0HD8MwPZZkp6UdGeSz4caN8nXSS6VtFbSBtuDHKLY3iTpYJLdQ4x3ElcmuVzSzyT9qjlMG8JyHV045I9JLpP0paTeXm+apsDnJK077vZaSQcmNJdBNce/T0p6OMlTk5hDs5v4d0kbBxrySkk/b46FH5P0E9t/HWhsJTnQ/H1Q0g4dPUQcwqArBU1T4LskXWz7wuaFh5skPT3hOfWueaHrIUl7k9w/8NirbJ/bfH2mpGskvT/E2El+m2Rtkgt09P/135LcMsTYtlc2L2iq2T2+TtIg76AMvVJQX2eTnbIkR2zfLul5ScskbUuyZ4ixbT8q6WpJ59mek3RvkoeGGFtHt2S3SnqnORaWpHuSPDvA2KslbW/ewThN0uNJBn27akLOl7SjOQttuaRHkjw34Ph3SHq42ZDtl3RbXwNNzdtkALo3TbvoADpG4EBhBA4URuBAYQQOFEbgQGEEDhRG4EBh/wVAsD+oWHjBgwAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "laby_to_image(lab2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrire une fonction est_valide(i, j, n, m) qui renvoie True si le couple (i,j) correspond à des coordonnées valides pour un labyrinthe de taille (n,m), et False sinon.\n", "On donne ci-dessous des exemples d'appels.\n", "\n", "~~~python\n", ">>> est_valide(5, 2, 10, 10)\n", "True\n", ">>> est_valide(-3, 4, 10, 10)\n", "False\n", "~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Codez votre réponse dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 201, "metadata": {}, "outputs": [], "source": [ "# saisir votre code ici\n", "def est_valide(i, j, n, m):\n", " return 0 <= i < n and 0 <= j < m" ] }, { "cell_type": "code", "execution_count": 202, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "#Tests unitaires\n", "assert est_valide(5, 2, 10, 10) == True\n", "assert est_valide(-3, 4, 10, 10) == False\n", "print(\"Tests réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On suppose que le départ d'un labyrinthe est toujours indiqué, mais on ne fait aucune\n", "supposition sur son emplacement. Compléter la fonction depart(lab)ci-dessous de sorte\n", "qu'elle renvoie, sous la forme d'un tuple, les coordonnées du départ d'un labyrinthe\n", "(représenté par le paramètre lab). Par exemple, l'appel depart(lab1) doit renvoyer le\n", "tuple (5, 0).\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 3\n", "\n", "__Codez votre réponse dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 203, "metadata": {}, "outputs": [], "source": [ "# saisir votre code ici\n", "def depart(lab):\n", " n = len(lab)\n", " m = len(lab[0])\n", " for i in range(n):\n", " for j in range(m):\n", " if lab[i][j] == 2:\n", " return (i, j)" ] }, { "cell_type": "code", "execution_count": 204, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "# tests unitaires\n", "assert depart(lab1) == (5, 0)\n", "assert depart(lab2) == (1, 0)\n", "print(\"Tests réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrire une fonction nb_cases_vides(lab) qui renvoie le nombre de cases vides d'un\n", "labyrinthe (comprenant donc l'arrivée et le départ).\n", "Par exemple, l'appel nb_cases_vides(lab2) doit renvoyer la valeur 19." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 4\n", "\n", "__Codez votre réponse dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 205, "metadata": {}, "outputs": [], "source": [ "# saisir votre code ici\n", "def nb_cases_vides(lab):\n", " c = 0\n", " n = len(lab)\n", " m = len(lab[0])\n", " for i in range(n):\n", " for j in range(m):\n", " if lab[i][j] != 1:\n", " c = c + 1\n", " return c" ] }, { "cell_type": "code", "execution_count": 206, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "# tests unitaires\n", "assert nb_cases_vides(lab1) == 58\n", "assert nb_cases_vides(lab2) == 19\n", "print(\"Tests réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Partie B : Recherche d’une solution dans un labyrinthe\n", " \n", " \n", "On suppose dans cette partie que les labyrinthes possèdent un unique chemin allant du départ\n", "à l’arrivée sans repasser par la même case. Dans la suite, c’est ce chemin que l’on appellera\n", "solution du labyrinthe.\n", "Pour déterminer la solution d'un labyrinthe, on parcourt les cases vides de proche en proche.\n", "Lors d’un tel parcours, afin d’éviter de tourner en rond, on choisit de marquer les cases visitées.\n", "Pour cela, on remplace la valeur d'une case visitée dans le tableau représentant le labyrinthe\n", "par la valeur 4." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On dit que deux cases d'un labyrinthe sont voisines si elles ont un côté commun.\n", "On considère une fonction voisines(i, j, lab) qui prend en arguments deux entiers ݅\n", "et ݆ représentant les coordonnées d’une case et un tableau lab qui représente un labyrinthe.\n", "Cette fonction renvoie la liste des coordonnées des cases voisines de la case de\n", "coordonnées (i, j) qui sont valides, non visitées et qui ne sont pas des murs. L'ordre des\n", "éléments de cette liste n'importe pas.\n", "Ainsi, l'appel `voisines(1, 1, [[1, 1, 1], [4, 0, 0], [1, 0, 1]])` renvoie la\n", "liste [(2, 1), (1, 2)].\n", "Que renvoie l'appel `voisines(1, 2, [[1, 1, 4], [0, 0, 0], [1, 1, 0]])` ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1\n", "\n", "Saisir votre réponse ici.\n", "\n", "`voisines(1, 2, [[1, 1, 4], [0, 0, 0], [1, 1, 0]])` renvoie la liste `[(1,1), (2,2)]`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complément : codez une fonction voisines\n", "\n", "__Saisir votre réponse ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 207, "metadata": {}, "outputs": [], "source": [ "def voisines(i, j, lab):\n", " n = len(lab)\n", " m = len(lab[0])\n", " liste_voisines = []\n", " for (vi, vj) in [(i,j-1), (i+1, j), (i, j+1), (i-1, j)]:\n", " if est_valide(vi, vj, n, m) and (lab[vi][vj] == 0 or lab[vi][vj] == 3):\n", " liste_voisines.append((vi, vj))\n", " return liste_voisines" ] }, { "cell_type": "code", "execution_count": 208, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussi\n" ] } ], "source": [ "# test unitaire\n", "assert set(voisines(1, 1, [[1, 1, 1], [4, 0, 0], [1, 0, 1]])) == set([(2, 1), (1, 2)])\n", "print(\"Test réussi\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2\n", "\n", "\n", "On souhaite stocker la solution dans une liste chemin. Cette liste contiendra les\n", "coordonnées des cases de la solution, dans l'ordre. Pour cela, on procède de la façon\n", "suivante.\n", "\n", "* Initialement :\n", " - déterminer les coordonnées du départ : c'est la première case à visiter ;\n", " - ajouter les coordonnées de la case départ à la liste chemin.\n", "* Tant que l'arrivée n'a pas été atteinte :\n", " - on marque la case visitée avec la valeur 4 ;\n", " - si la case visitée possède une case voisine libre, la première case de la liste renvoyée par la fonction voisines devient la prochaine case à visiter et on ajoute à la liste chemin ;\n", " - sinon, il s'agit d'une impasse. On supprime alors la dernière case dans la liste chemin. La prochaine case à visiter est celle qui est désormais en dernière position de la liste chemin.\n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2 a\n", "\n", "On donne un nouveau labyrinthe `lab3` :" ] }, { "cell_type": "code", "execution_count": 209, "metadata": {}, "outputs": [], "source": [ "lab3 = [[1, 1, 1, 1, 1, 1],\n", "[2, 0, 0, 0, 0, 3],\n", "[1, 0, 1, 0, 1, 1],\n", "[1, 1, 1, 0, 0, 1]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La suite d'instructions ci-dessous simule le début des modifications subies par la liste\n", "chemin lorsque l'on applique la méthode présentée.\n", "\n", "~~~python\n", "# entrée: (1, 0),sortie (1, 5)\n", "chemin = [(1, 0)]\n", "chemin.append((1,1))\n", "chemin.append((2,1))\n", "chemin.pop()\n", "chemin.append((1,2))\n", "chemin.append((1,3))\n", "chemin.append((2,3))\n", "~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Compléter cette suite d'instructions jusqu'à ce que la liste chemin représente la\n", "solution. Rappel : la méthode `pop` supprime le dernier élément d'une liste et renvoie cet\n", "élément." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2. a.\n", "\n", "Saisir votre réponse ici.\n", "\n", "~~~python\n", "# entrée: (1, 0),\n", "chemin = [(1, 0)]\n", "chemin.append((1,1))\n", "chemin.append((2,1))\n", "chemin.pop()\n", "chemin.append((1,2))\n", "chemin.append((1,3))\n", "chemin.append((2,3))\n", "chemin.append((3,3))\n", "chemin.pop()\n", "chemin.pop()\n", "chemin.append((1,4))\n", "chemin.append((1,5))\n", "~~~\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2.a\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recopier et compléter la fonction solution(lab) donnée ci-dessous de sorte qu'elle\n", "renvoie le chemin solution du labyrinthe représenté par le paramètre lab.\n", "On pourra pour cela utiliser la fonction voisines.\n", "\n", "__Saisir votre code dans la cellule ci-dessous__" ] }, { "cell_type": "code", "execution_count": 210, "metadata": {}, "outputs": [], "source": [ "def solution(lab):\n", " lab = deepcopy(lab)\n", " chemin = [depart(lab)]\n", " case = chemin[0]\n", " i = case[0]\n", " j = case[1] \n", " while lab[i][j] != 3:\n", " lab[i][j] = 4\n", " liste_voisines = voisines(i, j, lab)\n", " if len(liste_voisines) > 0:\n", " (i, j) = liste_voisines[0]\n", " chemin.append((i, j))\n", " else:\n", " chemin.pop()\n", " (i, j) = chemin[len(chemin)-1]\n", " return chemin" ] }, { "cell_type": "code", "execution_count": 211, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussis\n" ] } ], "source": [ "# Tests unitaires\n", "assert solution(lab2) == [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), \n", " (2, 5), (3, 5), (4, 5), (5, 5), (6, 5)]\n", "assert solution(lab1) == [(5, 0), (5, 1), (4, 1), (3, 1), (2, 1), (1, 1), (1, 2),\n", " (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (5, 4), (5, 5),\n", " (4, 5), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7),\n", " (0, 8), (0, 9), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (5, 10)]\n", "assert solution(lab3) == [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]\n", "print(\"Test réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "_Cet exercice traite de manipulation de tableaux, de récursivité et du paradigme « diviser pour\n", "régner »._" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans un tableau Python d'entiers tab, on dit que le couple d’indices (݅i, j) forme une inversion\n", "lorsque ݅ i < j et tab[i] > tab[j]. On donne ci-dessous quelques exemples.\n", "\n", "* Dans le tableau [1, 5, 3, 7], le couple d’indices (1,2) forme une inversion car 5 > 3. Par contre, le couple (1,3) neforme pas d'inversion car 5 < 7. Il n’y a qu’une inversion dans ce tableau.\n", "\n", "* Il y a trois inversions dans le tableau [1, 6, 2, 7, 3], à savoir les couples d'indices (1, 2), (1, 4) et (3, 4).\n", "\n", "* On peut compter six inversions dans le tableau [7, 6, 5, 3] : les couples d'indices (0, 1), (0, 2), (0, 3), (1, 2), (1, 3) et (2, 3).\n", "\n", "\n", "On se propose dans cet exercice de déterminer le nombre d’inversions dans un tableau quelconque. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Questions préliminaires " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. Expliquer pourquoi le couple (1, 3) est une inversion dans le tableau [4, 8, 3, 7]." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1\n", "\n", "Saisir votre réponse ici :" ] }, { "cell_type": "code", "execution_count": 212, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 212, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tab = [4, 8, 3, 7]\n", "1 < 3 and tab[1] > tab[3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Justifier que le couple (2, 3) n’en est pas une." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2\n", "\n", "Saisir votre réponse ici " ] }, { "cell_type": "code", "execution_count": 213, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 213, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tab = [4, 8, 3, 7]\n", "2 < 3 and tab[2] > tab[3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Partie A : méthode itérative" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le but de cette partie est d’écrire une fonction itérative nombre_inversion qui renvoie le\n", "nombre d’inversions dans un tableau. Pour cela, on commence par écrire une fonction\n", "fonction1 qui sera ensuite utilisée pour écrire la fonction nombre_inversion." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1 a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On donne la fonction suivante.\n", "\n", "~~~python\n", "def fonction1(tab, i):\n", " nb_elem = len(tab)\n", " cpt = 0\n", " for j in range(i+1, nb_elem):\n", " if tab[j] < tab[i]:\n", " cpt += 1\n", " return cpt\n", "~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Indiquer ce que renvoie la fonction1(tab, i) dans les cas suivants.\n", "* Cas n°1 : tab = [1, 5, 3, 7] et i = 0.\n", "* Cas n°2 : tab = [1, 5, 3, 7] et i = 1.\n", "* Cas n°3 : tab = [1, 5, 2, 6, 4] et i = 1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1 a\n", "Saisir votre réponse ici : " ] }, { "cell_type": "code", "execution_count": 218, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cas 1 : fonction1([1, 5, 3, 7], 0)= 0\n", "Cas 2 : fonction1([1, 5, 3, 7], 1)= 1\n", "Cas 3 : fonction1([1, 5, 2, 6, 4], 1)= 2\n" ] } ], "source": [ "def fonction1(tab, i):\n", " nb_elem = len(tab)\n", " cpt = 0\n", " for j in range(i+1, nb_elem):\n", " if tab[j] < tab[i]:\n", " cpt += 1\n", " return cpt\n", "\n", "print(\"Cas 1 : fonction1([1, 5, 3, 7], 0)=\", fonction1([1, 5, 3, 7], 0))\n", "print(\"Cas 2 : fonction1([1, 5, 3, 7], 1)=\", fonction1([1, 5, 3, 7], 1))\n", "print(\"Cas 3 : fonction1([1, 5, 2, 6, 4], 1)=\", fonction1([1, 5, 2, 6, 4], 1))\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1 b\n", "\n", "Expliquer ce que permet de déterminer cette fonction." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1 b\n", "\n", "Saisir votre réponse ici.\n", "\n", "Fonction1 renvoie le nombre de couple (i,j) qui forment une inversion avec i < j < len(tab)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En utilisant la fonction précédente, écrire une fonction nombre_inversion(tab) qui\n", "prend en argument un tableau et renvoie le nombre d’inversions dans ce tableau.\n", "On donne ci-dessous les résultats attendus pour certains appels.\n", "\n", "~~~python\n", ">>> nombre_inversions([1, 5, 7])\n", "0\n", ">>> nombre_inversions([1, 6, 2, 7, 3])\n", "3\n", ">>> nombre_inversions([7, 6, 5, 3])\n", "6\n", "~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2 \n", "\n", "__Saisir votre code dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 221, "metadata": {}, "outputs": [], "source": [ "# saisir votre code ici\n", "def nombre_inversions(tab):\n", " cpt = 0\n", " for i in range(len(tab) - 1):\n", " cpt = cpt + fonction1(tab, i)\n", " return cpt" ] }, { "cell_type": "code", "execution_count": 222, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussis\n" ] } ], "source": [ "# tests unitaires\n", "assert nombre_inversions([1, 5, 7]) == 0\n", "assert nombre_inversions([1, 6, 2, 7, 3]) == 3\n", "assert nombre_inversions([7, 6, 5, 3]) == 6\n", "print(\"Test réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quelle est l’ordre de grandeur de la complexité en temps de l'algorithme obtenu ?\n", "Aucune justification n'est attendue." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 3\n", "\n", "Saisir votre réponse ici.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La complexité est quadratique par rapport à la taille du tableau, c'est-à-dire de l'ordre de $(len(tab))^{2}$. En effet pour i allant de 0 à `len(tab) - 2`, on exécute `fonction1(tab, i)` qui contient une boucle avec `len(tab) - i - 1` itérations. On a donc $\\sum_{i=0}^{len(tab) - 2}len(tab) - i - 1 = \\sum_{j=1}^{len(tab) - 1}j=\\frac{(len(tab)-1)(len(tab))}{2}$ exécutions de la boucle interne." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Partie B : Méthode récursive\n", "Le but de cette partie est de concevoir une version récursive de la fonction\n", "nombre_inversion.\n", "On définit pour cela des fonctions auxiliaires.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1\n", "\n", "1. Donner le nom d’un algorithme de tri ayant une complexité meilleure que quadratique. On donne une implémentation de ce tri ci-dessous.\n", "\n", "_Indication : chercher sur cette page _" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 1\n", "\n", "Il s'agit du tri fusion dont la complexité a pour ordre de grandeur $n\\log(n)$ où $n$ est la taille du tableau. On en donne une implémentation ci-dessous." ] }, { "cell_type": "code", "execution_count": 275, "metadata": {}, "outputs": [], "source": [ "def fusion(tab,a, b, c):\n", " \"\"\"Procédure qui fusionne dans l'ordre croissant\n", " deux sous tableaux consécutifs de tab \n", " chaque sous tableau étant trié dans l'ordre croissant :\n", " tb[a:b] et tab[b:c]\n", " \"\"\"\n", " tmp = [0 for _ in range(c - a)] #tableau temporaire pour fusionner\n", " i = a #indice dans le sous tableau tab[a:b]\n", " j = b #indice dans le sous tableau tab[c:d]\n", " k = 0 #indice dans le sous-tableau tmp\n", " #tant qu'on n'a pas traité complètement l'un des 2 sous-tableaux\n", " while i < b and j < c: \n", " if tab[i] < tab[j]:\n", " tmp[k] = tab[i]\n", " i = i + 1\n", " else:\n", " tmp[k] = tab[j]\n", " j = j + 1\n", " k = k + 1\n", " #on complète tmp avec les éléments restants dans tab[b:c]\n", " while i < b:\n", " tmp[k] = tab[i]\n", " i = i + 1\n", " k = k + 1\n", " #on complète tmp avec les éléments restants dans tab[a:b]\n", " while j < c:\n", " tmp[k] = tab[j]\n", " j = j + 1\n", " k = k + 1\n", " #on recopie le tableau temporaire\n", " for k in range(c - a):\n", " tab[a + k] = tmp[k]\n", " \n", "def tri(tab):\n", " \"\"\"Procédure qui trie en place le tableau tab par tri fusion\"\"\"\n", " def tri_aux(tab, debut, fin):\n", " \"\"\"Fonction récursive auxiliaire qui réalise le tri fusion\"\"\"\n", " if fin - debut > 1:\n", " med = (debut + fin) // 2 #on coupe le tableau en 2 (diviser pour régner)\n", " tri_aux(tab, debut, med) #on trie récursivement tab[debut:med]\n", " tri_aux(tab, med, fin) #on trie récursivement tab[med:fin]\n", " fusion(tab, debut, med, fin) #on fusionne tab[debut:med] et tab[med:fin]\n", " tri_aux(tab, 0, len(tab))" ] }, { "cell_type": "code", "execution_count": 241, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 7, 8]" ] }, "execution_count": 241, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#petit exemple de fusion\n", "tab = [0, 2, 8, 1, 3, 7]\n", "fusion(tab, 0, 3, 6)\n", "tab" ] }, { "cell_type": "code", "execution_count": 249, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "#tests unitaires de tri_fusion\n", "import random\n", "for taille in range(0, 10):\n", " for essai in range(5):\n", " tab_alea = [random.randint(0, 100) for _ in range(taille)]\n", " tab_croissant = sorted(tab_alea)\n", " tab_decroissant = sorted(tab_alea, reverse = True)\n", " copie_tab_alea = tab_alea[:]\n", " copie_tab_croissant = tab_croissant[:]\n", " copie_tab_decroissant = tab_decroissant[:]\n", " tri(copie_tab_alea)\n", " tri(copie_tab_croissant)\n", " tri(copie_tab_decroissant)\n", " assert copie_tab_alea == tab_croissant\n", " assert copie_tab_croissant == tab_croissant\n", " assert copie_tab_decroissant == tab_croissant\n", "print(\"Tests réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans la suite de cet exercice, on suppose qu’on dispose d'une fonction tri(tab) qui prend en\n", "argument un tableau et renvoie un tableau contenant les mêmes éléments rangés dans l'ordre\n", "croissant." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrire une fonction moitie_gauche(tab) qui prend en argument un tableau tab et\n", "renvoie un nouveau tableau contenant la moitié gauche de tab. Si le nombre d'éléments\n", "de tab est impair, l'élément du centre se trouve dans cette partie gauche.\n", "On donne ci-dessous les résultats attendus pour certains appels.\n", "\n", "~~~python\n", ">>> moitie_gauche([])\n", "[]\n", ">>> moitie_gauche([4, 8, 3])\n", "[4, 8]\n", ">>> moitie_gauche ([4, 8, 3, 7])\n", "[4, 8]\n", "~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 2 \n", "\n", "__Saisir votre code dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 270, "metadata": {}, "outputs": [], "source": [ "#saisir votre code ici\n", "def moitie_gauche(tab):\n", " n = len(tab)\n", " med = n // 2\n", " if n % 2 == 1:\n", " med = med + 1\n", " #attention les index commencent à 0\n", " return [tab[k] for k in range(0, med)]" ] }, { "cell_type": "code", "execution_count": 267, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussis\n" ] } ], "source": [ "#Test unitaires\n", "\n", "assert moitie_gauche([]) == []\n", "assert moitie_gauche([4, 8, 3]) == [4,8]\n", "assert moitie_gauche([4, 8, 3, 7]) == [4,8]\n", "print(\"Test réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Complément à la question 2\n", "\n", "__Codez la fonction `moitie_droite` dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 271, "metadata": {}, "outputs": [], "source": [ "#saisir votre code ici\n", "def moitie_droite(tab):\n", " n = len(tab)\n", " med = n // 2\n", " if n % 2 == 1:\n", " med = med + 1\n", " #attention les index commencent à 0\n", " return [tab[k] for k in range(med, n)]" ] }, { "cell_type": "code", "execution_count": 269, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussis\n" ] } ], "source": [ "#Test unitaires\n", "\n", "assert moitie_droite([]) == []\n", "assert moitie_droite([4, 8, 3]) == [3]\n", "assert moitie_droite([4, 8, 3, 7]) == [3,7]\n", "print(\"Test réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3 a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrire une fonction `nb_inv_tab(tab1, tab2)`. Cette fonction\n", "renvoie le nombre d’inversions du tableau obtenu en mettant bout à bout les tableaux\n", "tab1 et tab2, à condition que tab1 et tab2 soient triés dans l’ordre croissant.\n", "On donne ci-dessous deux exemples d’appel de cette fonction :\n", " \n", "~~~python\n", ">>> nb_inv_tab([3, 7, 9], [2, 10])\n", "3\n", ">>> nb_inv_tab([7, 9, 13], [7, 10, 14])\n", "3\n", "~~~\n", "Estimer la complexité de cette fonction, comparer avec celle des voisins." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 3) a)\n", "\n", "__Saisir votre code dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 288, "metadata": {}, "outputs": [], "source": [ "def nb_inv_tab_quadratique(tab1, tab2):\n", " \"\"\"Complexité quadratique en O(len(tab1) * len(tab2))\"\"\"\n", " n = len(tab1)\n", " m = len(tab2)\n", " cpt = 0\n", " for i in range(n):\n", " for j in range(m):\n", " if tab[i] > tab[j]:\n", " cpt = cpt + 1\n", " return cpt \n", "\n", "def nb_inv_tab(tab1, tab2):\n", " \"\"\"Complexité linéaire en O(len(tab1) + len(tab1))\"\"\"\n", " n = len(tab1)\n", " m = len(tab2)\n", " cpt = 0\n", " j = 0\n", " for i in range(n):\n", " while j < m and tab2[j] < tab1[i]:\n", " j = j + 1\n", " cpt = cpt + j\n", " return cpt " ] }, { "cell_type": "code", "execution_count": 289, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests réussis\n" ] } ], "source": [ "#Tests unitaires\n", "assert nb_inv_tab([3, 7, 9], [2, 10]) == 3\n", "assert nb_inv_tab([7, 9, 13], [7, 10, 14]) == 3\n", "print(\"Tests réussis\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3 b)\n", "\n", "En utilisant la fonction nb_inv_tab et les questions précédentes, écrire une fonction\n", "récursive nb_inversions_rec(tab) qui permet de calculer le nombre d'inversions\n", "dans un tableau. Cette fonction renverra le même nombre que\n", "nombre_inversions(tab) de la partie A. On procédera de la façon suivante :\n", "\n", "* Séparer le tableau en deux tableaux de tailles égales (à une unité près).\n", "* Appeler récursivement la fonction `nb_inversions_rec` pour compter le nombre d’inversions dans chacun des deux tableaux\n", "* Trier les deux tableaux (on rappelle qu'une fonction de tri est déjà définie). \n", "* Ajouter au nombre d'inversions précédemment comptées le nombre renvoyé par la fonction `nb_inv_tab` avec pour arguments les deux tableaux triés.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Réponse à la question 3) b)\n", "\n", "__Saisir votre code dans la cellule ci-dessous.__" ] }, { "cell_type": "code", "execution_count": 292, "metadata": {}, "outputs": [], "source": [ "def nb_inversions_rec(tab):\n", " \"\"\"On peut montrer que c'est une complexité d'ordre de grandeur n * (log(n)) ** 2\"\"\"\n", " if len(tab) >= 2:\n", " gauche = moitie_gauche(tab) \n", " droite = moitie_droite(tab) \n", " cpt = nb_inversions_rec(gauche) \n", " cpt = cpt + nb_inversions_rec(droite)\n", " tri(gauche)\n", " tri(droite)\n", " return cpt + nb_inv_tab(gauche, droite)\n", " return 0" ] }, { "cell_type": "code", "execution_count": 291, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test réussis\n" ] } ], "source": [ "# tests unitaires\n", "assert nb_inversions_rec([1, 5, 7]) == 0\n", "assert nb_inversions_rec([1, 6, 2, 7, 3]) == 3\n", "assert nb_inversions_rec([7, 6, 5, 3]) == 6\n", "print(\"Test réussis\")" ] }, { "cell_type": "code", "execution_count": 345, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " Taille Rapport durées Rapport ordres de grandeurs Rapport constantes \n", " 32.0000 2.1311 3.1250 0.6820 \n", " 64.0000 2.5400 2.8800 0.8819 \n", " 128.0000 2.4227 2.7222 0.8900 \n", " 256.0000 2.6293 2.6122 1.0065 \n", " 512.0000 2.1936 2.5312 0.8666 \n", " 1024.0000 2.2757 2.4691 0.9217 \n", " 2048.0000 2.2785 2.4200 0.9415 \n", " 4096.0000 2.3551 2.3802 0.9895 \n", " 8192.0000 2.2409 2.3472 0.9547 \n", " 16384.0000 2.2291 2.3195 0.9610 \n" ] } ], "source": [ "import random\n", "import time\n", "import math\n", "\n", "def tableau_aleatoire(taille):\n", " return [random.randint(0, 100) for _ in range(taille)]\n", "\n", "def ordre_grandeur(taille):\n", " return taille * (math.log(taille)) ** 2\n", "\n", "\n", "def doubling_ratio():\n", " \"\"\"Mesure de l'évolution du rapport de durée d'exécution sur un échantillon de tableaux de même taille\n", " lorsqu'on double la taille, comparaison avec l'évolution du rapport de l'ordre de grandeur,\n", " mesure de l'évolution du rapport des constantes duree/(ordre de grandeur)\"\"\"\n", " print(\"{:^20}\".format(\"Taille\"), \"{:^20}\".format(\"Rapport durées\"),\n", " \"{:^20}\".format(\"Rapport ordres de grandeurs\"),\n", " \"{:^20}\".format(\"Rapport constantes\"))\n", " taille_echantillon = 5\n", " duree_moyenne = 0\n", " constante = 0\n", " liste_taille = [2 ** k for k in range(4, 15)]\n", " for i in range(len(liste_taille)):\n", " constante_preced = constante\n", " duree_moyenne_preced = duree_moyenne\n", " duree_totale = 0\n", " taille = liste_taille[i]\n", " echantillon = [tableau_aleatoire(taille) for _ in range(taille_echantillon)]\n", " for j in range(taille_echantillon): \n", " debut = time.perf_counter()\n", " nb_inversions_rec(echantillon[j])\n", " duree = time.perf_counter() - debut\n", " duree_totale += duree\n", " duree_moyenne = duree_totale / taille_echantillon\n", " taille_preced = liste_taille[i-1]\n", " constante = duree_moyenne/ordre_grandeur(taille)\n", " if i > 0:\n", " print(f\"{taille:^20.4f}\",\n", " f\"{duree_moyenne/duree_moyenne_preced:^20.4f}\",\n", " f\"{ordre_grandeur(taille) / ordre_grandeur(taille_preced):^20.4f}\", \n", " f\"{constante / constante_preced :^20.4f}\")\n", " \n", "doubling_ratio()" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }