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

.128013it3a;dvn2.S5wb*cy+14: f-up08)_9eklohrP=[s6(]/mg7050g0G0c0e0b0I0P0w0q0I0e0P0P0N010c0b0A010406050P0z0U0U0e0L0r040l0J0I0z0;0J0i050T0{0}0 110_0A04051h1a1k0T1h0_0g0b0h0)0+0-0/0+0i0V0z0e0V0G0y0A0r0c0K180w0K0b0V0K0I1M0K0c0@050!0o0I0G1t0,0.011L1N1P1N0c1V1X1T0c0L1i1H0)140P0A0e0i0/0j011Z1v010x0$0G0i0e0U0G1T1^1`1 1#221X25270@0a0w0M0L0J0A0J0P0b170i0w0Y1?0L0L0G0q2s1a2a0i1i0T1H2F1/1;1:1U0g2c1w0b0i242p1T1q1s0*1!2P2R0i0J2V1T0A2y1i2D2F2,0`1_2t2X202#0L0~0I1T0e1K2y0x0/030E0E0q2$0G1P2!0J0y0t3a0@0w0t1a0e2-2:0^2/2b2=1#2@2_2{2}0G2 01313335372S3a0y1}040w0j3g3i1`3k2D2O013p0e2`1i2|0K2~3032340Y3z2#3B0d3d0d3H2C3j0_3L3n0/3O3Q053S3U3v3W3y2Q3A3b0u3d0u3)1b3+3l2;1u3o0J2^3P3r3T3t3V3x3Y3{3!3b0m3d0m412,3,2:3M3:4b3@3w3X364h393b0Q3d0Q4n433-463/483q3R3s3u4v3`383B0W3d0W4E3J4p3m4H3N4J4a4L4c4N3_4g4Q3b0C3d0C4V2E4X452Y4!493;3?4d3^4f4x4,0y0F3d0F4;3K4q3.4_4K3=4M4e4w3Z4z3a0B0@0t0B564?4r4#4{5d4~5f4y3B0t0t5k3f0T3h3*3J1l2*1a2V2I0g1;2N594w2U1r1i2)0G2+3j5D2E054w5U2b0b0g0/322D5w3r5$5(4 5g5+0w2g0G5.5u515y2F5C4G4^0i0@0x0e2A480b361X0E270U5W3E443M0J0@0N6c0w6e590?040O6c6l4Z0U0b5k6q5~206n0S6c0_425E3L5-015)2:3B3D5c6G4*503|3C1~5?5^4P6Q6L5B3k6D5X6F5%6H0E5*3b3$4L6N5/5v6+6S265@6(5_6Q6,3H6C2.6$5.6*0y3~6-6%6O5:3}6=276U4+6Q733)6x1#0H0@0Y0x6w584Z0n3d7m4Y5 0x61630c65670G7r4@6y0@0R7B4r0@196!5!7C1#6n0D0v6B7G6.714k747b6P4i0y4k5=6?7X777!1T6Y0w7-6k7g3/0@0b6j6r4^6g046i7K7/7n5 0o0@2f7G6m7E844Z600462640L660I686a874^7O7R7K6e7T6J4A5,756/514B7$7a6^6V7Z4B5|3E7.7^207i040n1L1X7@7:3N7I8M7 207`020V0c0f7|2,7~7s2?7=8i7D047Q7K6}5V6 6(714S7W8y7c7Z4S8w6@766:0y8=3H7.928!7M7;8a7w0E0b0U5A8Z8F1#7`8Y3j947H978c8e8g0G6b8m8N6n6p9r8R3o8%7}9e0/7`0y8Q8#1#6t6v9v9F0/6z8l6~4q8o1`3B4.8?8}514.8{7(8~9T91937-9A8O9l0c999E95019g9.9k8b9,9a9c9i9)7`0p9=59897?8,7S8s71539U8t6Q539Y8@7Y5ha79$9%9)899@7y8f0G699p8(9f0@0kar960e0A0A240gav016n7F9J9/ak98a29O9KaD0@0D9N8.9Pa58p5i8r9Z5`5jac9V6Q5l7+3h9%9(8Na19 4Z7`0s9h3J9j599H049`4Wa470aU5xaWad7)b0a!a97Zb08C929)8H2y0c0z0L7J9da,7v9m7zap9qaL9/9taC89bhaRaM9Ma38m0T5Z5F5T5H5Q1a0c5KbG2L2G0e1WbD0T5I6C0Y0!0$0P04.

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

.128013it3a;dv,n2S5wbcy+14: f-up08)_9eklohxrP=[s6(]/mg7050g0F0c0e0b0H0P0v0p0H0e0P0P0N010c0b0z010406050P0y0U0U0e0L0q040l0I0H0y0;0I0j050T0{0}0 110_0z04051h1a1k0T1h0_0g0b0h0)0+0-0/0+0j0V0y0e0V0F0x0z0q0c0J180v0J0b0V0J0H1M0J0c0@050!0o0H0F1t0,0.011L1N1P1N0c1V1X1T0c0L1i1H0)140P0z0e0j0/0k011Z1v010w0$0F0j0e0U0F1T1^1`1 1#221X25270@0a0v0M0L0I0z0I0P0b170j0v0Y1?0L0L0F0p2s1a2a0j1i0T1H2F1/1;1:1U0g2c1w0b0j242p1T1q1s0*1!2P2R0j0I2V1T0z2y1i2D2F2,0`1_2t2X202#0L0~0H1T0e1K2y0w0/030D0D0p2$0F1P2!0I0x0d0x0s0@0v0s1a0e2-2:0^2/2b2=1#2@2_2{2}0F2 01313335372S3a0x1}040v0k3h3j1`3l2D2O013q0e2`1i2|0J2~3032340Y3A2#3C0d3e0d3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0t3e0t3*1b3,3m2;1u3p0I2^3Q3s3U3u3W3y3Z3|3#3b0m3e0m422,3-2:3N3;4c3^3x3Y364i393b0Q3e0Q4o443.473:493r3S3t3v4w3{383C0W3e0W4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0B3e0B4W2E4Y462Y4#4a3=3@4e3_4g4y4-0x0E3e0E4=3L4r3/4`4L3?4N4f4x3!4A3c0A0@0s0A571l2*1a2V2I0g1;2N5a4x2U1r1i2)0F2+3k3+3K054x5E2b0b0g0/322D3C3d4M5M5O505h5R1~2g0F5V5g4z5Y2F3i453N0G0@0Y0w5G2E5,5a0n3e5=5K4^2?0w0@0P0I0}0F0D0~0K0b5{5@4!0?040R694H4_0j0@0h3Q0F0y0L0P6f596b0@0i5{0v6a6h0@0G6q4Z4_6c0C0u5{0_435H3M5U015P2:3C3E5d6M4+513}3D5Z265#6N5W5(3b6R0T3i0v6,6w6g2?6z0D61636v6x200I0@0N6^6/1#0U0b0@5n6J4?6B2t6T6=6P3b3%5T5N6#5%523%0v5!5$4Q6W7d3I6-6.6r4_5.040w496~7t6:0468753F6_1#0I5_7C197E7s6C2?0o0@0L1`1C773N6c6e7E7G3:6z7V5a6E6G7E6I2.6L7f6O1`3C3 7e7m4,6W3 7k6Z7^6V4j0x7?7q7r6-7!3O6;6?277z7O7H0@0r6}7M866i046k1X6n6p7Z6 0/6c0O7%4!8j7D7-7A1#6c0S6H7V795Q4k3s797h6W4l7|277~5X8H5*3F858q8704668x3k7N5}8d048g2,8#4s88628a7+8E7/7a7;4B8I8=8K804C8N6!6U8Q0x4C8S7r867v7x0L8b8$7#7C9a3N7I0@2Q9e5a0j7Q047S1y0F8u6D0@7Y8y8c9c6A8p8z8r6t9j8v9m2f9r207X9H3p6j6l8n9K9B040C6F8D9z5L8=8G0x4T7@7g7n804T8~8P6%9Z1T6*8T848+9k8-6@8h8V6{048f9D6y8k9N6o9P018sa38wa38B9~6`0@0xaa9La08ma29V9ba40@8taj8,9d9_9A019{adar9w8W9y9vaka98:ao8F7b0x4/9#909,4/9*9$7_80aI839;969h5;awak8j0G6=8.9qaX9f0@020V0c0fae9c8Ya80@7*4p8;5V9Y54aJ6$5254aNaKa 9.6+9;848i0@a;a(5a9{8)8!b804a!89a%a^aE9XaG5m8_9+52bpb1a~6Wbp948Uas7v2y0c6n7L8*bgbabl2.0T5J5p5D5r5A1a0c5ubR2L2G0e1WbO0T5s6I0Y0!0$0P04.

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

.128013it3a;dv,FnT2S5wbcy+14: f-up08)_9eklohrP=[s6(]/mg7050g0H0c0e0b0J0Q0x0r0J0e0Q0Q0O010c0b0B010406050Q0A0V0V0e0M0s040n0K0J0A0=0K0k050U0|0~10120`0B04051i1b1l0U1i0`0g0b0h0*0,0.0:0,0k0W0A0e0W0H0z0B0s0c0L190x0L0b0W0L0J1N0L0c0^050#0q0J0H1u0-0/011M1O1Q1O0c1W1Y1U0c0M1j1I0*150Q0B0e0k0:0m011!1w010y0%0H0k0e0V0H1U1_1{201$231Y26280^0a0x0N0M0K0B0K0Q0b180k0x0Z1@0M0M0H0r2t1b2b0k1j0U1I2G1:1=1;1V0g2d1x0b0k252q1U1r1t0+1#2Q2S0k0K2W1U0B2z1j2E2G2-0{1`2u2Y212$0M0 0J1U0e1L2z0y0:030F0F0r2%0H1Q2#0K0z0o0z0u0^0x0u1b0e2.2;0_2:2c2?1$2^2`2|2~0H3001323436382T3b0z1~040x0m3i3k1{3m2E2P013r0e2{1j2}0L2 3133350Z3B2$3D0d3f0d3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0v3f0v3+1c3-3n2=1v3q0K2_3R3t3V3v3X3z3!3}3$3c0o3f0o432-3.2;3O3=4d3_3y3Z374j3a3c0R3f0R4p453/483;4a3s3T3u3w4x3|393D0X3f0X4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0D3f0D4X2F4Z472Z4$4b3?3^4f3`4h4z4.0z0G3f0G4?3M4s3:4{4M3@4O4g4y3#4B3d0C0^0u0C581m2+1b2W2J0g1=2O5b4y2V1s1j2*0H2,3l3,3L054y5F2c0b0g0:332E3D3e4N5N5P515i5S1 2h0H5W5h4A5Z2G3j463O0I0^0Z0y5H2F5-5b0p3f5?5L4_2@0y0^0Q0K0~0H0F2p0.0b1X0H5|5^4#0@040S6c4I4`0k0^250Q6i5a6e0^0i5|0x6d6k616p4!4`6f6t443L6v6j2@0^0b6z5~1$6C6u6w6I04280V0K6L3O6f0E0w5|0`6E5@3N5V015Q2;3D3F5e6*4,523~3E5!275$6+5X5)3c6/0U3j0x736G6q4`5/040b5=6%3G6Q3q6y7c756A210K0^0O0O6P6H1$0V0b0^5o7c7e0:6f6!7c6$2/6)5O6|5R3c3(5U7F6=5Y7I6_285%4R6@7J3J747W7i6M0:782z0c0A0M1a7h7x010I0r0^0l0M0A6b7B6W6;0F7H0z407K7R4-6@400x5#806?4k7}1U713G747,787a7p766R6K7+7q0:7l04020W0c0f7o8l8i3q0q0^2g6W5b6f6h7w8m3P6m0k6o8F8w7y0^0E8h7j1$0K5`044a8Q7Z8H048K2-7Y3O8o020J8s8X3O7s7u8B6r047A4q7_7L7{6-4l3t7`5(534m846`867N3b8a727X738e0^7$7(7*8$8e7/040j3R0Q7@8^8L5M8`7|4D7 6|906@4D937Q9w7S889u7V8d8G8f7b9h8G8D8;6x8!9O216O8v8R3;6J9R6N8O8-5b8T0^2$0c9#4#9%799g3l8%5b6l6S0H6U9Y8N8?6#8_5W7|4U9v7M6~0z4U9A6{a353a19G9a7,9?0e0h2A0F370c0F8k9L8M018o8uao9V8Z6264662q2r6a9`019N9q8Y9?6naC9TataG7gaL8(0^0z9+9PaIaF6X0^0PaC9?an5G9M0^0T6DaO9=9XaV9$0^0taC8/043ha.8=a*9:ae0^6T6Va_6B9!7^aV7`7|4:a26}534:a795a4b8ac7Xa}8!1{0Qaj8+amaS7k7mbq7f8!6328ay68aBb19S0^8E7DapaH8JaJ6sbt9W9QbB9Z04a{6Fbja#5I8G8oa;bO0:a?a^bFauaKa|8G9?a bJ048Pb4b%2ub68|548~8`9x8855bd9C81b}988cadb+a~9^b0b=aW040PbEa$bGaNcfb(bK9UaM79b.0E0TbLaqbscl4t0^agaiakbpcu9$8U8WcB4#9?0QblbnalbU4@9~7Gb^5nb`be53cRb a96@cR5+c49;4#7#0!9fcrb,c8b.cdaZchbVapb)bSc6cnbZaD8Ocqb;5G0U5K5q5E5s5B1b0c5vd72M2H0e6a2G5t6$0Z0#0%0Q04.

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

.128013it3adv,n2S5wbcy+14: f-up08)_9eklohrP=[s6(]/mg7050f0E0c0e0b0G0N0u0o0G0e0N0N0L010c0b0y010406050N0x0S0S0e0J0p040k0H0G0x0/0H0i050R0_0{0}0 0@0y04051f181i0R1f0@0f0b0g0%0)0+0-0)0i0T0x0e0T0E0w0y0p0c0I160u0I0b0T0I0G1K0I0c0=050Y0n0G0E1r0*0,011J1L1N1L0c1T1V1R0c0J1g1F0%120N0y0e0i0-0j011X1t010v0!0E0i0e0S0E1R1?1^1}1Z201V23250=0a0u0K0J0H0y0H0N0b150i0u0W1;0J0J0E0o2q18280i1g0R1F2D1-1/1.1S0f2a1u0b0i222n1R1o1q0(1Y2N2P0i0H2T1R0y2w1g2B2D2*0^1@2r2V1~2Z0J0|0G1R0e1I2w0v0-030C0C0o2!0E1N2Y0H0w0U0w0r0=0u0r180e2+2.0?2-292:1Z2=2@2_2{0E2}012 3133352Q380w1{040u0j3f3h1^3j2B2M013o0e2^1g2`0I2|2~30320W3y2Z3A0d3c0d3G2A3i0@3K3m0-3N3P053R3T3u3V3x2O3z390s3c0s3(193*3k2/1s3n0H2?3O3q3S3s3U3w3X3`3Z390l3c0l402*3+2.3L3/4a3?3v3W344g37390O3c0O4m423,453.473p3Q3r3t4u3_363A0U3c0U4D3I4o3l4G3M4I494K4b4M3^4f4P390A3c0A4U2C4W442W4Z483:3=4c3@4e4w4+0w0D3c0D4:3J4p3-4^4J3;4L4d4v3Y4y3a0z0=0r0z554=4q4!4`5c4}5e4x3A0r3b045w551j2(182T2G0f1/2L584v2S1p1g2%0E2)3i3)3I054v5Q290b0f0-302B5v3q5Y5!4~5f5%0u2e0E5*5t505x3(4F4@0i0=3X1^2Z0p0C250S5S2C0u433L0H0=0L643D67580i0n5|0b2y6c6e4Y0;040P0B6c0@415T3K5)015#2.3A3C5b6x4)4 3{3B1|5/5;4O6H6C0R3g6t2,6w5Z6y0C5$393#4K6E5+5u6Y6J245:6V5=6H6Z3G6R5R6T5*6X0w3}6!6U6F5,3|6)256L4*6H6`5^574Y0F5|3s6l5_1~0m3c7c775`0v7a1v5 7h4X4@6o0P7o4?2;0=176u2C6m7q0=0h6c667d3n0=637y5W7u1Z6o0B0t6s7t0u6#6^4j6{726G4h0w4j5.6*7Y6~7#1R6P3D0u7/7A1~79040b0v7E7;7N0=7s7K7{3.7w7S586o7D7K7F7i7v047J6S897|046r8780010H7f042Z0c7`7G0-8l0=2O8q8e81045}0i5 610E8c6=8x016o7Q7K6;6v4p7U6A4z5(6|6$504A7%716,6M7!4A2D3g7/8)8)8j7?7^8w7p1~7r834Y5{8n8/7M8s6a6b8i8r010S0b0=5l7 907O8`688m4799847}8?5`7I9d4Y69040L8~2*888:1Z92949g8;0=7P7R968O8T6^4R7X8Z737!4R8X6+6}6%387,8(8*9R7:908^2w0_0G0Y8p8 8H9l9o3i9q8{91935y9z8d5X9C8Q0w4-9F9M504-9K7)9N9^3G9S9T8H7?340N0E9v8f8K4n7S8P1^3A529_8U6H529}9G7Z5gaha1a28*8j9V0E9X9Z9j4@9%az8a8A7n9A9r0-8=aG9+8^7x9p8j9l0waC9s9-3eaK3L85aS8y8F8NaH8I9xaZ8k0=0qa*8^aE0H0pa9aI9faW6f82a_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=0M7~bu4qa{b.9e0486bD8H8^b(7LaX9x0QbA9(3I9*b/049W0x9Y0e9!acaWae0i5v5@2`6#6-7!5w709Lajck5@7-at907?2w0c0x0JaN9)bZ8z34bg6062bGb+b-8Ga%bmb79wb?a bzcN8f0Bb bI7 0R5V5B5P5D5M180c5Gc(2J2E0e1Uc#0R5E6t0W0Y0!0N04.