{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# [ALGO1 : Introduction à l'algorithmique](https://perso.crans.org/besson/teach/info1_algo1_2019/)\n", "\n", "- [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : https://perso.crans.org/besson/teach/info1_algo1_2019/\n", "- Magistère d'Informatique de Rennes - ENS Rennes - Année 2019/2020\n", "- Intervenants :\n", " + Cours : [Lilian Besson](https://perso.crans.org/besson/)\n", " + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/)\n", "- Références :\n", " + [Open Data Structures](http://opendatastructures.org/ods-python.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Cours Magistral 6\n", "\n", "- Ce cours traite des algorithmes gloutons.\n", "- Ce notebook sera concis, comparé aux précédents." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Rendu de monnaie\n", "\n", "- Voir https://en.wikipedia.org/wiki/Change-making_problem ou https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_rendu_de_monnaie" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "def binary_coin_change(x, R):\n", " \"\"\"Coin change\n", "\n", " :param x: table of non negative values\n", " :param R: target value\n", " :returns bool: True if there is a non negative linear combination\n", " of x that has value R\n", " :complexity: O(n*R)\n", " \"\"\"\n", " if int(R) != R: # we work with 1/100\n", " R = int(R * 100)\n", " x = [int(xi * 100) for xi in x]\n", " b = [False] * (R + 1)\n", " b[0] = True\n", " for xi in x:\n", " for s in range(xi, R + 1):\n", " b[s] |= b[s - xi]\n", " return b[R]" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "def constructive_coin_change(values_of_coins, sum_to_find):\n", " \"\"\"Coin change\n", "\n", " :param values_of_coins: table of non negative values\n", " :param sum_to_find: target value\n", " :returns bool: True if there is a non negative linear combination\n", " of x that has value R\n", " :complexity: O(n*R)\n", " \"\"\"\n", " with_cents = False\n", " if int(sum_to_find) != sum_to_find: # we work with 1/100\n", " with_cents = True\n", " sum_to_find = int(sum_to_find * 100)\n", " values_of_coins = [int(pi * 100) for pi in values_of_coins]\n", " n = len(values_of_coins)\n", " number_of_coins = [0] * n\n", " values_of_coins = sorted(values_of_coins, reverse=True)\n", " current_sum = sum_to_find\n", " for i, pi in enumerate(values_of_coins):\n", " assert pi > 0, \"Error: a coin with value zero.\"\n", " if pi > current_sum:\n", " continue # coin is too large, we continue\n", " how_much_pi, rest = divmod(current_sum, pi) # x // y, x % y\n", " number_of_coins[i] = how_much_pi\n", " print(\"For current sum = {}, coin = {}, was used {} times, now sum = {}.\".format(current_sum, pi, how_much_pi, rest))\n", " current_sum = rest\n", " if current_sum != 0:\n", " raise ValueError(\"Could not write {} in the coin system {} with greedy method.\".format(sum_to_find, values_of_coins))\n", " if with_cents:\n", " values_of_coins = [round(pi / 100, 2) for pi in values_of_coins]\n", " return number_of_coins, values_of_coins" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec les pièces des euros :" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "For current sum = 1612, coin = 1000, was used 1 times, now sum = 612.\n", "For current sum = 612, coin = 500, was used 1 times, now sum = 112.\n", "For current sum = 112, coin = 100, was used 1 times, now sum = 12.\n", "For current sum = 12, coin = 10, was used 1 times, now sum = 2.\n", "For current sum = 2, coin = 2, was used 1 times, now sum = 0.\n" ] }, { "data": { "text/plain": [ "([0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0],\n", " [500.0,\n", " 200.0,\n", " 100.0,\n", " 50.0,\n", " 20.0,\n", " 10.0,\n", " 5.0,\n", " 2.0,\n", " 1.0,\n", " 0.5,\n", " 0.2,\n", " 0.1,\n", " 0.05,\n", " 0.02,\n", " 0.01])" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "billets = [500, 200, 100, 50, 20, 10, 5]\n", "pieces = [2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]\n", "euros = billets + pieces\n", "\n", "binary_coin_change(euros, 16.12)\n", "constructive_coin_change(euros, 16.12)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "For current sum = 16, coin = 10, was used 1 times, now sum = 6.\n", "For current sum = 6, coin = 5, was used 1 times, now sum = 1.\n" ] }, { "ename": "ValueError", "evalue": "Couldnot write 16 in the coin system [500, 200, 100, 50, 20, 10, 5] with greedy method.", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m