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

.128013uk /iCxERP)j=h-a,1èn8]fI.Vr6mc;pày72tl0qsebwS_L53(év[:4dg+9oû050(0Q0L0q0f0M0P0d0E0M0q0P0P0n010L0f0G010406050P0b0D0D0q0B0I040T0,0M0b110,0u0d020q0D0G0F0d0j0Q1b0B0O0b0Q0P050e181a1c1e160G041C1J051M0e1M1O1J160(0f0!0_0{0}0 0o0f0)0o0M1$0o0L14050;0R0M0Q1X0|0~011#1%1)1%0L1/1;1-0L0R0,0(1e1.0B1K0L0o0_1h0P0G0q0u0 0K011?1Z010x0?0Q0u1p0Q1-2e2g2l1^2o1;2r0D2t040a0d0k0B0,0G0,0P0f1k1m0/2c0B0B0Q0E2O1C2v0u1K0e2a2!0L2827290(2x0 1)0u2q2L1-1U1W0`1@2.0f2:0u241V1-0G2T1K2Y2!35172f1m2_2m2~0B1b0M140d0s2X3915382w3b1^3d3f3h0K3k2g3m2Y2-013r0q3g040d0X3v2Z163y3p0 3B3D0d0%3H3x393z3N3h0W3R3J3T3L3A0,3e3C3h0C3Y3n3a1Y3q3%3s3E0J3,3K3/3M3;3)3E0v3^3!3`3$3(3O0+403o423V040s0N473.2`433=0s3j1D3l3Z484g4a0s3u4l3w4n4f3c3|3D0s3G4t3I3-3U4y140s3Q4C3S4o4x444H3X4K4v4F4O4b3+4K1L331C2@2%0(2+3z0E242D0.1V1K320Q343l3R054*0/4=4M3q140k0y0i0g0i0T3R0d4E3#0,140n55574213040#4@3_4g0D0f4H0N4d4X5j2m5f0r5c5r1^5l140W5p375w0 5t5v415k5m040K5B4?5D015F4K565O5y4b5M3w5d4g5Q355S5H2m5U4Q5C5%1^5!3l5$4|0 5U4s5+5;5P145u5R5Y5(5J4k5^4w5-140w3Y064S3#0E0s14030d0A0Q0B2M1l0d0q0!2U2c0u0E0q0L0Z2r2W4R5~1^0c140/0x5i5,0 0S3h6E5_0u0x142T0u0(0b0U0D1l2r0f0Q0U2T0E6J635E140Y6#3U140q6Y2q0(2T6*3#5.3w5:6$3A140f6=5e140l0$3Y0d746_3z6A040f6D5}5O0u6,6.6P6;7c6F0159040n5b7j5_5U5W2Z6y6%04724R757A763#782T0L0b0B0u5G5_5f0#667z757v6{040G7K6`7m7p5#7R7e044 51536~5Z145h5q7k7#6}7.7L65737Q5O787a7V6+7T7}5814020M0L0F7Y5/7!7f6O6:0Q7*5s147y35067B7_7k7E0:7H7J7q6`7M8e4}7 7=8s7@8r3z7m0*80496N6/6R6T0u6V6X6Z8u7w6)8x7~6-8b7i7Z5O7m0p8E4p147U8R6?5{8!3c6|8O5`040l7^747R780Q0@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;4Ya80e4#1C0L4%ad2)2#23252%0q1:aa4#1I4{6`2T0D0U0x0q0c6X0o0X141u1w1y1A0d9!5X1P3m1J0V0q0d6n6i0f6k320Z0P2q6t1=0(2g0^0{2R6Z2O0d1A0L0_8_1;6l6n0E6p6r6t6vaS0u0z060V1=4*0-a-2Qa,0d1y0q6:6s0faF0r0d0H0_0q0baW0d6Q2cb20d2/0Z0=2Tbk1=a%4*6q6s6uba1la}0y0M0daw1ja+1m0Q0x0x0:bd0M3%0^2Q0E0o0qaF6l0G0G8_0d0B0Z0E7H2M0xbd6Z2J6W0Bbo002qaW0Danbt0^0!3C0Qb)b`0d0G0f0t0EaG0(0Z0mbf971A0z1LaL04bDaPbha-5lb~0ha+0}0q0I6hbtbFbrbuaOaQ6j1m6m6o4^4+3z1`1(1*1,ar8SbY6/4@0ea73E2K7H0d0,0R0L2q0fb:0b3a0,bnbpcvcdaK16ab0: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

.128013uk /iCxERP)j=h-a,1èn8]fI.r6mc;pày72tl0qsebwS_L53(év[:4dg+9oû050%0P0K0q0f0L0O0d0D0L0q0O0O0n010K0f0F010406050O0b0C0C0q0A0H040S0+0L0b100+0u0d020q0C0F0E0d0j0P1a0A0N0b0P0O050e17191b1d150F041B1I051L0e1L1N1I150%0f0Z0^0`0|0~0o0f0(0o0L1#0o0K13050:0Q0L0P1W0{0}011!1$1(1$0K1.1:1,0K0Q0+0%1d1-0A1J0K0o0^1g0O0F0q0u0~0J011=1Y010x0=0P0u1o0P1,2d2f2k1@2n1:2q0C2s040a0d0k0A0+0F0+0O0f1j1l0.2b0A0A0P0D2N1B2u0u1J0e292Z0K2726280%2w0~1(0u2p2K1,1T1V0_1?2-0f2/0u231U1,0F2S1J2X2Z34162e1l2^2l2}0A1a0L130d0s2W3814372v3a1@3c3e3g0J3j2f3l2X2,013q0q3f040d0W3u2Y153x3o0~3A3C0d0$3G3w383y3M3g0V3Q3I3S3K3z0+3d3B3g0B3X3m391X3p3$3r3D0I3+3J3.3L3:3(3D0v3@3Z3_3#3%3N0*3 3n413U040s0M463-2_423;0s3i1C3k3Y474f490s3t4k3v4m4e3b3{3C0s3F4s3H3,3T4x130s3P4B3R4n4w434G3W4J1K321B2?2$0%2*3y0D232C0-1U1J310P333k3Q054Z0.4+4L3p130k0y0i0g0i0S3Q0d4D3!0+130n4~504112040!4-3^4f0C0f4G0M4c4Q5c2l580r555k1@5e130V5i365p0~5m5o405d5f040J5u4,5w015y4J4 5H5r4a5F3v564f5J345L5A2l5N4P5v5W1@5T3k5V4=0~5N4r5!5*5I135n5K5R5X5C4j5.4v5$130w3X064u3y0c130.0x5b5#0~0R3g685/0u0x132S0u0%0b0T0C1k2q0f0P0T2S0D6d5|5x130X6v3T130q6s2p0%2S6A3!5%3v5)6w3z130f6I57130l0#3X0d6X6M636P675?5H0u6C6E6j6H6%690152040n546.5/5N5P2Y5@5}046V4J066Y736Z3!64042S0K0b0A0u5z5/580!5 71736}3L130F7e6N6;6@5U7l6O044^4`4|6R5S135a5j6/6)046Q7E7f5~6W6Y7u770f6$7t6(7n7p3y6;020L0K0E7s5(7u7G6D6i6G0P7A5l13703472746X7O6h0/7b7d6^6N7g7.4?047o7J7 7L7~7W130)7V3!7G7+6l6n0u6p6r6t816x046z856B047*6F6-7S6/6;0p8c487U8q6J5;8A4o6P8m5:040l7M7^5H770P0?7-8D6S6 8N747_787{7c8G3b7`6j8g6o0;8k2T8J588p5{8r8t6,8T8?8E045=8w6e8I88518a8%5q5_8:6T606276650P7R5G6/6b3D8J6f8)6k6m8,6q988o9k6*7+8v9g7K8L7;4l7k8P7`7a8$928B8!8*9o8i8-6E6u8U7B9s9Q8(8s6+7,9r8~7%5M5C6{4;868L3+0e4/4*4R9.0e4U1B0K4W9?2(2!22242$0q1/9:4U1H9(3y2S0C0T0x0q0c6r0o0W131t1v1x1z0d9A5Q1O3l1I0U0q0d0Z0P0A2L1k0d310Y0O2p0K0Y1;0%2f0@0`2Q6t2N0d1z0K0^8R1:0d0qat0D2b0u0D0qaD2q2N0z060U1;4Z0,aP2PaO0d1x0q6Ga!0fai0r0d0G0^0q0baB0d6k2ba-0d2.0Y0;2Sb21;aJ4ZaYa!0Ya$0f1ka(0y0L0da91iaN1l9e0x0/a{0L3$0@2P0D0o0qaiaT0F0F8R0d0A0Y0D7b2L0xa{6t2I6q0Ab6002paB0Ca0bb0@0Z3B0PbNb#ay0f0t0Daj0%0Y0ma}8f1z0z1Kao04bmasa aP5eb)0haN0|0q0Haubbbob9bcaratavbj1laU2T4 9-3y1_1%1)1+a48d6CbG6F4-9,4!3D2J7b0d0+0Q0K2p0fbU0b390+b5b7ccb`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

.128013.ur6km c;piy/7C2EtPj)=lh0sebwS_53(-av,1[:n84dg+9]ofI050T0B0s0K0l0x0A0h0i0x0K0A0A0w010s0l0k010406050A0c0g0g0K0d0m040E0Y0x0c0^0Y0Q050n0 1113150}0k041e1l051o0n1o1q1l0}0T0l0L0-0/0;0?0y0l0U0y0x1E0y0s0{050(0C0x0B1z0:0=011D1F1H1F0s1N1P1L0s0C0Y0T151M0d1m0s0y0-180A0k0K0Q0?0q011R1B010Z0*0B0Q0K0g0B1L1?1^1}1T201P23250{0a0h0t0d0Y0k0Y0A0l1b0Q0h0$1;0d0d0B0i2q1e280Q1m0n1/2D0s1-1,1.0T2a0?1H0Q222n1L1w1y0.1S2N0l2P0Q1)1x1L0k2w1m2B2D2+0~1@2r2V1~2!0d120x0{0h0N2A2/0|2.292;1T2?2^2`0q2}1^2 2B2M01340K2_040h0H382C0}3b320?3e3g0h0S3k3a2/3c3q2`0G3u3m3w3o3d0Y2@3f2`0e3B302:1A333G353h0o3L3n3O3p3Q3I3h0R3U3D3W3F3H3r0W3$313(3y040N0z3-3N2W3)3R0N2|1f2~3C3.3_3:0N373~39403^2=3Y3g0N3j463l3M3x4b0{0N3t4f3v414a3*4k3A4n484i4r3;3K4n1n2)1e2T2G0T2K3c0i1)261m4E1p4C2-4A4J0$2*3%420{0t0!0r0p0r0E3u0h4h3E0Y0{0w4(4*3(0`040O3u4:3_0g0l4k0z3?4A3V3_4=0M4/511~4{0{0G4 2-561T53554V574|040q5b2~4_1~5f4n4)5d0?583;5m395o5e0{545r5z5u5j4t5c5h5A045C2+5s5J5F0{455I4p5K5M2~5O5U5Q3;4^5t014=0X3B064v3E0f0{0$0Z5$5P010D2`5?5Z3d0Z0{2w0Q0T0c0F0g1c230l0B0F2w0i5{495K0I6d3x0{0K6a220T2w6h3E5q5N5E3d0{0l6p4;5B5g5|0Q5:0B0u6k60626x520{0v0P3B0h6P5Y6e0?5/040l5=5D5%6C046G6m6o6Y5@4,040w4.6)5|5v5x2C6t4=6N4u6Q6{6R3c6U2w0s0c0d1d6/6S6u040$6F6l610c6O6Q6t6!0k6A766+6.6s6Z4X4Z4#4%505@4=4@7t6B6v6J5p0{5*6`7f5%6U6W7j6i047i753c6+020x0s0j7m5X7g6j7b6n0B7A5K6_2+066|7F5@6!796$7c7#0?6+0b7;770K0k0k6m7^4=6g7x767h7~6L7e7*6t6 0%72747n7,5 6m63650Q67696b8404805T827X6H6(8d5|6+0J7J3E83813c6r7V7o6V8n5W396}8A6D7a6H7d8C6q857E6P880{0B0+7!8R6y047%3 7*8V7G8f71738z3/8f7c64660)8l2x8n8p5n8G7/7Z8I8:4W8H7N4+0{0V935i4k92968;786E908Q8q8D8T7(5,8W9g6X9k3E5_3h7^0Q5~048P8@8j8_8|9w8s6%8!9s8$6M868L3(898.8c8F8e9z8g9B8k6l6c8#6K8o9F6#7Y8u8~7u6z9e4`5j6=4U5|8E8K6@0{0O0X0v3L0n4S0B2D2(a14D1x4F2G2I2E1(1*2G0K1Oa40n4E0}ah0%0)0+04.