{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Référence : " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1) a)" ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour total_hors_reduction\n" ] } ], "source": [ "def total_hors_reduction(tab):\n", " \"\"\"Renvoie la somme des valeurs numériques contenues \n", " dans un tableau tab\n", " \"\"\"\n", " somme = 0\n", " for element in tab:\n", " somme = somme + element\n", " return somme\n", "\n", "#tests unitaires\n", "def test_total_hors_reduction():\n", " assert total_hors_reduction([]) == 0\n", " assert total_hors_reduction([2,2]) == 4\n", " assert total_hors_reduction([1,2]) == 3\n", " assert total_hors_reduction([-1,2]) == 1\n", " print(\"Tests unitaires réussis pour total_hors_reduction\")\n", " \n", "test_total_hors_reduction()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 1) b)" ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour offre_bienvenue\n" ] } ], "source": [ "def offre_bienvenue(tab):\n", " \"\"\"\n", " Le site de vente propose la promotion suivante \n", " comme offre de bienvenue : 20% de réduction\n", " sur le premier article de la liste, \n", " 30% de réduction sur le deuxième article de la liste \n", " (s’il y a au moins deux articles) \n", " et aucune réduction sur le reste des articles \n", " (s’il y en a).\n", " Fonction qui en prend paramètre le tableau tab \n", " des prix des articles du panier d’un client \n", " et qui renvoie le total à payer lorsqu'on \n", " leur applique l’offre de bienvenue.\n", " \"\"\"\n", " somme = 0\n", " longueur = len(tab)\n", " if longueur > 0:\n", " somme = tab[0] * 0.8\n", " if longueur > 1:\n", " somme = somme + tab[1] * 0.7\n", " if longueur > 2:\n", " for i in range(2, longueur):\n", " somme = somme + tab[i]\n", " return somme\n", "\n", "#tests unitaires\n", "def test_offre_bienvenue():\n", " assert offre_bienvenue([]) == 0\n", " assert offre_bienvenue([100]) == 80.0\n", " assert offre_bienvenue([100, 200]) == 220.0\n", " assert offre_bienvenue([100, 200, 300]) == 520\n", " print(\"Tests unitaires réussis pour offre_bienvenue\")\n", "\n", "test_offre_bienvenue()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 2" ] }, { "cell_type": "code", "execution_count": 89, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour prix_solde\n" ] } ], "source": [ "def prix_solde(tab):\n", " \"\"\"\n", " Lors de la période des soldes, le site de vente propose les réductions suivantes :\n", " — si le panier contient 5 articles ou plus, une réduction globale de 50%,\n", " — si le panier contient 4 articles, une réduction globale de 40%,\n", " — si le panier contient 3 articles, une réduction globale de 30%,\n", " — si le panier contient 2 articles, une réduction globale de 20%,\n", " — si le panier contient 1 article, une réduction globale de 10%.\n", " Prend pour argument le tableau tab des prix des articles\n", " du panier d’un client et renvoyant le total des prix \n", " de ces articles lorsqu’on leur applique la réduction des soldes \n", " \"\"\"\n", " total = total_hors_reduction(tab)\n", " longueur = len(tab)\n", " if longueur >= 5:\n", " return total * 0.5\n", " elif longueur >= 4:\n", " return total * 0.6\n", " elif longueur >= 3:\n", " return total * 0.7\n", " elif longueur >= 2:\n", " return total * 0.8\n", " return total * 0.9 \n", "\n", "def test_prix_solde():\n", " assert prix_solde([]) == 0\n", " assert prix_solde([100]) == 90.0\n", " assert prix_solde([100, 200]) == 240.0\n", " assert prix_solde([100, 200, 300]) == 420.0\n", " assert prix_solde([100, 200, 300, 400]) == 600.0\n", " assert prix_solde([100, 200, 300, 400, 500]) == 750.0\n", " print(\"Tests unitaires réussis pour prix_solde\")\n", "\n", "test_prix_solde()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3) a)" ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour minimum\n" ] } ], "source": [ "def minimum(tab):\n", " \"\"\"\n", " Prend en paramètre un tableau de nombres tab\n", " Renvoie la valeur minimum de ce tableau \n", " \"\"\"\n", " if len(tab) > 0:\n", " mini = tab[0]\n", " for k in range(1, len(tab)):\n", " if tab[k] < mini:\n", " mini = tab[k]\n", " return mini\n", " \n", "def test_minimum():\n", " assert minimum([]) == None\n", " assert minimum([-1]) == -1\n", " assert minimum([-1, 1]) == -1\n", " assert minimum([-1,-2,1]) == -2\n", " assert minimum([-2,-1,1]) == -2\n", " assert minimum([1, -1, -2]) == -2\n", " print(\"Tests unitaires réussis pour minimum\")\n", "\n", "test_minimum()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 3) b)" ] }, { "cell_type": "code", "execution_count": 91, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour offre_bon_client\n" ] } ], "source": [ "def offre_bon_client(tab):\n", " \"\"\"\n", " Pour ses bons clients, le site de vente propose\n", " une offre promotionnelle, à partir de 2\n", " articles achetés, l’article le moins cher\n", " des articles commandés est offert\n", " Prend pour paramètre le tableau des prix\n", " des articles du panier d’un client\n", " et renvoie le total à payer lorsquon leur applique \n", " l'offre bon client. \n", " \"\"\"\n", " longueur = len(tab)\n", " if longueur >= 2:\n", " return total_hors_reduction(tab) - minimum(tab)\n", " return total_hors_reduction(tab) \n", "\n", "def test_offre_bon_client():\n", " assert offre_bon_client([]) == 0\n", " assert offre_bon_client([100]) == 100\n", " assert offre_bon_client([50, 200]) == 200\n", " assert offre_bon_client([100, 200, 300]) == 500\n", " assert offre_bon_client([200, 100, 300]) == 500\n", " assert offre_bon_client([200, 300, 100]) == 500\n", " print(\"Tests unitaires réussis pour offre_bon_client\")\n", "\n", "test_offre_bon_client()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 4) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Afin de diminuer le stock de ses articles dans ses entrepôts, l’entreprise imagine faire l’offre\n", "suivante à ses clients : en suivant l’ordre des articles dans le panier du client, elle considère les\n", "3 premiers articles et offre le moins cher, puis les 3 suivants et offre le moins cher et ainsi de\n", "suite jusqu’à ce qu’il reste au plus 2 articles qui n’ont alors droit à aucune réduction.\n", "Exemple : Si le panier du client contient un pantalon à 30,50 euros, un tee-shirt à 15 euros, une\n", "paire de chaussettes à 6 euros, une jupe à 20 euros, une paire de collants à 5 euros, une robe à\n", "35 euros et un short à 10,50 euros, ce panier est représenté par le tableau suivant :\n", "\n", " tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]\n", " \n", "Pour le premier groupe (le pantalon à 30,50 euros, le tee-shirt à 15 euros, la paire de chaussettes\n", "à 6 euros), l’article le moins cher, la paire de chaussettes à 6 euros, est offert. Pour le second\n", "groupe (la jupe à 20 euros, la paire de collants à 5 euros, la robe à 35 euros), la paire de collants\n", "à 5 euros est offerte.\n", "Donc le total après promotion de déstockage est 111 euros.\n", "On constate que le prix après promotion de déstockage dépend de l’ordre dans lequel se pré-\n", "sentent les articles dans le panier." ] }, { "cell_type": "code", "execution_count": 132, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tests unitaires réussis pour offre_bloc\n", "Tests unitaires réussis pour promotion_bloc_trois\n" ] } ], "source": [ "def offre_bloc(tab, debut_bloc):\n", " \"\"\"\n", " Renvoie le total pour un bloc de 3 articles consécutifs\n", " dans le panier, l'article avec le prix minimal étant déduit\n", " \"\"\"\n", " mini_bloc = tab[debut_bloc]\n", " somme_bloc = tab[debut_bloc]\n", " for k in range(debut_bloc + 1, debut_bloc + 3):\n", " if tab[k] < mini_bloc:\n", " mini_bloc = tab[k]\n", " somme_bloc = somme_bloc + tab[k]\n", " return somme_bloc - mini_bloc\n", "\n", "\n", "def test_offre_bloc():\n", " assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 0) == 45.5\n", " assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 3) == 55\n", " print(\"Tests unitaires réussis pour offre_bloc\")\n", "\n", "\n", "test_offre_bloc()\n", "\n", "\n", "\n", "def promotion_bloc_trois(tab):\n", " \"\"\"\n", " Prend en paramètre un tableau de prix d'articles dans un panier\n", " Renvoie le prix du panier après déduction du minimum des 3 premiers\n", " , du minimum des 3 suivants etc ...\n", " \"\"\"\n", " total = 0\n", " longueur = len(tab)\n", " debut_bloc = 0\n", " while longueur - debut_bloc > 2:\n", " total = total + offre_bloc(tab, debut_bloc)\n", " debut_bloc = debut_bloc + 3\n", " while longueur - debut_bloc > 0:\n", " total = total + tab[debut_bloc]\n", " debut_bloc = debut_bloc + 1\n", " return total\n", "\n", "def test_promotion_bloc_trois():\n", " assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 111\n", " assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0]) == 100.5\n", " assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5, 8, 6]) == 119\n", " print(\"Tests unitaires réussis pour promotion_bloc_trois\")\n", " \n", "test_promotion_bloc_trois()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 4) a) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Proposer un panier contenant les mêmes articles que ceux de l’exemple mais ayant un prix\n", "après promotion de déstockage différent de 111 euros." ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]\n" ] }, { "data": { "text/plain": [ "97.0" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from random import shuffle\n", "tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]\n", "tab2 = tab[:]\n", "print(tab2)\n", "shuffle(tab2)\n", "promotion_bloc_trois(tab2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 4) b) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(b) Proposer un panier contenant les mêmes articles mais ayant le prix après promotion de\n", "déstockage le plus bas possible." ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "96.0" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]\n", "tab3 = sorted(tab, reverse = True)\n", "promotion_bloc_trois(tab3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question 4) c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(c) Une fois ses articles choisis, quel algorithme le client peut-il utiliser pour modifier son\n", "panier afin de s’assurer qu’il obtiendra le prix après promotion de déstockage le plus bas\n", "possible ? On ne demande pas d’écrire cet algorithme." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "_On peut appliquer l'algorithme glouton ci-dessous :_\n", "\n", "* _pour le premier bloc on prend les trois articles avec les prix les plus élevés, le minimum de ces trois est un choix optimal si on n'applique la réduction qu'au premier bloc : en effet il faut forcément en prendre trois et le plus petit de trois donc on ne peut faire mieux que le troisième prix par ordre décroissant_\n", "* _pour le second bloc, on prend les trois articles avec les prix les plus élevés parmi ceux restants, le minimum de ces trois est un choix optimal si on n'applique la réduction qu'aux deux premiers blocs : en effet pour tout autre choix de deux blocs, en réordonnant événtuellement les blocs par ordre décroissant de leur minimum, on a forcément le minimum du premier bloc <= au minimum de notre premier choix glouton de bloc qui contient les trois plus grand prix, minimum du second bloc <= au minimum notre second choix glouton de bloc qui contient les plus grands de rangs 4, 5 et 6 ._\n", "* _etc tant qu'il reste au moins trois articles. On peut démontrer en itérant le raisonnment qu'à l'étape k le choix optimal local en prenant les trois plus grand prix restants pour constituer un nouveau bloc donne un choix optimal global si on se restreint au choix de k blocs ..._\n", "\n", "_Une façon de réaliser ces choix gloutons est de trier d'abord les valeurs ordre décroissant par exemple avec l'algorithme de tri par sélection et de sommer tous les prix dont l'index n'est pas de la forme 3 * k + 2 (troisième position dans le bloc donc minimum du bloc)_\n" ] }, { "cell_type": "code", "execution_count": 144, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test unitaire réussi pour bloc_trois_glouton\n", "Test unitaire réussi pour bloc_trois_glouton2\n" ] } ], "source": [ "def index_maxi(tab, debut):\n", " maxi = tab[debut]\n", " imaxi = debut\n", " for k in range(debut + 1, len(tab)):\n", " if tab[k] > maxi:\n", " maxi = tab[k]\n", " imaxi = k\n", " return imaxi\n", "\n", "def tri_selection_decroissant(tab):\n", " \"\"\"Tri par sélection par ordre décroissant\n", " en place\"\"\"\n", " for i in range(len(tab) - 1):\n", " imax = index_maxi(tab, i)\n", " tab[i], tab[imax] = tab[imax], tab[i]\n", "\n", "def promotion_bloc_trois_glouton(tab):\n", " copie_tab = tab[:]\n", " tri_selection_decroissant(copie_tab)\n", " return promotion_bloc_trois(copie_tab) \n", "\n", "def promotion_bloc_trois_glouton2(tab):\n", " total = 0\n", " longueur = len(tab)\n", " debut_bloc = 0\n", " while longueur - debut_bloc > 2:\n", " for i in range(debut_bloc, debut_bloc + 3):\n", " imax = index_maxi(tab, i)\n", " tab[i], tab[imax] = tab[imax], tab[i]\n", " total = total + tab[debut_bloc] + tab[debut_bloc + 1]\n", " debut_bloc = debut_bloc + 3\n", " while longueur - debut_bloc > 0:\n", " total = total + tab[debut_bloc]\n", " debut_bloc = debut_bloc + 1\n", " return total \n", "\n", "def test_promotion_bloc_trois_glouton():\n", " assert promotion_bloc_trois_glouton([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96\n", " print(\"Test unitaire réussi pour bloc_trois_glouton\")\n", " \n", "def test_promotion_bloc_trois_glouton2():\n", " assert promotion_bloc_trois_glouton2([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96\n", " print(\"Test unitaire réussi pour bloc_trois_glouton2\")\n", " \n", "test_promotion_bloc_trois_glouton()\n", "test_promotion_bloc_trois_glouton2()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 4" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [], "source": [ "ARBRE_VIDE = None\n", "\n", "def arbre(arbre_gauche, valeur, arbre_droit):\n", " return (arbre_gauche, valeur, arbre_droit)\n", "\n", "def racine(arbre):\n", " return arbre[1]\n", "\n", "def gauche(arbre):\n", " return arbre[0]\n", "\n", "def droit(arbre):\n", " return arbre[2]\n", "\n", "def est_vide(arbre):\n", " return arbre is ARBRE_VIDE\n", "\n" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [], "source": [ "B = arbre(\n", " arbre(\n", " arbre(\n", " arbre(ARBRE_VIDE, \"Marc\", ARBRE_VIDE)\n", " , \"Lea\"\n", " , arbre(ARBRE_VIDE, \"Lea\", ARBRE_VIDE)\n", " )\n", " ,\"Lea\"\n", " ,arbre(\n", " arbre(ARBRE_VIDE, \"Claire\", ARBRE_VIDE)\n", " , \"Theo\"\n", " , arbre(ARBRE_VIDE, \"Theo\", ARBRE_VIDE)\n", " )\n", " )\n", " , \"Lea\"\n", " ,arbre(\n", " arbre(\n", " arbre(ARBRE_VIDE, \"Marie\", ARBRE_VIDE)\n", " , \"Louis\"\n", " , arbre(ARBRE_VIDE, \"Louis\", ARBRE_VIDE)\n", " )\n", " ,\"Louis\"\n", " ,arbre(\n", " arbre(ARBRE_VIDE, \"Anne\", ARBRE_VIDE)\n", " , \"Anne\"\n", " , arbre(ARBRE_VIDE, \"Kevin\", ARBRE_VIDE)\n", " )\n", " )\n", ")" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((((None, 'Marc', None), 'Lea', (None, 'Lea', None)),\n", " 'Lea',\n", " ((None, 'Claire', None), 'Theo', (None, 'Theo', None))),\n", " 'Lea',\n", " (((None, 'Marie', None), 'Louis', (None, 'Louis', None)),\n", " 'Louis',\n", " ((None, 'Anne', None), 'Anne', (None, 'Kevin', None))))" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "B" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [], "source": [ "def vainqueur(arbre):\n", " return racine(arbre)" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'Lea'" ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "vainqueur(B)" ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [], "source": [ "def finale(arbre):\n", " return [racine(gauche(arbre)), racine(droit(arbre))]" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['Lea', 'Louis']" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "finale(B)" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [], "source": [ "def occurences(arb, nom):\n", " if est_vide(arb):\n", " return 0\n", " if racine(arb) == nom:\n", " return 1 + occurences(gauche(arb), nom) + occurences(droit(arb), nom)\n", " else:\n", " return occurences(gauche(arb), nom) + occurences(droit(arb), nom)" ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "occurences(B, \"Lea\")" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "occurences(B, \"Louis\")" ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [], "source": [ "def a_gagne(arb, nom):\n", " if est_vide(arb):\n", " return None\n", " #cas d'une feuille\n", " if (droit(arb) is ARBRE_VIDE \n", " and gauche(arb) is ARBRE_VIDE):\n", " return False\n", " #cas d'une victoire\n", " if racine(arb) == nom:\n", " return True\n", " #recherche récursive dans les sous-arbres\n", " return a_gagne(gauche(arb), nom) or a_gagne(droit(arb), nom) " ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a_gagne(B, \"Marc\")" ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 109, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a_gagne(B, \"Louis\")" ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [], "source": [ "def nombre_matchs_faux( arb , nom):\n", " \"\"\" arbre_competition , str -> int \"\"\"\n", " return occurences( arb , nom )" ] }, { "cell_type": "code", "execution_count": 111, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nombre_matchs_faux(B , \"Lea\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lea a gagné trois matchs et non quatre, de même Louis en a gagné deux et non trois" ] }, { "cell_type": "code", "execution_count": 112, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nombre_matchs_faux(B , \"Louis\")" ] }, { "cell_type": "code", "execution_count": 113, "metadata": {}, "outputs": [], "source": [ "def nombre_matchs_correct( arb , nom):\n", " \"\"\" arbre_competition , str -> int \"\"\"\n", " if est_vide(arb):\n", " return 0\n", " return occurences( arb , nom ) - 1" ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nombre_matchs_correct(B , \"Lea\")" ] }, { "cell_type": "code", "execution_count": 115, "metadata": {}, "outputs": [], "source": [ "def liste_joueurs ( arb ):\n", " \"\"\" arbre_competition -> tableau \"\"\"\n", " #cas d'une arbre vide\n", " if est_vide ( arb ):\n", " return []\n", " #feuille\n", " elif est_vide(gauche(arb)) and est_vide(droit(arb)):\n", " return [racine(arb)]\n", " else :\n", " return liste_joueurs(gauche(arb)) + liste_joueurs(droit(arb))" ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['Marc', 'Lea', 'Claire', 'Theo', 'Marie', 'Louis', 'Anne', 'Kevin']" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "liste_joueurs(B)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercice 5" ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [], "source": [ "def creer_pile_vide():\n", " return []\n", "\n", "def est_vide_pile(pile):\n", " return len(pile) == 0\n", "\n", "def empiler(pile, element):\n", " pile.append(element)\n", " \n", "def depiler(pile):\n", " return pile.pop()" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [], "source": [ "FILE_VIDE = None\n", "\n", "class Noeud:\n", " \n", " def __init__(self, valeur, suivant):\n", " self._valeur = valeur\n", " self._suivant = suivant\n", " \n", " def __str__(self):\n", " return f\"({self._valeur}, {str(self._suivant)})\"\n", " \n", "class File:\n", " \n", " def __init__(self):\n", " self._premier = None\n", " self._dernier = None\n", " self._taille = 0\n", " \n", " def __len__(self):\n", " return self._taille\n", " \n", " def est_vide(self):\n", " return self._taille == 0\n", " \n", " def enfiler(self, element):\n", " nouveau = Noeud(element, None)\n", " if self.est_vide():\n", " self._premier = self._dernier = nouveau\n", " else:\n", " self._dernier._suivant = nouveau\n", " self._dernier = nouveau\n", " self._taille += 1\n", " \n", " def defiler(self):\n", " if not self.est_vide():\n", " valeur = self._premier._valeur\n", " self._premier = self._premier._suivant\n", " self._taille -= 1\n", " if self.est_vide():\n", " self._dernier = None\n", " return valeur\n", " \n", " def __str__(self):\n", " return str(self._premier)\n", " \n", " \n", " \n", " \n", " \n", "def creer_file_vide():\n", " return File()\n", "\n", "def est_vide_file(file):\n", " return file.est_vide()\n", "\n", "def enfiler(file, element):\n", " file.enfiler(element)\n", " \n", "def defiler(file):\n", " return file.defiler()" ] }, { "cell_type": "code", "execution_count": 119, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'(jaune, (rouge, (jaune, (vert, (rouge, None)))))'" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F = creer_file_vide()\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"rouge\")\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"vert\")\n", "enfiler(F, \"rouge\")\n", "str(F)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On inverse une file en la transférant dans une pile" ] }, { "cell_type": "code", "execution_count": 120, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "jaune\n", "['jaune']\n", "rouge\n", "['jaune', 'rouge']\n", "jaune\n", "['jaune', 'rouge', 'jaune']\n", "vert\n", "['jaune', 'rouge', 'jaune', 'vert']\n", "rouge\n", "['jaune', 'rouge', 'jaune', 'vert', 'rouge']\n", "['jaune', 'rouge', 'jaune', 'vert', 'rouge']\n" ] } ], "source": [ "P = creer_pile_vide()\n", "while not(est_vide_file(F)):\n", " e = defiler(F)\n", " print(e)\n", " empiler(P, e)\n", " print(P)\n", "print(P)" ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [], "source": [ "def taille_file(F):\n", " G = creer_file_vide()\n", " compteur = 0\n", " while not (est_vide_file(F)):\n", " enfiler(G , defiler(F)) \n", " compteur += 1\n", " while not (est_vide_file(G)):\n", " enfiler(F, defiler(G)) \n", " return compteur" ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(jaune, (rouge, (jaune, (vert, (rouge, None)))))\n" ] }, { "data": { "text/plain": [ "5" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F = creer_file_vide()\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"rouge\")\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"vert\")\n", "enfiler(F, \"rouge\")\n", "print(F)\n", "taille_file(F)" ] }, { "cell_type": "code", "execution_count": 123, "metadata": {}, "outputs": [], "source": [ "def former_pile(F, debug = True):\n", " P1 = creer_pile_vide()\n", " while not(est_vide_file(F)):\n", " e = defiler(F)\n", " if debug:print(e)\n", " empiler(P1, e)\n", " if debug:print(P1)\n", " if debug:print(P1)\n", " P2 = creer_pile_vide()\n", " while not(est_vide_pile(P1)):\n", " empiler(P2, depiler(P1))\n", " return P2" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(jaune, (rouge, (jaune, (vert, (rouge, None)))))\n", "jaune\n", "['jaune']\n", "rouge\n", "['jaune', 'rouge']\n", "jaune\n", "['jaune', 'rouge', 'jaune']\n", "vert\n", "['jaune', 'rouge', 'jaune', 'vert']\n", "rouge\n", "['jaune', 'rouge', 'jaune', 'vert', 'rouge']\n", "['jaune', 'rouge', 'jaune', 'vert', 'rouge']\n" ] }, { "data": { "text/plain": [ "['rouge', 'vert', 'jaune', 'rouge', 'jaune']" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F = creer_file_vide()\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"rouge\")\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"vert\")\n", "enfiler(F, \"rouge\")\n", "print(F)\n", "former_pile(F)" ] }, { "cell_type": "code", "execution_count": 125, "metadata": {}, "outputs": [], "source": [ "def nb_elements(F, elt):\n", " G = creer_file_vide()\n", " compteur = 0\n", " while not (est_vide_file(F)):\n", " e = defiler(F)\n", " enfiler(G , e) \n", " if e == elt:\n", " compteur += 1\n", " while not (est_vide_file(G)):\n", " enfiler(F, defiler(G)) \n", " return compteur" ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(jaune, (rouge, (jaune, (vert, (rouge, None)))))\n" ] }, { "data": { "text/plain": [ "2" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F = creer_file_vide()\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"rouge\")\n", "enfiler(F, \"jaune\")\n", "enfiler(F, \"vert\")\n", "enfiler(F, \"rouge\")\n", "print(F)\n", "nb_elements(F, \"jaune\")" ] }, { "cell_type": "code", "execution_count": 127, "metadata": {}, "outputs": [], "source": [ "def verifier_contenu(F, nb_rouge, nb_vert, nb_jaune):\n", " return (nb_elements(F, \"rouge\") <= nb_rouge\n", " and nb_elements(F, \"vert\") <= nb_vert\n", " and nb_elements(F, \"vejaune\") <= nb_jaune)" ] }, { "cell_type": "code", "execution_count": 128, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 128, "metadata": {}, "output_type": "execute_result" } ], "source": [ "verifier_contenu(F, 2, 2,1)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3.6.9 64-bit", "language": "python", "name": "python36964bit6c276e138c8d4d719f159ddc377af459" }, "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.5" } }, "nbformat": 4, "nbformat_minor": 4 }