{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercices du livre - Chapitre 10 - solutions\n",
    "\n",
    "---\n",
    "\n",
    "<table class=\"appbclp1\">\n",
    "<tr> <td style=\"font-weight: bold!;\">auteurs :</td><td style=\"text-align: left!;\">Laurent Pointal &lt;<a href=\"mailtp:laurent.pointal@limsi.fr\">laurent.pointal@limsi.fr</a>&gt; &amp; Bob Cordeau &lt;<a href=\"pycours@kordeo.eu\">pycours@kordeo.eu</a>&gt; </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">licence :</td><td style=\"text-align: left!;\">Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0) </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">source :</td><td style=\"text-align: left!;\"><a href=\"https://github.com/lpointal/appbclp\">https://github.com/lpointal/appbclp</a></td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">description :</td><td style=\"text-align: left!;\">Les programmes dans ce Notebook Jupyter servent de support au livre <span style=\"font-style: italic!;\">« Python 3 - Apprendre à  programmer dans l'écosystème Python»</span>, édition Dunod, dans lequel les différentes sections sont expliquées </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">url :</td><td style=\"text-align: left!;\"><a href=\"https://www.dunod.com/sciences-techniques/python-3\">https://www.dunod.com/EAN/9782100809141</a></td> </tr>\n",
    "</table>\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 1\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def distance(s, t):\n",
    "    \"\"\"Retourne la distance d'édition entre deux chaînes.\"\"\"\n",
    "    if len(s) == 0:\n",
    "        return len(t)\n",
    "    elif len(t) == 0:\n",
    "        return len(s)\n",
    "    else:\n",
    "        ecart = 0\n",
    "        if s[-1] != t[-1]:\n",
    "            ecart = 1\n",
    "        d1 = distance(s[:-1], t) + 1\n",
    "        d2 = distance(s, t[:-1]) + 1\n",
    "        d3 = distance(s[:-1], t[:-1]) + ecart\n",
    "\n",
    "        return min(d1, d2, d3)\n",
    "\n",
    "# Programme principal ==========================================================\n",
    "s = input(\"\\nEntrez une première chaîne : \")\n",
    "s = s.lower()\n",
    "t = input(\"Entrez une seconde chaîne  : \")\n",
    "t = t.lower()\n",
    "print(f'\\nDistance d\\'édition entre \"{s}\" et \"{t}\" : {distance(s, t)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 2\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def somme_rec():\n",
    "    \"\"\"Calcule récursivement le total des entrées.\"\"\"\n",
    "    f = input(\"Entrez un nombre (saisie vide pour quitter) : \")\n",
    "\n",
    "    return 0 if not f else float(f) + somme_rec()\n",
    "\n",
    "# Programme principal ==========================================================\n",
    "print(f\"\\nTotal des saisies : {somme_rec()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 3\n",
    "\n",
    "# Globale ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "couples = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'), (100, 'C'),\n",
    "           (90, 'XC'), (50, 'L'), (40, 'XL'), (10, 'X'), (9, 'IX'), (5, 'V'),\n",
    "           (4, 'IV'), (1, 'I')]\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def dec2romain(num):\n",
    "    romain = ''\n",
    "\n",
    "    while num > 0:\n",
    "        for i, r in couples:\n",
    "            while num >= i:\n",
    "                romain += r\n",
    "                num -= i\n",
    "\n",
    "    return romain\n",
    "\n",
    "# Programme principal =========================================================\n",
    "nums = [12, 482, 1490, 2242]\n",
    "\n",
    "for num in nums:\n",
    "    print(f\"{num} => {dec2romain(num)}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 4\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def est_palindrome(s):\n",
    "    \"\"\"Détermine récursivement si la chaîne <s> est un palindrome.\"\"\"\n",
    "    if len(s) <= 1:\n",
    "        return True\n",
    "\n",
    "    return (s[0] == s[len(s) - 1]) and (est_palindrome(s[1:len(s) - 1]))\n",
    "\n",
    "# Programme principal ==========================================================\n",
    "ch = input(\"\\nEntrez une chaîne : \")\n",
    "ch = ch.lower()\n",
    "print(f\"\"\"{ch} {\"est\" if est_palindrome(ch) else \"n'est pas\"} un palindrome.\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 5\n",
    "\n",
    "def deux_index(liste, cible):\n",
    "    verif = {}\n",
    "    for i, nbr in enumerate(liste):\n",
    "        if cible - nbr in verif:\n",
    "            return (verif[cible - nbr], i)\n",
    "        verif[nbr] = i\n",
    "\n",
    "liste = (10, 20, 10, 40, 50, 60, 70)\n",
    "cible = 60\n",
    "index1, index2 = deux_index(liste, cible)\n",
    "print(f\"\\ncible = {cible}\\n\\tindice = {index1} : {liste[index1]}\"\n",
    "      f\"\\n\\tindice = {index2} : {liste[index2]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 6\n",
    "\n",
    "# Globale ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "MAX = 8\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def calcul(d, n):\n",
    "    \"\"\"Calcul récursif du nombre de façons de faire <n> avec <d> dés.\"\"\"\n",
    "    resultat, debut = 0, 1\n",
    "    if (d == 1) or (n == d) or (n == 6*d):  # conditions terminales\n",
    "        return 1\n",
    "    else:                   # sinon appels récursifs\n",
    "        if n > 6*(d-1):     # optimisation importante\n",
    "            debut = n - 6*(d-1)\n",
    "\n",
    "        for i in range(debut, 7):\n",
    "            if n == i:\n",
    "                break\n",
    "            resultat += calcul(d-1, n-i)\n",
    "    return resultat\n",
    "\n",
    "# Programme principal =========================================================\n",
    "d = int(input(\"Nombre de dés [2 .. {:d}] : \".format(MAX)))\n",
    "while not(d >= 2and d <= MAX):\n",
    "    d = int(input(\"Nombre de dés [2 .. {:d}], s.v.p. : \".format(MAX)))\n",
    "\n",
    "n = int(input(\"Entrez un entier [{:d} .. {:d}] : \".format(d, 6*d)))\n",
    "while not(n >= d and n <= 6*d):\n",
    "    n = int(input(\"Entrez un entier [{:d} .. {:d}], s.v.p. : \".format(d, 6*d)))\n",
    "\n",
    "print(\"Il y a {:d} façon(s) de faire {:d} avec {:d} dés.\".format(calcul(d, n), n, d))"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
