Programmation Dynamique | Exercices

Voici exercices du site codex

Factorielle⚓︎

On note $n!$ la factorielle d'un entier naturel $n$, c'est le produit des nombres entiers strictement positifs qui sont inférieurs ou égaux à $n$.

Formule récursive

Pour $i>0$ on a $i! = (i-1)! × i$, comme on peut le constater sur les exemples

$5! = 1×2×3×4×5 = 4! × 5$
$6! = 1×2×3×4×5×6 = 5! × 6$
$7! = 1×2×3×4×5×6×7 = 6! × 7$

Ceci conduit à une fonction récursive classique

Python
def factorielle(n):
    """Renvoie la factorielle de n positif"""
    if n == 0:
        return 1
    else:
        return n * factorielle(n - 1)

On souhaite calculer $n!$ et mémoriser dans une liste factorielle_mem les nombres factoriels calculés. Cela permet une utilisation intensive de la fonction, ce qui est souvent le cas en combinatoire. On propose ici une fonction non récursive factorielle qui prend en paramètre un nombre entier n et qui renvoie le factoriel de ce nombre, dont voici le principe :

factorielle_mem est initialisé à [1] de sorte que $0!$ est égal à factorielle_mem[0]
factorielle(n) fait plusieurs actions :
- Elle remplit, si nécessaire, factorielle_mem avec une boucle.
- Elle renvoie $n!$ en utilisant factorielle_mem[n] qui sera donc de taille au moins n + 1 à la fin de l'appel.
- On utilisera la variable fact_i pour $i!$
- On utilisera la variable fact_im1 pour $(i-1)!$

Complèter le code suivant:

Évaluations restantes : 5/5

.128013oP;f 8lkg5:+bry2a1h3tvw=u6e[(*Sn9]_s-c)7im./4p0d050W0B0v0r0P0h0K0f0M0h0r0K0K0y010v0P0U010406050K0z0Q0Q0r0o0p040F0b0h0z0;0b0G050S0{0}0 110_0U04051h1a1k0S1h0_0W0P0w0)0+0-0/0+0G0j0z0r0j0B0L0U0p0v0t180f0t0P0j0t0h1M0t0v0@050!0n0h0B1t0,0.011L1N1P1N0v1V1X1T0v0o1i1H0)140K0U0r0G0/0q011Z1v010e0$0B0G0r0Q0B1T1^1`1 1#221X25270@0a0f0c0o0b0U0b0K0P170G0f0Y1?0o0o0B0M2s1a2a0G1i0S1H2F1/1;1:1U0W2c1w0P0G242p1T1q1s0*1!2P2R0G0b2V1T0U2y1i2D2F2,0`1_2t2X202#0o0~0h1T0r1K2y0e0/030J0J0M2$0B1P2!0b0L0s3a0@0f0s1a0r2-2:0^2/2b2=1#2@2_2{2}0B2 01313335372S3a0L1}040f0q3g3i1`3k2D2O013p0r2`1i2|0t2~3032340Y3z2#3B0u3d0u3H2C3j0_3L3n0/3O3Q053S3U3v3W3y2Q3A3b0T3d0T3)1b3+3l2;1u3o0b2^3P3r3T3t3V3x3Y3{3!3b0k3d0k412,3,2:3M3:4b3@3w3X364h393b0A3d0A4n433-463/483q3R3s3u4v3`383B0O3d0O4E3J4p3m4H3N4J4a4L4c4N3_4g4Q3b0g3d0g4V2E4X452Y4!493;3?4d3^4f4x4,0L0H3d0H4;3K4q3.4_4K3=4M4e4w3Z4z3a0V0@0s0V564?4r4#4{5d4~5f4y3B0s0s5k3f0S3h3*3J1l2*1a2V2I0W1;2N594w2U1r1i2)0B2+3j5D2E054w5U2b0P0W0/322D5w3r5$5(4 5g5+0f2g0B5.5u515y2F5C4G4^0G0@0e0r2A480P361X0J270Q5W3E443M0b0@0y6c0f6e590?040C6c6l4Z0Q0P5k6q5~206n0I6c0_425E3L5-015)2:3B3D5c6G4*503|3C1~5?5^4P6Q6L5B3k6D5X6F5%6H0J5*3b3$4L6N5/5v6+6S265@6(5_6Q6,3H6C2.6$5.6*0L3~6-6%6O5:3}6=276U4+6Q733)6x1#0i0@0Y0e6w584Z0x3d7m4Y5 0e61630v65670B7r4@6y0@0D7B4r0@196!5!7C1#6n0N0l6B7G6.714k747b6P4i0L4k5=6?7X777!1T6Y0f7-6k7g3/0@0P6j6r4^6g046i7K7/7n5 0n0@2f7G6m7E844Z600462640o660h686a874^7O7R7K6e7T6J4A5,756/514B7$7a6^6V7Z4B5|3E7.7^207i040x1L1X7@7:3N7I8M7 207`020j0v0d7|2,7~7s2?7=8i7D047Q7K6}5V6 6(714S7W8y7c7Z4S8w6@766:0L8=3H7.928!7M7;8a7w0J0P0Q5A8Z8F1#7`8Y3j947H978c8e8g0B6b8m8N6n6p9r8R3o8%7}9e0/7`0L8Q8#1#6t6v9v9F0/6z8l6~4q8o1`3B4.8?8}514.8{7(8~9T91937-9A8O9l0v999E95019g9.9k8b9,9a9c9i9)7`0E9=59897?8,7S8s71539U8t6Q539Y8@7Y5ha79$9%9)899@7y8f0B699p8(9f0@0Rar960r0U0U240Wav016n7F9J9/ak98a29O9KaD0@0N9N8.9Pa58p5i8r9Z5`5jac9V6Q5l7+3h9%9(8Na19 4Z7`0m9h3J9j599H049`4Wa470aU5xaWad7)b0a!a97Zb08C929)8H2y0v0z0o7J9da,7v9m7zap9qaL9/9taC89bhaRaM9Ma38m0S5Z5F5T5H5Q1a0v5KbG2L2G0r1WbD0S5I6C0Y0!0$0K04.

Somme maximale de k termes consécutifs⚓︎

Compléter la fonction somme_maxi qui prend en paramètres un tableau d'entiers valeurs, et un entier strictement positif k. Cette fonction doit renvoyer la somme maximale de k entiers consécutifs du tableau valeurs.

On garantit que le tableau valeurs est de taille au moins égale à k et que k est un entier strictement positif.

Exemple

>>> somme_maxi([0, 1, 2, 3, 2, 1, 0], 3)  # pour les termes consécutifs 2, 3, 2
7
>>> somme_maxi([0, 1, 2, 3, 2, 1, 0], 1)  # pour le terme 3
3

Indice

On pourra commencer par faire le cumul des k premières valeurs pour initialiser une variable maxi.

On pourra ensuite faire une boucle qui ajoute la valeur suivante et retranche la première valeur.

Évaluations restantes : 5/5

.128013oP;f 8lkg5:+,bry2a1h3tvw=u6e[(Sn9]x_s-c)7im/4p0d050W0C0w0s0Q0h0L0f0N0h0s0L0L0z010w0Q0U010406050L0A0R0R0s0p0q040F0b0h0A0;0b0G050S0{0}0 110_0U04051h1a1k0S1h0_0W0Q0x0)0+0-0/0+0G0j0A0s0j0C0M0U0q0w0u180f0u0Q0j0u0h1M0u0w0@050!0o0h0C1t0,0.011L1N1P1N0w1V1X1T0w0p1i1H0)140L0U0s0G0/0r011Z1v010e0$0C0G0s0R0C1T1^1`1 1#221X25270@0a0f0c0p0b0U0b0L0Q170G0f0Y1?0p0p0C0N2s1a2a0G1i0S1H2F1/1;1:1U0W2c1w0Q0G242p1T1q1s0*1!2P2R0G0b2V1T0U2y1i2D2F2,0`1_2t2X202#0p0~0h1T0s1K2y0e0/030K0K0N2$0C1P2!0b0M0v0M0t0@0f0t1a0s2-2:0^2/2b2=1#2@2_2{2}0C2 01313335372S3a0M1}040f0r3h3j1`3l2D2O013q0s2`1i2|0u2~3032340Y3A2#3C0v3e0v3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0T3e0T3*1b3,3m2;1u3p0b2^3Q3s3U3u3W3y3Z3|3#3b0k3e0k422,3-2:3N3;4c3^3x3Y364i393b0B3e0B4o443.473:493r3S3t3v4w3{383C0P3e0P4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0g3e0g4W2E4Y462Y4#4a3=3@4e3_4g4y4-0M0H3e0H4=3L4r3/4`4L3?4N4f4x3!4A3c0V0@0t0V571l2*1a2V2I0W1;2N5a4x2U1r1i2)0C2+3k3+3K054x5E2b0Q0W0/322D3C3d4M5M5O505h5R1~2g0C5V5g4z5Y2F3i453N0i0@0Y0e5G2E5,5a0y3e5=5K4^2?0e0@0L0b0}0C0K0~0J0Q5{5@4!0?040E694H4_0G0@0x3Q0C0A0p0L6f596b0@0n5{0f6a6h0@0i6q4Z4_6c0O0l5{0_435H3M5U015P2:3C3E5d6M4+513}3D5Z265#6N5W5(3b6R0S3i0f6,6w6g2?6z0K61636v6x200b0@0z6^6/1#0R0Q0@5n6J4?6B2t6T6=6P3b3%5T5N6#5%523%0f5!5$4Q6W7d3I6-6.6r4_5.040e496~7t6:0468753F6_1#0b5_7C197E7s6C2?0o0@0p1`1C773N6c6e7E7G3:6z7V5a6E6G7E6I2.6L7f6O1`3C3 7e7m4,6W3 7k6Z7^6V4j0M7?7q7r6-7!3O6;6?277z7O7H0@0m6}7M866i046k1X6n6p7Z6 0/6c0D7%4!8j7D7-7A1#6c0I6H7V795Q4k3s797h6W4l7|277~5X8H5*3F858q8704668x3k7N5}8d048g2,8#4s88628a7+8E7/7a7;4B8I8=8K804C8N6!6U8Q0M4C8S7r867v7x0p8b8$7#7C9a3N7I0@2Q9e5a0G7Q047S1y0C8u6D0@7Y8y8c9c6A8p8z8r6t9j8v9m2f9r207X9H3p6j6l8n9K9B040O6F8D9z5L8=8G0M4T7@7g7n804T8~8P6%9Z1T6*8T848+9k8-6@8h8V6{048f9D6y8k9N6o9P018sa38wa38B9~6`0@0Maa9La08ma29V9ba40@8taj8,9d9_9A019{adar9w8W9y9vaka98:ao8F7b0M4/9#909,4/9*9$7_80aI839;969h5;awak8j0i6=8.9qaX9f0@020j0w0dae9c8Ya80@7*4p8;5V9Y54aJ6$5254aNaKa 9.6+9;848i0@a;a(5a9{8)8!b804a!89a%a^aE9XaG5m8_9+52bpb1a~6Wbp948Uas7v2y0w6n7L8*bgbabl2.0S5J5p5D5r5A1a0w5ubR2L2G0s1WbO0S5s6I0Y0!0$0L04.

Somme d'un sous-ensemble⚓︎

Étant donné un ensemble $E$ d'entiers positifs et un entier naturel $s$, on demande s'il existe un sous-ensemble de $E$ dont la somme des éléments est égale à $s$.

On appelle ensemble vide l'ensemble qui ne contient aucun élément et on le note en général $\emptyset$. L'ensemble vide est un sous-ensemble de n'importe quel ensemble $E$ et la somme de ses éléments vaut $0$.

Méthode par force brute : on teste tous les sous-ensembles de $E$. Le problème avec cette méthode est que si $n$ est le nombre d'éléments de $E$, alors le nombre de sous-ensembles de $E$ est $2^n$. Avec le calcul des sommes de chaque sous-ensemble, on obtient un coût total de l'ordre de $n\times 2^n$. Ce coût est rédhibitoire. Par exemple, avec $n=40$, le coût est d'environ $40\times 2^{40} \simeq 4\times 10^{13}$. Donc si une machine effectue une opération en $10^{-7}$ s, il faudra environ $4\times 10^6$ s pour explorer tous les cas, soit environ 1000 heures !

On va donc utiliser la programmation dynamique.

Programmation dynamique⚓︎

Un ensemble de nombres est représenté par une liste en Python, par exemple [4, 1, 8, 2].

Définition des sous-problèmes

Pour chaque élément d'indice i, nous avons une prise de décision entre deux possibilités:

soit on choisit cet élément d'indice i et on continue récursivement avec les éléments restants et la somme restante;
soit on ne le choisit pas et on continue récursivement avec les éléments restants et la même somme.

Les cas de base:

la somme à obtenir est nulle et le sous-ensemble est trouvé,
il n'y a pas d'élément à choisir ou la somme à obtenir est négative.

On utilise un dictionnaire pour mémoriser les solutions des sous-problèmes dans une approche descendante. Une clé du dictionnaire est un couple (s, i) qui représente le sous-problème obtenir la somme s en considérant les éléments à partir de l'indice i, la valeur associée étant True ou False.

Compléter le code de la fonction somme_possible qui prend en paramètres une liste ens représentant un ensemble de nombres, un entier positif s, un indice i, un dictionnaire memo et qui renvoie True s'il existe un sous-ensemble de nombres dont la somme des éléments vaut s et False sinon.

Exemple

Python
>>> nombres = [4, 1, 8, 2]
>>> somme_possible(nombres, 7, 0, {})
True

Le sous-ensemble dont la somme des éléments vaut 7 est $\{ 4, 1, 2 \}$.

Évaluations restantes : 5/5

.128013oP;f 8lkg5:+,Fbry2a1h3tvwT=u6e[(Sn9]_s-c)7im/4p0d050X0E0x0t0R0h0M0f0O0h0t0M0M0B010x0R0V010406050M0C0S0S0t0q0r040H0b0h0C0=0b0I050T0|0~10120`0V04051i1b1l0T1i0`0X0R0y0*0,0.0:0,0I0j0C0t0j0E0N0V0r0x0v190f0v0R0j0v0h1N0v0x0^050#0p0h0E1u0-0/011M1O1Q1O0x1W1Y1U0x0q1j1I0*150M0V0t0I0:0s011!1w010e0%0E0I0t0S0E1U1_1{201$231Y26280^0a0f0c0q0b0V0b0M0R180I0f0Z1@0q0q0E0O2t1b2b0I1j0T1I2G1:1=1;1V0X2d1x0R0I252q1U1r1t0+1#2Q2S0I0b2W1U0V2z1j2E2G2-0{1`2u2Y212$0q0 0h1U0t1L2z0e0:030L0L0O2%0E1Q2#0b0N0k0N0u0^0f0u1b0t2.2;0_2:2c2?1$2^2`2|2~0E3001323436382T3b0N1~040f0s3i3k1{3m2E2P013r0t2{1j2}0v2 3133350Z3B2$3D0w3f0w3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0U3f0U3+1c3-3n2=1v3q0b2_3R3t3V3v3X3z3!3}3$3c0k3f0k432-3.2;3O3=4d3_3y3Z374j3a3c0D3f0D4p453/483;4a3s3T3u3w4x3|393D0Q3f0Q4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0g3f0g4X2F4Z472Z4$4b3?3^4f3`4h4z4.0N0J3f0J4?3M4s3:4{4M3@4O4g4y3#4B3d0W0^0u0W581m2+1b2W2J0X1=2O5b4y2V1s1j2*0E2,3l3,3L054y5F2c0R0X0:332E3D3e4N5N5P515i5S1 2h0E5W5h4A5Z2G3j463O0i0^0Z0e5H2F5-5b0z3f5?5L4_2@0e0^0M0b0~0E0L2p0.0R1X0E5|5^4#0@040G6c4I4`0I0^250M6i5a6e0^0n5|0f6d6k616p4!4`6f6t443L6v6j2@0^0R6z5~1$6C6u6w6I04280S0b6L3O6f0P0l5|0`6E5@3N5V015Q2;3D3F5e6*4,523~3E5!275$6+5X5)3c6/0T3j0f736G6q4`5/040R5=6%3G6Q3q6y7c756A210b0^0B0B6P6H1$0S0R0^5o7c7e0:6f6!7c6$2/6)5O6|5R3c3(5U7F6=5Y7I6_285%4R6@7J3J747W7i6M0:782z0x0C0q1a7h7x010i0O0^0A0q0C6b7B6W6;0L7H0N407K7R4-6@400f5#806?4k7}1U713G747,787a7p766R6K7+7q0:7l04020j0x0d7o8l8i3q0p0^2g6W5b6f6h7w8m3P6m0I6o8F8w7y0^0P8h7j1$0b5`044a8Q7Z8H048K2-7Y3O8o020h8s8X3O7s7u8B6r047A4q7_7L7{6-4l3t7`5(534m846`867N3b8a727X738e0^7$7(7*8$8e7/040o3R0M7@8^8L5M8`7|4D7 6|906@4D937Q9w7S889u7V8d8G8f7b9h8G8D8;6x8!9O216O8v8R3;6J9R6N8O8-5b8T0^2$0x9#4#9%799g3l8%5b6l6S0E6U9Y8N8?6#8_5W7|4U9v7M6~0N4U9A6{a353a19G9a7,9?0t0y2A0L370x0L8k9L8M018o8uao9V8Z6264662q2r6a9`019N9q8Y9?6naC9TataG7gaL8(0^0N9+9PaIaF6X0^0FaC9?an5G9M0^0K6DaO9=9XaV9$0^0maC8/043ha.8=a*9:ae0^6T6Va_6B9!7^aV7`7|4:a26}534:a795a4b8ac7Xa}8!1{0Maj8+amaS7k7mbq7f8!6328ay68aBb19S0^8E7DapaH8JaJ6sbt9W9QbB9Z04a{6Fbja#5I8G8oa;bO0:a?a^bFauaKa|8G9?a bJ048Pb4b%2ub68|548~8`9x8855bd9C81b}988cadb+a~9^b0b=aW040FbEa$bGaNcfb(bK9UaM79b.0P0KbLaqbscl4t0^agaiakbpcu9$8U8WcB4#9?0MblbnalbU4@9~7Gb^5nb`be53cRb a96@cR5+c49;4#7#0!9fcrb,c8b.cdaZchbVapb)bSc6cnbZaD8Ocqb;5G0T5K5q5E5s5B1b0x5vd72M2H0t6a2G5t6$0Z0#0%0M04.

Nombres de Delannoy⚓︎

Dans une grille de taille $n×m$, on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) vers le coin supérieur droit (au Nord-Est).

Les seuls mouvements autorisés sont :

↑ Aller au Nord d'une unité.
→ Aller à l'Est d'une unité.
↗ Aller au Nord-Est en diagonale, sur le prochain nœud.

Écrire une fonction delannoy qui prend en paramètres deux entiers n et m et renvoie le nombre de chemins allant de $(0, 0)$ jusqu'à $(n, m)$.

Pour ce faire, on remarquera :

Si n ou m est nul,
alors le seul chemin est en ligne droite, la réponse est 1,
sinon : -n et m sont non nuls et les chemins qui vont en (n, m) se répartissent en trois catégories :
- ceux qui venaient de (n - 1, m ),
- ceux qui venaient de (n , m - 1),
- ceux qui venaient de (n - 1, m - 1),
ces trois catégories sont distinctes et se comptent bien par récursivité.
On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.

Exemples

Python
>>> delannoy(3, 3)
63
>>> delannoy(2, 1)
5

Compléter le code :

Évaluations restantes : 5/5

.128013oPf 8lkg5:+,bry2a1h3tvw=u6e[(Sn9]_s-c)7im/4p0d050U0B0v0r0O0g0J0e0L0g0r0J0J0y010v0O0S010406050J0z0P0P0r0o0p040E0b0g0z0/0b0F050Q0_0{0}0 0@0S04051f181i0Q1f0@0U0O0w0%0)0+0-0)0F0i0z0r0i0B0K0S0p0v0t160e0t0O0i0t0g1K0t0v0=050Y0n0g0B1r0*0,011J1L1N1L0v1T1V1R0v0o1g1F0%120J0S0r0F0-0q011X1t010d0!0B0F0r0P0B1R1?1^1}1Z201V23250=0a0e0c0o0b0S0b0J0O150F0e0W1;0o0o0B0L2q18280F1g0Q1F2D1-1/1.1S0U2a1u0O0F222n1R1o1q0(1Y2N2P0F0b2T1R0S2w1g2B2D2*0^1@2r2V1~2Z0o0|0g1R0r1I2w0d0-030I0I0L2!0B1N2Y0b0K0N0K0s0=0e0s180r2+2.0?2-292:1Z2=2@2_2{0B2}012 3133352Q380K1{040e0q3f3h1^3j2B2M013o0r2^1g2`0t2|2~30320W3y2Z3A0u3c0u3G2A3i0@3K3m0-3N3P053R3T3u3V3x2O3z390R3c0R3(193*3k2/1s3n0b2?3O3q3S3s3U3w3X3`3Z390j3c0j402*3+2.3L3/4a3?3v3W344g37390A3c0A4m423,453.473p3Q3r3t4u3_363A0N3c0N4D3I4o3l4G3M4I494K4b4M3^4f4P390f3c0f4U2C4W442W4Z483:3=4c3@4e4w4+0K0G3c0G4:3J4p3-4^4J3;4L4d4v3Y4y3a0T0=0s0T554=4q4!4`5c4}5e4x3A0s3b045w551j2(182T2G0U1/2L584v2S1p1g2%0B2)3i3)3I054v5Q290O0U0-302B5v3q5Y5!4~5f5%0e2e0B5*5t505x3(4F4@0F0=3X1^2Z0p0I250P5S2C0e433L0b0=0y643D67580F0n5|0O2y6c6e4Y0;040D0M6c0@415T3K5)015#2.3A3C5b6x4)4 3{3B1|5/5;4O6H6C0Q3g6t2,6w5Z6y0I5$393#4K6E5+5u6Y6J245:6V5=6H6Z3G6R5R6T5*6X0K3}6!6U6F5,3|6)256L4*6H6`5^574Y0h5|3s6l5_1~0x3c7c775`0d7a1v5 7h4X4@6o0D7o4?2;0=176u2C6m7q0=0m6c667d3n0=637y5W7u1Z6o0M0k6s7t0e6#6^4j6{726G4h0K4j5.6*7Y6~7#1R6P3D0e7/7A1~79040O0d7E7;7N0=7s7K7{3.7w7S586o7D7K7F7i7v047J6S897|046r8780010b7f042Z0v7`7G0-8l0=2O8q8e81045}0F5 610B8c6=8x016o7Q7K6;6v4p7U6A4z5(6|6$504A7%716,6M7!4A2D3g7/8)8)8j7?7^8w7p1~7r834Y5{8n8/7M8s6a6b8i8r010P0O0=5l7 907O8`688m4799847}8?5`7I9d4Y69040y8~2*888:1Z92949g8;0=7P7R968O8T6^4R7X8Z737!4R8X6+6}6%387,8(8*9R7:908^2w0_0g0Y8p8 8H9l9o3i9q8{91935y9z8d5X9C8Q0K4-9F9M504-9K7)9N9^3G9S9T8H7?340J0B9v8f8K4n7S8P1^3A529_8U6H529}9G7Z5gaha1a28*8j9V0B9X9Z9j4@9%az8a8A7n9A9r0-8=aG9+8^7x9p8j9l0KaC9s9-3eaK3L85aS8y8F8NaH8I9xaZ8k0=0la*8^aE0b0pa9aI9faW6f82a_6n7Ca.9i9#a%aQa*9t9.a|7B8ga*9la-b1aL7l5~a;a?a(6pbiaMba0=aRbd3Lb5aV9:9+aYbqa`8bbn04bpaO90bsbi988Lad9=af395k8S9~5?5iam9`6HbN8%7.9Saubf8Ba;8Da#7z970=0C7~bu4qa{b.9e0486bD8H8^b(7LaX9x0HbA9(3I9*b/049W0z9Y0r9!acaWae0F5v5@2`6#6-7!5w709Lajck5@7-at907?2w0v0z0oaN9)bZ8z34bg6062bGb+b-8Ga%bmb79wb?a bzcN8f0Mb bI7 0Q5V5B5P5D5M180v5Gc(2J2E0r1Uc#0Q5E6t0W0Y0!0J04.