Aller au contenu

Rendu de monnaie

Cet exercice s'inspire d'un exercice de Nicolas Revéret

On s'intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d'une liste donnée de valeurs de pièces (et/ou de billets).

Le système monétaire est donné sous forme d'une liste décroissante fixée :

🐍 Script Python
VALEURS = [100, 50, 20, 10, 5, 2, 1]

On supposera qu'il n'y a pas de limitation quant au nombre de pièces de chaque valeur.

Exemples : Rendre 68 ou 291

  • Pour rendre 68, on peut rendre la liste de pièces [1, 2, 5, 10, 50].
  • Pour rendre 291, on peut rendre la liste de pièces [1, 20, 20, 50, 100, 100].

Avec ce système monétaire, on ne peut pas rendre la monnaie avec moins de pièces.

Un algorithme glouton permet, dans ce cas (chose non générale), d'obtenir la solution optimale :

  • On rend une pièce de la plus grande valeur possible, puis on rend la monnaie sur le reste. Ce qui est une procédure récursive !

Exercice

Coder une fonction rendu_monnaie qui prend en paramètre un entier n et qui renvoie la liste décroissante des pièces obtenue avec cet algorithme glouton récursif.

Cette fonction prend un deuxième argument : la liste des valeurs, par défaut il vaut VALEURS et devra être conservé.

Cette fonction prend un troisième argument : un entier i qui correspond à l'indice de la pièce dernièrement utilisée. Par défaut, il vaut 0 et peut donc être omis lors des tests.

🐍 Script Python
>>> rendu_monnaie(68)
[1, 2, 5, 10, 50]
>>> rendu_monnaie(291)
[1, 20, 20, 50, 100, 100]
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013x/.r;nbylaeu)dV63Am(P+02è-U],59fq78 _o=pcwgv41`kRéhtsSàL[ji:E050o0l0!0k0+0j0#0K0P0j0k0#0#0N010!0+0O010406050#0m0t0t0k0e0i040$0M0j0m110M0g050c181a1c1e160O04051u1n1x0c1u160o0+0S0_0{0}0 0Z0+0R0Z0j1L0Z0!14050;0h0j0l1G0|0~011K1M1O1M0!1U1W1S0!0e1v0!0Z1Y1I010G0?0l0g0k0t0l010_1h0#0O0k0g0 0y1S23251?1!1_1W1|1~140a0K0v0e0M0O0M0#0+1k0g0K0/210e0e0l0P2s1n2a0g1v0c1;2F1.1:1/1T0o2c0 1O0g1{2p1S1D1F0`1Z2P0+2R0g0M2V1S0O2y1v2D2F2-17242t2X1@2$0e1b0j140K0U2C2;152:2b2?1!2^2`2|0y2 25312D2O01360k2{040K0r3a2E163d340 3g3i0K0T3m3c2;3e3s2|0E3w3o3y3q3f0M2_3h2|0q3D322=1H353I373j0I3N3p3Q3r3S3K3j0J3W3F3Y3H3J3t0F3(333*3A040U0x3/3P2Y3+3T0U2~1o303E3:3{3=0U39403b423`2@3!3i0U3l483n3O3z4d140U3v4h3x434c3,4m3C4p4a4k4t3?3M4w4j3G453V4C3X444l3?3%4H3)4J4z0U3.4p1y2+1n2V2I0o1:2N3G0P2%1 1v4X1w4V2/4T4%0/2,4O1@0W140/0G3w4D3*0Q2|4|4I2@0G142y0g0o0m0L0t1l1|0+0l514?1!13040u5g4r35141m4T525i140D3w0K4}44140S3h0l0m0e0#5m4b1!0M140N5H3z140p0s0(0-0B0X0$5N3G5j5v4p5x5s3r140+5X3*5K045M5r5h0 0t0+143^5:5n0 5j0n0,3_3e4 3j0K645+3{0#0o14016b603G682|640K0X1{0S0M5e0K0{6o0+0#0!1X0P2m6r0#256t2u0l0^0O0+0z0P6C0K2o5E0K560o2y0K5q2-4x6e6963640A0K0k0S2z0K0m2t3h0R3I2r0Z1~0K0R0j0M1j1l6M0Y0P5E2q4{4N5{016f6W0K6Y1j0?6r6z6o0k6q6s1X0/0^0V5B1W6|0V6d3*726h740K0%6J1c110e6B6o002!1D6H0K0V0+7l6 5I0 7o6h6b013D7p5y4@5)6~2-5$5;3f5p5w7Q5J5L5/7U7!5=5@045_2/5%015j5 4w7p7P7/4^042y0!5E6R307V705j0)0C7O6h7)017`0l0@5f5`7I7:147=6S7@877/0g140b7Z7/5-7%80888n047i5D5F661@838B5o045*8e3e5j857?8k818f7`0+7T8u8m8o8q7W5-020R0!0f8W708w7 3b887;868N8l7W0P0U14030K6^2R6J5D0!7t0^6N6P6!6$6p6E6G1X8H8j8/8:707`7|7~8%8f8w6N595b0g5d8d7.7W5j5l8I4E7Y9u3*5Z9h5O8x5C6|8E5|5u9A9v8G9I5,140w9L3{5?4m9F8g040n8.7@888a8c9T8-8M9b8O3e8=8@8_2t0O8}6M1{6O1X930P7a6J6F7C0+0K0H0m9 0#0l0e7b951i0^0P0Z0z6P2v6p1O7d9X8/8v556C6t9P1@8sap8F9k5a5c0=9p308,149t9q8(9w7(8r140Aas5(048p9x3{9z5#al9C7j8AaO8C9HaR8U9KaW5t9V5w9*4$8?048^0k0O9:0j6_6{5F8Raj8NaS2yaia$0 5-0d9T8wa/9:579$aBb38Va 9U9W5#a{7/9,a-9.6Z0*6?6A959}6uac6P7s6p1_8*3n9)657_am7}0ebx3ja|anay491n4:0l2F2*bN4W1E4Y2I2L2G0k1VbQ0c4X16b!0:0=0@04.