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

.128013bq,9vià3o_x;jlpwf( g0]6-)2s1+8Vûené4èE[m5tCLRPhk:c.a=rySIu/7d050-0H0Q0!0g0o0B0t0Y0o0!0B0B0#010Q0g0p010406050B0*0O0O0!0$0%040(0j0o0*110j0I0t020!0O0p0m0t0T0H1b0$0c0*0H0B050+181a1c1e160p04051J1C1M0+1J160-0g0f0_0{0}0 0V0g0u0V0o1!0V0Q14050;0b0o0H1V0|0~011Z1#1%1#0Q1-1/1+0Q0$1K0Q0V0_1h0B0p0!0I0 0A011;1X010r0?0H0I1p0H1+27292e1?2h1/2k0O2m040a0t0U0$0j0p0j0B0g1k1m0/250$0$0H0Y2H1C2o0I1K0+232T2022211,0-2q0 1%0I2j2E1+1S1U0`1=2%0g2)0I0j2-1+0p2M1K2R2T2~17281m2/2f2@0$1b0o140t0C2Q3215312p341?36383a0A3d293f2R2$013k0!39040t0i3o2S163r3i0 3u3w0t0K3A3q323s3G3a0P3K3C3M3E3t0j373v3a0x3R3g331W3j3W3l3x0,3#3D3(3F3*3Y3x0E3.3T3:3V3X3H0e3_3h3{3O040C0v403%2:3|3+0C3c1D3e3S4149430C3n4e3p4g48353=3w0C3z4m3B3$3N4r140C3J4v3L4h4q3}4A3Q4D4o4y4H443!4D1N2|1C2-2W0-222#3U0Y2^2w0.1T1K2{0H2}3e3K054!0/4,4F3j140U0)0M0R0M0(3K0t4x3U0j140#4 513{13040N4.3/490O0g4A0v464Q5d2f590d565l1?5f140P5j305q0 5n5p3`5e5g040A5v4-5x015z4D505I5s445G3p57495K2~5M5B2f5O4J5w5X1?5U3e5W4?0 5O4l5#5+5J145o5L5S5Y5D4d5/4p5%140w3R064L4Z0C14030t0F0H0$2F1l0t0!0f2N250I0Y0!0Q0J2k2P4K5^1?0W140/0r5c5$0 0q3a6x5:0I0r142M0I0-0*0k0O1l2k0g0H0k2M0Y6C5}5y140s6U3N140!6R2j0-2M6Z3U5(3p5*6V3t140g6+58140z0X3R0t6}6/3s6t040g6w5@5I0I6#6%6I6*756y0153040#557c5:5O5Q2S6r6W046{4K6~7t6 3U712M0Q0*0$0I5A5:590N607s6~7o6;040p7D6:7f7i5V7K77044_4{4}6@5T145b5k7d7U6?7%7E5 6|7J5I71737O6!7M7?5214020o0Q0m7R5)7T786H6)0H7Z5m147r2~067u7/7d7x0:7A7C7j6:7F874@7^7+8l7-8k3s7f0D7_426G6(6K6M0I6O6Q6S8n7p6Y8q7@6$847b7S5I7f0y8x4i147N8K6,5=8T356=8H5;040z7.6}7K710H0@868X6^7q8+7u8-8z7z7B8!8o848B6N0=8F2N8%598J5|8L7985968Z8t3U7)8~0 8v9i015O5{5H7d598*4K628`046v8%6A3x8%6E8z6I918D939d04989p6D836(8O9L8r8)8a4f7t9v7y8i9l7U906L926P6%6T8=7!9J9B9N7a8;998Y045?8P7d7l9I9s8b1C4:4+4Ra10+4U1C0Q4Wa62Z2U0!1.a34U1I4=6:2M0O0k0r0!0W6Q0V0i141u1w1y1A0t9T5R1P3f1J0S0!0t6g6b0g6d2{0J0B2j6m1:0-290^0{2K6S2H0t1A0Q0_8/1/6e6g0Y6i6k6m6oaI0I0Z060S1:4!0GaZ2JaY0t1y0!6)6l0gav0d0t0h0_0!0*aM0t6J25a^0t2(0J0=2Mba1:aT4!6j6l6nb01la:0)0o0tam1jaX1m0H0r0r0:b30o3W0^2J0Y0V0!av6e0p0p8/0t0$0J0Y7A2F0rb36S2C6P0$be002jaM0Oadbj0^0f3v0HbVb-0t0p0g0L0Yaw0-0J0nb5901A0Z1NaB04btaFb7aZ5fb;0laX0}0!0%6abjbvbhbkaEaG6c1m6f6h4/4#3s1^1$1(1*ah8LbO6(4.0+a03x2D7A0t0j0b0Q2j0gb$0*330jbdbfclc3aA16a40: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

.128013bq,9vià3o_x;jlpwf( g0]6-)2s1+8ûené4èE[m5tCLRPhk:c.a=rySIu/7d050,0G0P0Z0g0o0B0t0X0o0Z0B0B0!010P0g0p010406050B0)0N0N0Z0#0$040%0j0o0)100j0H0t020Z0N0p0m0t0S0G1a0#0c0)0G0B050*17191b1d150p04051I1B1L0*1I150,0g0f0^0`0|0~0U0g0u0U0o1Z0U0P13050:0b0o0G1U0{0}011Y1!1$1!0P1,1.1*0P0#1J0P0U0^1g0B0p0Z0H0~0A011:1W010r0=0G0H1o0G1*26282d1=2g1.2j0N2l040a0t0T0#0j0p0j0B0g1j1l0.240#0#0G0X2G1B2n0H1J0*222S1 21201+0,2p0~1$0H2i2D1*1R1T0_1;2$0g2(0H0j2,1*0p2L1J2Q2S2}16271l2.2e2?0#1a0o130t0C2P3114302o331=3537390A3c283e2Q2#013j0Z38040t0i3n2R153q3h0~3t3v0t0J3z3p313r3F390O3J3B3L3D3s0j363u390x3Q3f321V3i3V3k3w0+3!3C3%3E3)3X3w0E3-3S3/3U3W3G0e3^3g3`3N040C0v3 3$2/3{3*0C3b1C3d3R4048420C3m4d3o4f47343;3v0C3y4l3A3#3M4q130C3I4u3K4g4p3|4z3P4C1M2{1B2,2V0,212!3T0X2@2v0-1S1J2`0G2|3d3J054T0.4#4E3i130T0(0L0Q0L0%3J0t4w3T0j130!4^4`3`12040M4%3.480N0g4z0v454J562e520d4 5e1=58130O5c2 5j0~5g5i3_5759040A5o4$5q015s4C4_5B5l435z3o50485D2}5F5u2e5H4I5p5Q1=5N3d5P4,0~5H4k5U5!5C135h5E5L5R5w4c5(4o5W130w3Q064n3r0V130.0r555V0~0q39625)0H0r132L0H0,0)0k0N1k2j0g0G0k2L0X675?5r130s6p3M130Z6m2i0,2L6u3T5X3o5Z6q3s130g6C51130z0W3Q0t6R6G5}6J615-5B0H6w6y6d6B6X63014|040!4~6(5)5H5J2R5.5@046P4C066S6}6T3T5~042L0P0)0#0H5t5)520M5_6{6}6@3E130p786H6+6.5O7f6I044/4;4?6L5M13545d6)6Z046K7y795^6Q6S7o710g6W7n6Y7h7j3r6+020o0P0m7m5Y7o7A6x6c6A0G7u5f136`2}6|6~6R7I6b0/75776/6H7a7(4-047i7D7_7F7^7Q130D7P3T7A7#6f6h0H6j6l6n7{6r046t7 6v047!6z6%7M6)6+0y86417O8k6D5+8u4h6J8g5*040z7G7/5B710G0?7%8x6M6_8H6~7:727=768A347;6d8a6i0;8e2M8D528j5=8l8n6$8N8-8y045,8q688C824{848X5k5:8*6N5`5|705 0G7L5A6)653w8D698Z6e6g8$6k928i9e6!7#8p9a7E8F7+4e7e8J7;748W8|8v8U8!9i8c8%6y6o8O7v9m9K8Y8m6#7$9l8^7X5G5w6=4+808F3!0*4)4!4K9(0*4N1B0P4P9-2Y2T0Z1-9*4N1H9Y3r2L0N0k0r0Z0V6l0U0i131t1v1x1z0t9u5K1O3e1I0R0Z0t0f0G0#2E1k0t2`0I0B2i0P0I1/0,280@0`2J6n2G0t1z0P0^8L1.0t0Zak0X240H0X0Zau2j2G0Y060R1/4T0FaG2IaF0t1x0Z6AaR0ga90d0t0h0^0Z0)as0t6e24a!0t2%0I0;2La_1/aA4TaPaR0IaT0g1kaV0(0o0ta01iaE1l980r0/a/0o3V0@2I0X0U0Za9aK0p0p8L0t0#0I0X752E0ra/6n2B6k0#a}002ias0N9@b20@0f3u0GbEbSap0g0K0Xaa0,0I0na;891z0Y1Maf04bdaja?aG58bW0laE0|0Z0$alb2bfb0b3aiakamba1laL2M4_9%3r1@1#1%1)9{876wbx6z4%9$4U3w2C750t0j0b0P2i0gbL0)320ja|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

.128013ben,49viE[3+mo5_tC;Phkjlpwf(: cg.a=ry0S6I]-u/72)s18d050!0c0r0I0i0y0X0E0F0y0I0X0X0J010r0i0z010406050X0S0n0n0I0K0L040N0o0y0S0^0o0d050T0 1113150}0z04051l1e1o0T1l0}0!0i0h0-0/0;0?0v0i0G0v0y1C0v0r0{050(0b0y0c1x0:0=011B1D1F1D0r1L1N1J0r0K1m0r0v0-180X0z0I0d0?0V011P1z010B0*0c0d0I0n0c1J1,1.1?1R1_1N1|1~0{0a0E0u0K0o0z0o0X0i1b0d0E0$1*0K0K0c0F2j1e210d1m0T1(2w1#1%1$1K0!230?1F0d1{2g1J1u1w0.1Q2G0i2I0d0o2M1J0z2p1m2u2w2!0~1-2k2O1@2T0K120y0{0E0Y2t2(0|2%222*1R2,2.2:0V2?1.2^2u2F012}0I2/040E0l312v0}342{0?37390E0f3d332(353j2:0p3n3f3p3h360o2-382:0O3u2_2)1y2|3z2~3a0U3E3g3H3i3J3B3a0Z3N3w3P3y3A3k0g3V2`3X3r040Y0M3$3G2P3Y3K0Y2=1f2@3v3%3/3)0Y303@323_3.2+3R390Y3c3 3e3F3q440{0Y3m483o3`433Z4d3t4g414b4k3*3D4g1p2Y1e2M2z0!1%2E3x0F2U1 1m4x1n4v2$4t4D0$2Z3W3{0{0u0P0j0s0j0N3n0E4a3x0o0{0J4Y4!3X0`040k3n4*3/0n0i4d0M3,4t3O3/4,0e4)4{1@4=0{0p4_2$501R4}4 4P514?040V552@4:1@594g4Z570?523*5g325i580{4~5l5t5o5d4m565b5u045w2!5m5D5z0{3~5C4i5E5G2@5I5O5K3*4/5n014,0Q3u064o3x0w0{0$0B5W5J010A2:5-5T360B0{2p0d0!0S0q0n1c1|0i0c0q2p0F5=425E0C673q0{0I641{0!2p6b3x5k5H5y360{0i6j4+5v5a5?0d5*0c0x6e5`5|6r4|0{0W0D3u0E6J5S680?5)040i5,5x5X6w046A6g6i6S5.4$040J4(6Z5?5p5r2v6n4,6H4n6K6=6L356O2p0r0S0K1d6)6M6o040$6z6f5{0S6I6K6n6U0z6u706#6(6m6T4R4T4V4X4`5.4,4.7n6v6p6D5j0{5!6;795X6O6Q7d6c047c6 356#020y0r0t7g5R7a6d756h0c7u5E6:2!066?7z5.6U736W767V0?6#0H7+710I0z0z6g7/4,6a7r707b7^6F787!6n6_0%6|6~7h7$5_6g5}5 0d6163657~047`5N7|7R6B6Y875?6#0R7D3x7}7{356l7P7i6P8h5Q326@8u6x746B778w6k7 7y6J820{0c0+7U8L6s047X3^7!8P7A896{6}8t3(89765~600)8f2q8h8j5h8A7)7T8C8*4Q8B7H4#0{0m8}5c4d8|908+726y8`8K8k8x8N7Y5$8Q9a6R9e3x5:3a7/0d5^048J8.8d8:8?9q8m6X8U9m8W6G808F3X838(868z889t8a9v8e6f668V6E8i9z6V7S8o8^7o6t984;5d6,4O5?8y8E6.0{0k0Q0W3E0T4M0c2w2X9{4w1v4y2z2C2x0I1M9~0T4x0}a80%0)0+04.