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

.128013n1.P8Sp(àevèkId3+:aûts2C,Roblu=h 54é07_9[6]xyfm-)cEirwL;/qgVj050p0k0v0t0!0D0w0H0Y0D0t0w0w0F010v0!0h010406050w0E0V0V0t0#0T040g0B0D0E110B0b0H020t0V0h0(0H0A0k1b0#0*0E0k0w050)181a1c1e160h041C1J051M0)1M1O1J160p0!0l0_0{0}0 0G0!0+0G0D1$0G0v14050;0C0D0k1X0|0~011#1%1)1%0v1/1;1-0v0C0B0p1e1.0#1K0v0G0_1h0w0h0t0b0 0x011?1Z010U0?0k0b1p0k1-2e2g2l1^2o1;2r0V2t040a0H0e0#0B0h0B0w0!1k1m0/2c0#0#0k0Y2O1C2v0b1K0)2a2!0v2827290p2x0 1)0b2q2L1-1U1W0`1@2.0!2:0b241V1-0h2T1K2Y2!35172f1m2_2m2~0#1b0D140H0c2X3915382w3b1^3d3f3h0x3k2g3m2Y2-013r0t3g040H0q3v2Z163y3p0 3B3D0H0J3H3x393z3N3h0I3R3J3T3L3A0B3e3C3h0Q3Y3n3a1Y3q3%3s3E0M3,3K3/3M3;3)3E0f3^3!3`3$3(3O0O403o423V040c0L473.2`433=0c3j1D3l3Z484g4a0c3u4l3w4n4f3c3|3D0c3G4t3I3-3U4y140c3Q4C3S4o4x444H3X4K4v4F4O4b3+4K1L331C2@2%0p2+3z0Y242D0.1V1K320k343l3R054*0/4=4M3q140e0o0Z0y0Z0g3R0H4E3#0B140F55574213040P4@3_4g0V0!4H0L4d4X5j2m5f0z5c5r1^5l140I5p375w0 5t5v415k5m040x5B4?5D015F4K565O5y4b5M3w5d4g5Q355S5H2m5U4Q5C5%1^5!3l5$4|0 5U4s5+5;5P145u5R5Y5(5J4k5^4w5-140R3Y064S3#0Y0c14030H0,0k0#2M1l0H0t0l2U2c0b0Y0t0v0K2r2W4R5~1^0n140/0U5i5,0 0$3h6E5_0b0U142T0b0p0E0N0V1l2r0!0k0N2T0Y6J635E140i6#3U140t6Y2q0p2T6*3#5.3w5:6$3A140!6=5e140X0s3Y0H746_3z6A040!6D5}5O0b6,6.6P6;7c6F0159040F5b7j5_5U5W2Z6y6%04724R757A763#782T0v0E0#0b5G5_5f0P667z757v6{040h7K6`7m7p5#7R7e044 51536~5Z145h5q7k7#6}7.7L65737Q5O787a7V6+7T7}5814020D0v0(7Y5/7!7f6O6:0k7*5s147y35067B7_7k7E0:7H7J7q6`7M8e4}7 7=8s7@8r3z7m0r80496N6/6R6T0b6V6X6Z8u7w6)8x7~6-8b7i7Z5O7m0W8E4p147U8R6?5{8!3c6|8O5`040X7^747R780k0@8d8(6 7x8=7B8@8G7G7I8+8v8b8I6U0=8M2U8.5f8Q628S7g8c9d8*8A3#7:950 8C9p015U615N7k5f8;4R6891046C8.6H3E8.6L8G6P988K9a9k049f9w6K8a6/8V9S8y8:8h4m7A9C7F8p9s7#976S996W6.6!8|7+9Q9I9U7h8{9g8)045|8W7k7s9P9z8i1C4_4;4Ya80)4#1C0v4%ad2)2#23252%0t1:aa4#1I4{6`2T0V0N0U0t0n6X0G0q141u1w1y1A0H9!5X1P3m1J0%0t0H6n6i0!6k320K0w2q6t1=0p2g0^0{2R6Z2O0H1A0v0_8_1;6l6n0Y6p6r6t6vaS0b0d060%1=4*0ua-2Qa,0H1y0t6:6s0!aF0z0H0j0_0t0EaW0H6Q2cb20H2/0K0=2Tbk1=a%4*6q6s6uba1la}0o0D0Haw1ja+1m0k0U0U0:bd0D3%0^2Q0Y0G0taF6l0h0h8_0H0#0K0Y7H2M0Ubd6Z2J6W0#bo002qaW0Vanbt0^0l3C0kb)b`0H0h0!0m0YaG0p0K0-bf971A0d1LaL04bDaPbha-5lb~0Sa+0}0t0T6hbtbFbrbuaOaQ6j1m6m6o4^4+3z1`1(1*1,ar8SbY6/4@0)a73E2K7H0H0B0C0v2q0!b:0E3a0BbnbpcvcdaK16ab0: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

.128013n1.P8Sp(àevèkId3+:aûts2C,Roblu=h 54é07_9[6]xyfm-)cEirwL;/qgj050p0k0v0t0!0D0w0H0Y0D0t0w0w0F010v0!0h010406050w0E0V0V0t0#0T040g0B0D0E100B0b0H020t0V0h0(0H0A0k1a0#0*0E0k0w050)17191b1d150h041B1I051L0)1L1N1I150p0!0l0^0`0|0~0G0!0+0G0D1#0G0v13050:0C0D0k1W0{0}011!1$1(1$0v1.1:1,0v0C0B0p1d1-0#1J0v0G0^1g0w0h0t0b0~0x011=1Y010U0=0k0b1o0k1,2d2f2k1@2n1:2q0V2s040a0H0e0#0B0h0B0w0!1j1l0.2b0#0#0k0Y2N1B2u0b1J0)292Z0v2726280p2w0~1(0b2p2K1,1T1V0_1?2-0!2/0b231U1,0h2S1J2X2Z34162e1l2^2l2}0#1a0D130H0c2W3814372v3a1@3c3e3g0x3j2f3l2X2,013q0t3f040H0q3u2Y153x3o0~3A3C0H0J3G3w383y3M3g0I3Q3I3S3K3z0B3d3B3g0Q3X3m391X3p3$3r3D0M3+3J3.3L3:3(3D0f3@3Z3_3#3%3N0O3 3n413U040c0L463-2_423;0c3i1C3k3Y474f490c3t4k3v4m4e3b3{3C0c3F4s3H3,3T4x130c3P4B3R4n4w434G3W4J1K321B2?2$0p2*3y0Y232C0-1U1J310k333k3Q054Z0.4+4L3p130e0o0Z0y0Z0g3Q0H4D3!0B130F4~504112040P4-3^4f0V0!4G0L4c4Q5c2l580z555k1@5e130I5i365p0~5m5o405d5f040x5u4,5w015y4J4 5H5r4a5F3v564f5J345L5A2l5N4P5v5W1@5T3k5V4=0~5N4r5!5*5I135n5K5R5X5C4j5.4v5$130R3X064u3y0n130.0U5b5#0~0$3g685/0b0U132S0b0p0E0N0V1k2q0!0k0N2S0Y6d5|5x130i6v3T130t6s2p0p2S6A3!5%3v5)6w3z130!6I57130X0s3X0H6X6M636P675?5H0b6C6E6j6H6%690152040F546.5/5N5P2Y5@5}046V4J066Y736Z3!64042S0v0E0#0b5z5/580P5 71736}3L130h7e6N6;6@5U7l6O044^4`4|6R5S135a5j6/6)046Q7E7f5~6W6Y7u770!6$7t6(7n7p3y6;020D0v0(7s5(7u7G6D6i6G0k7A5l13703472746X7O6h0/7b7d6^6N7g7.4?047o7J7 7L7~7W130r7V3!7G7+6l6n0b6p6r6t816x046z856B047*6F6-7S6/6;0W8c487U8q6J5;8A4o6P8m5:040X7M7^5H770k0?7-8D6S6 8N747_787{7c8G3b7`6j8g6o0;8k2T8J588p5{8r8t6,8T8?8E045=8w6e8I88518a8%5q5_8:6T606276650k7R5G6/6b3D8J6f8)6k6m8,6q988o9k6*7+8v9g7K8L7;4l7k8P7`7a8$928B8!8*9o8i8-6E6u8U7B9s9Q8(8s6+7,9r8~7%5M5C6{4;868L3+0)4/4*4R9.0)4U1B0v4W9?2(2!22242$0t1/9:4U1H9(3y2S0V0N0U0t0n6r0G0q131t1v1x1z0H9A5Q1O3l1I0%0t0H0l0k0#2L1k0H310K0w2p0v0K1;0p2f0@0`2Q6t2N0H1z0v0^8R1:0H0tat0Y2b0b0Y0taD2q2N0d060%1;4Z0uaP2PaO0H1x0t6Ga!0!ai0z0H0j0^0t0EaB0H6k2ba-0H2.0K0;2Sb21;aJ4ZaYa!0Ka$0!1ka(0o0D0Ha91iaN1l9e0U0/a{0D3$0@2P0Y0G0taiaT0h0h8R0H0#0K0Y7b2L0Ua{6t2I6q0#b6002paB0Va0bb0@0l3B0kbNb#ay0!0m0Yaj0p0K0,a}8f1z0d1Kao04bmasa aP5eb)0SaN0|0t0Taubbbob9bcaratavbj1laU2T4 9-3y1_1%1)1+a48d6CbG6F4-9,4!3D2J7b0H0B0C0v2p0!bU0E390Bb5b7ccb`an159;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

.128013nb1lu=h. P4580S7p9_[6(e]yvfm-k)cEIirwd;/3+:gats2C,jo050M0x0U0T0J0e0V0j0G0e0T0V0V0g010U0J0r010406050V0f0C0C0T0K0z040p0!0e0f0^0!0b050O0 1113150}0r041e1l051o0O1o1q1l0}0M0J0A0-0/0;0?0h0J0S0h0e1E0h0U0{050(0c0e0x1z0:0=011D1F1H1F0U1N1P1L0U0c0!0M151M0K1m0U0h0-180V0r0T0b0?0W011R1B010B0*0x0b0T0C0x1L1?1^1}1T201P23250{0a0j0k0K0!0r0!0V0J1b0b0j0$1;0K0K0x0G2q1e280b1m0O1/2D0U1-1,1.0M2a0?1H0b222n1L1w1y0.1S2N0J2P0b1)1x1L0r2w1m2B2D2+0~1@2r2V1~2!0K120e0{0j0d2A2/0|2.292;1T2?2^2`0W2}1^2 2B2M01340T2_040j0P382C0}3b320?3e3g0j0l3k3a2/3c3q2`0m3u3m3w3o3d0!2@3f2`0v3B302:1A333G353h0q3L3n3O3p3Q3I3h0n3U3D3W3F3H3r0s3$313(3y040d0o3-3N2W3)3R0d2|1f2~3C3.3_3:0d373~39403^2=3Y3g0d3j463l3M3x4b0{0d3t4f3v414a3*4k3A4n484i4r3;3K4n1n2)1e2T2G0M2K3c0G1)261m4E1p4C2-4A4J0$2*3%420{0k0I0H0X0H0p3u0j4h3E0!0{0g4(4*3(0`040u3u4:3_0C0J4k0o3?4A3V3_4=0Y4/511~4{0{0m4 2-561T53554V574|040W5b2~4_1~5f4n4)5d0?583;5m395o5e0{545r5z5u5j4t5c5h5A045C2+5s5J5F0{455I4p5K5M2~5O5U5Q3;4^5t014=0y3B064v3E0E0{0$0B5$5P010L2`5?5Z3d0B0{2w0b0M0f0t0C1c230J0x0t2w0G5{495K0w6d3x0{0T6a220M2w6h3E5q5N5E3d0{0J6p4;5B5g5|0b5:0x0Z6k60626x520{0F0R3B0j6P5Y6e0?5/040J5=5D5%6C046G6m6o6Y5@4,040g4.6)5|5v5x2C6t4=6N4u6Q6{6R3c6U2w0U0f0K1d6/6S6u040$6F6l610f6O6Q6t6!0r6A766+6.6s6Z4X4Z4#4%505@4=4@7t6B6v6J5p0{5*6`7f5%6U6W7j6i047i753c6+020e0U0N7m5X7g6j7b6n0x7A5K6_2+066|7F5@6!796$7c7#0?6+0i7;770T0r0r6m7^4=6g7x767h7~6L7e7*6t6 0%72747n7,5 6m63650b67696b8404805T827X6H6(8d5|6+0D7J3E83813c6r7V7o6V8n5W396}8A6D7a6H7d8C6q857E6P880{0x0+7!8R6y047%3 7*8V7G8f71738z3/8f7c64660)8l2x8n8p5n8G7/7Z8I8:4W8H7N4+0{0Q935i4k92968;786E908Q8q8D8T7(5,8W9g6X9k3E5_3h7^0b5~048P8@8j8_8|9w8s6%8!9s8$6M868L3(898.8c8F8e9z8g9B8k6l6c8#6K8o9F6#7Y8u8~7u6z9e4`5j6=4U5|8E8K6@0{0u0y0F3L0O4S0x2D2(a14D1x4F2G2I2E1(1*2G0T1Oa40O4E0}ah0%0)0+04.