Rendu de monnaie (récursif)

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 de billets.

Le système de monnaie est donné sous forme d'une liste de valeurs décroissantes définie de façon globale et qui peut être utilisée dans les fonctions sans être donnée en paramètre.

Système monétaire utilisé
PIECES = [100, 50, 20, 10, 5, 2, 1]

On suppose qu'il n'y a pas de limitation quant au nombre de pièces et billets disponibles.

On souhaite, étant donnée une somme à rendre, déterminer la plus petite liste de pièces dont la somme est égale à celle-ci.

L'algorithme utilisé est le suivant :

  • On regarde les valeurs possibles en partant de la plus grande;
  • Si on peut rendre la valeur considérée, on le fait.
  • Sinon on passe à la valeur inférieure.
  • On continue tant que l'on n'a pas tout rendu.

La fonction rendu_monnaie prend en paramètre un entier a_rendre qui correspond à la somme à rendre et renvoie la liste des valeurs rendues, dans l'ordre décroissant.

Cette fonction utilise une fonction récursive rendu_monnaie_rec qui implémente l'algorithme ci-dessus.

Les deux façons d'écrire rendu_monnaie_rec

On propose 2 façons d'écrire la fonction rendu_monnaie_rec :

Dans cette version, la fonction rendu_monnaie_rec prend 2 paramètres :

  • a_rendre : un entier qui correspond à la somme à rendre.
  • i : un entier qui correspond à l'indice de la valeur considérée dans PIECES.

Elle renvoie la liste des valeurs rendues, dans l'ordre décroissant.

Si on peut rendre PIECES[i], on concatène cette valeur devant la liste obtenue par l'appel récursif.

Cette version est plus simple à écrire, mais la concaténation nécessite de recopier toutes les valeurs de la liste à chaque fois, ce qui donne un coût quadratique à cette implémentation.

Dans cette version, la fonction rendu_monnaie_rec prend 3 paramètres :

  • a_rendre : un entier qui correspond à la somme à rendre.
  • i : un entier qui correspond à l'indice de la valeur considérée dans PIECES.
  • deja_rendu : la liste des valeurs déjà rendues.

Elle renvoie la liste des valeurs rendues, dans l'ordre décroissant.

Si on peut rendre la valeur PIECES[i], on la rajoute à la liste deja_rendu en utilisant append avant de faire l'appel récursif.

Cette version est un peu plus compliquée à écrire mais en utilisant append, le coût reste linéaire.

Exemples 
>>> rendu_monnaie(68)
[50, 10, 5, 2, 1]
>>> rendu_monnaie(291)
[100, 100, 50, 20, 20, 1]

###(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 : 10/10

.128013fe)à61ipmSvk(q5rxd;VPo/aR lé+[C8Ly7I_3:-tg.=swc,èû]h2nEb0j94u050s0c0P0y0h0B0T0A0V0B0y0T0T0S010P0h0i010406050T0-0j0j0y0q0I040k0w0B0-110w0$0A020y0j0i0t0A0z0c1b0q0o0-0c0T050x181a1c1e160i04051J1C1M0x1J160s0h0l0_0{0}0 0!0h0Q0!0B1!0!0P14050;0(0B0c1V0|0~011Z1#1%1#0P1-1/1+0P0q1K0P0!0_1h0T0i0y0$0 0#011;1X010b0?0c0$1p0c1+27292e1?2h1/2k0j2m040a0A0v0q0w0i0w0T0h1k1m0/250q0q0c0V2H1C2o0$1K0x232T2022211,0s2q0 1%0$2j2E1+1S1U0`1=2%0h2)0$0w2-1+0i2M1K2R2T2~17281m2/2f2@0q1b0B140A0g2Q3215312p341?36383a0#3d293f2R2$013k0y39040A0M3o2S163r3i0 3u3w0A0,3A3q323s3G3a0p3K3C3M3E3t0w373v3a0f3R3g331W3j3W3l3x0J3#3D3(3F3*3Y3x0G3.3T3:3V3X3H0+3_3h3{3O040g0)403%2:3|3+0g3c1D3e3S4149430g3n4e3p4g48353=3w0g3z4m3B3$3N4r140g3J4v3L4h4q3}4A3Q4D4o4y4H443!4D1N2|1C2-2W0s222#3U0V2^2w0.1T1K2{0c2}3e3K054!0/4,4F3j140v0K0%0F0%0k3K0A4x3U0w140S4 513{13040E4.3/490j0h4A0)464Q5d2f590W565l1?5f140p5j305q0 5n5p3`5e5g040#5v4-5x015z4D505I5s445G3p57495K2~5M5B2f5O4J5w5X1?5U3e5W4?0 5O4l5#5+5J145o5L5S5Y5D4d5/4p5%140Z3R064L4Z0g14030A0u0c0q2F1l0A0y0l2N250$0V0y0P0C2k2P4K5^1?0m140/0b5c5$0 0U3a6x5:0$0b142M0$0s0-0L0j1l2k0h0c0L2M0V6C5}5y140n6U3N140y6R2j0s2M6Z3U5(3p5*6V3t140h6+58140d0N3R0A6}6/3s6t040h6w5@5I0$6#6%6I6*756y0153040S557c5:5O5Q2S6r6W046{4K6~7t6 3U712M0P0-0q0$5A5:590E607s6~7o6;040i7D6:7f7i5V7K77044_4{4}6@5T145b5k7d7U6?7%7E5 6|7J5I71737O6!7M7?5214020B0P0t7R5)7T786H6)0c7Z5m147r2~067u7/7d7x0:7A7C7j6:7F874@7^7+8l7-8k3s7f0D7_426G6(6K6M0$6O6Q6S8n7p6Y8q7@6$847b7S5I7f0O8x4i147N8K6,5=8T356=8H5;040d7.6}7K710c0@868X6^7q8+7u8-8z7z7B8!8o848B6N0=8F2N8%598J5|8L7985968Z8t3U7)8~0 8v9i015O5{5H7d598*4K628`046v8%6A3x8%6E8z6I918D939d04989p6D836(8O9L8r8)8a4f7t9v7y8i9l7U906L926P6%6T8=7!9J9B9N7a8;998Y045?8P7d7l9I9s8b1C4:4+4Ra10x4U1C0P4Wa62Z2U0y1.a34U1I4=6:2M0j0L0b0y0m6Q0!0M141u1w1y1A0A9T5R1P3f1J0H0y0A6g6b0h6d2{0C0T2j6m1:0s290^0{2K6S2H0A1A0P0_8/1/6e6g0V6i6k6m6oaI0$0R060H1:4!0YaZ2JaY0A1y0y6)6l0hav0W0A0e0_0y0-aM0A6J25a^0A2(0C0=2Mba1:aT4!6j6l6nb01la:0K0B0Aam1jaX1m0c0b0b0:b30B3W0^2J0V0!0yav6e0i0i8/0A0q0C0V7A2F0bb36S2C6P0qbe002jaM0jadbj0^0l3v0cbVb-0A0i0h0X0Vaw0s0C0*b5901A0R1NaB04btaFb7aZ5fb;0raX0}0y0I6abjbvbhbkaEaG6c1m6f6h4/4#3s1^1$1(1*ah8LbO6(4.0xa03x2D7A0A0w0(0P2j0hb$0-330wbdbfclc3aA16a40:0=0@04.

###(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 : 10/10

.128013fe)à61ipmSvk(q5rxd;Po/aR l+é[C8Ly7I_3:-tg.=swc,èû]h2nEb0j94u050s0c0O0x0h0A0S0z0U0A0x0S0S0R010O0h0i010406050S0,0j0j0x0q0H040k0v0A0,100v0#0z020x0j0i0t0z0y0c1a0q0o0,0c0S050w17191b1d150i04051I1B1L0w1I150s0h0l0^0`0|0~0Z0h0P0Z0A1Z0Z0O13050:0%0A0c1U0{0}011Y1!1$1!0O1,1.1*0O0q1J0O0Z0^1g0S0i0x0#0~0!011:1W010b0=0c0#1o0c1*26282d1=2g1.2j0j2l040a0z0u0q0v0i0v0S0h1j1l0.240q0q0c0U2G1B2n0#1J0w222S1 21201+0s2p0~1$0#2i2D1*1R1T0_1;2$0h2(0#0v2,1*0i2L1J2Q2S2}16271l2.2e2?0q1a0A130z0g2P3114302o331=3537390!3c283e2Q2#013j0x38040z0L3n2R153q3h0~3t3v0z0+3z3p313r3F390p3J3B3L3D3s0v363u390f3Q3f321V3i3V3k3w0I3!3C3%3E3)3X3w0F3-3S3/3U3W3G0*3^3g3`3N040g0(3 3$2/3{3*0g3b1C3d3R4048420g3m4d3o4f47343;3v0g3y4l3A3#3M4q130g3I4u3K4g4p3|4z3P4C1M2{1B2,2V0s212!3T0U2@2v0-1S1J2`0c2|3d3J054T0.4#4E3i130u0J0$0E0$0k3J0z4w3T0v130R4^4`3`12040D4%3.480j0h4z0(454J562e520V4 5e1=58130p5c2 5j0~5g5i3_5759040!5o4$5q015s4C4_5B5l435z3o50485D2}5F5u2e5H4I5p5Q1=5N3d5P4,0~5H4k5U5!5C135h5E5L5R5w4c5(4o5W130Y3Q064n3r0m130.0b555V0~0T39625)0#0b132L0#0s0,0K0j1k2j0h0c0K2L0U675?5r130n6p3M130x6m2i0s2L6u3T5X3o5Z6q3s130h6C51130d0M3Q0z6R6G5}6J615-5B0#6w6y6d6B6X63014|040R4~6(5)5H5J2R5.5@046P4C066S6}6T3T5~042L0O0,0q0#5t5)520D5_6{6}6@3E130i786H6+6.5O7f6I044/4;4?6L5M13545d6)6Z046K7y795^6Q6S7o710h6W7n6Y7h7j3r6+020A0O0t7m5Y7o7A6x6c6A0c7u5f136`2}6|6~6R7I6b0/75776/6H7a7(4-047i7D7_7F7^7Q130B7P3T7A7#6f6h0#6j6l6n7{6r046t7 6v047!6z6%7M6)6+0N86417O8k6D5+8u4h6J8g5*040d7G7/5B710c0?7%8x6M6_8H6~7:727=768A347;6d8a6i0;8e2M8D528j5=8l8n6$8N8-8y045,8q688C824{848X5k5:8*6N5`5|705 0c7L5A6)653w8D698Z6e6g8$6k928i9e6!7#8p9a7E8F7+4e7e8J7;748W8|8v8U8!9i8c8%6y6o8O7v9m9K8Y8m6#7$9l8^7X5G5w6=4+808F3!0w4)4!4K9(0w4N1B0O4P9-2Y2T0x1-9*4N1H9Y3r2L0j0K0b0x0m6l0Z0L131t1v1x1z0z9u5K1O3e1I0G0x0z0l0c0q2E1k0z2`0C0S2i0O0C1/0s280@0`2J6n2G0z1z0O0^8L1.0z0xak0U240#0U0xau2j2G0Q060G1/4T0XaG2IaF0z1x0x6AaR0ha90V0z0e0^0x0,as0z6e24a!0z2%0C0;2La_1/aA4TaPaR0CaT0h1kaV0J0A0za01iaE1l980b0/a/0A3V0@2I0U0Z0xa9aK0i0i8L0z0q0C0U752E0ba/6n2B6k0qa}002ias0j9@b20@0l3u0cbEbSap0h0W0Uaa0s0C0)a;891z0Q1Maf04bdaja?aG58bW0raE0|0x0Halb2bfb0b3aiakamba1laL2M4_9%3r1@1#1%1)9{876wbx6z4%9$4U3w2C750z0v0%0O2i0hbL0,320va|a~c3b.ae159+0/0;0?04.

###(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 : 10/10

.128013fe)61i_p3m:Svk-(5rtg.=swcd;,Po/]ha2nE bl0+j[C948uy7I050A0c0t0I0g0O0x0M0z0O0I0x0x0w010t0g0i010406050x0X0k0k0I0s0Y040m0E0O0X0^0E0K050F0 1113150}0i04051l1e1o0F1l0}0A0g0n0-0/0;0?0H0g0u0H0O1C0H0t0{050(0N0O0c1x0:0=011B1D1F1D0t1L1N1J0t0s1m0t0H0-180x0i0I0K0?0J011P1z010b0*0c0K0I0k0c1J1,1.1?1R1_1N1|1~0{0a0M0D0s0E0i0E0x0g1b0K0M0$1*0s0s0c0z2j1e210K1m0F1(2w1#1%1$1K0A230?1F0K1{2g1J1u1w0.1Q2G0g2I0K0E2M1J0i2p1m2u2w2!0~1-2k2O1@2T0s120O0{0M0f2t2(0|2%222*1R2,2.2:0J2?1.2^2u2F012}0I2/040M0j312v0}342{0?37390M0V3d332(353j2:0r3n3f3p3h360E2-382:0e3u2_2)1y2|3z2~3a0Z3E3g3H3i3J3B3a0W3N3w3P3y3A3k0U3V2`3X3r040f0P3$3G2P3Y3K0f2=1f2@3v3%3/3)0f303@323_3.2+3R390f3c3 3e3F3q440{0f3m483o3`433Z4d3t4g414b4k3*3D4g1p2Y1e2M2z0A1%2E3x0z2U1 1m4x1n4v2$4t4D0$2Z3W3{0{0D0!0L0T0L0m3n0M4a3x0E0{0w4Y4!3X0`040S3n4*3/0k0g4d0P3,4t3O3/4,0C4)4{1@4=0{0r4_2$501R4}4 4P514?040J552@4:1@594g4Z570?523*5g325i580{4~5l5t5o5d4m565b5u045w2!5m5D5z0{3~5C4i5E5G2@5I5O5K3*4/5n014,0G3u064o3x0o0{0$0b5W5J010y2:5-5T360b0{2p0K0A0X0h0k1c1|0g0c0h2p0z5=425E0q673q0{0I641{0A2p6b3x5k5H5y360{0g6j4+5v5a5?0K5*0c0R6e5`5|6r4|0{0d0l3u0M6J5S680?5)040g5,5x5X6w046A6g6i6S5.4$040w4(6Z5?5p5r2v6n4,6H4n6K6=6L356O2p0t0X0s1d6)6M6o040$6z6f5{0X6I6K6n6U0i6u706#6(6m6T4R4T4V4X4`5.4,4.7n6v6p6D5j0{5!6;795X6O6Q7d6c047c6 356#020O0t0B7g5R7a6d756h0c7u5E6:2!066?7z5.6U736W767V0?6#0v7+710I0i0i6g7/4,6a7r707b7^6F787!6n6_0%6|6~7h7$5_6g5}5 0K6163657~047`5N7|7R6B6Y875?6#0p7D3x7}7{356l7P7i6P8h5Q326@8u6x746B778w6k7 7y6J820{0c0+7U8L6s047X3^7!8P7A896{6}8t3(89765~600)8f2q8h8j5h8A7)7T8C8*4Q8B7H4#0{0Q8}5c4d8|908+726y8`8K8k8x8N7Y5$8Q9a6R9e3x5:3a7/0K5^048J8.8d8:8?9q8m6X8U9m8W6G808F3X838(868z889t8a9v8e6f668V6E8i9z6V7S8o8^7o6t984;5d6,4O5?8y8E6.0{0S0G0d3E0F4M0c2w2X9{4w1v4y2z2C2x0I1M9~0F4x0}a80%0)0+04.