Solutions
460
7) Nous obte nons le tableau sui vant :
b 1
a 1
a 2
a 3
a 4
a 5
a 6
b 2
b 3
b 4
b 5
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
2
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
B
A
a
a
p
r
r
r
e
e
t
t
i
La plus longue sous- séquence com mune est donc de lon gueur 3. C’est : art, comme nous le
montrons dans la question suivante.
8) En par tant de l’élé ment T (n, m) du tableau, la déter mi na tion d’une sous- séquence com -
mune de lon gueur maximale se fait à rebours, depuis le der nier carac tère jus qu’au pre mier,
de la manière sui vante ; si a i = b j alors on conserve la lettre a i et on se place dans la posi -
tion (case) T (i – 1, j – 1) ; si a i 2 b j , on se place dans la posi tion du tableau T ( i – l, j) ou
T (i, j – 1) de valeur maximale.
Ainsi dans notre exemple en par tant de T (6, 5) on suit la tra jec toire sui vante (cette tra jec toire
n’est pas unique) : on se posi tionne en T (5, 5) puisque a 6 5 e 2 b 5 5 t (on aurait aussi bien pu
se posi tion ner en T (6, 4) car Τ (5, 5) = T (6, 4) = 3), ensuite a 5 = b 5 et le carac tère t est conservé et
l’on se posi tionne en T (4, 4), puis en T (3, 4), puis en T (3, 3) où la lettre r est conser vée ; ensuite
on se posi tionne en T (2, 2) puis en T (2, 1), le carac tère a est conservé et l’on arrive en T (0, 0) et
l’algo rithme s’arrête. La plus longue sous- séquence com mune reconnue est donc : art.
4.3 Ce pro blème connu depuis l’Anti quité, jouit d’un cer tain regain d’actua lité, car il est ana logue
à celui de l’éta ge ment des fusées. Les anciens le trai taient par des méthodes arith mé tiques, voire
géo mé triques. Mais il peut consti tuer aussi une appli ca tion de la pro gram ma tion dyna mique.
1) Nous remar que rons sim ple ment que le nombre de voyages effec tués par l’ani mal
décroît de deux chaque fois que la charge dis po nible dimi nue de 100 kg. Cela peut per -
mettre de décom po ser le pro blème en « phases », selon qu’après 2n + 1 voyages il reste
n 3 100 , 1 n 2 12 3 100 , c , 100 kg de nour ri ture dis po nible.
• Partant du point A où 500 kg de nourriture sont disponibles, on va chercher le point B où
l’on peut apporter 400 kg : pour cela la bête parcourra (500 – 400)/0,5 = 200 km constitués
de 4 allers-retours entre A et B, suivis d’un aller AB ; soit au total 9 fois la distance AB ;
ainsi la distance de A à B vaut : 200/9 = 22,22 km.
• Partant de B, on va chercher le point C où on peut apporter 300 kg : pour cela la bête parcourra
(400 – 300)/0,5 = 200 km constitués de 3 allers-retours entre B et C, suivis d’un aller BC ; soit
au total 7 fois la distance BC ; ainsi la distance de B à C vaut : 200/7 = 28,56 km.
• Puis pour constituer un stock de 200 kg en D, la bête fera 2 allers-retours ente C et D, suivis
d’un aller CD ; ainsi CD = 200/5 = 40 km.
460
7) Nous obte nons le tableau sui vant :
b 1
a 1
a 2
a 3
a 4
a 5
a 6
b 2
b 3
b 4
b 5
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
2
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
B
A
a
a
p
r
r
r
e
e
t
t
i
La plus longue sous- séquence com mune est donc de lon gueur 3. C’est : art, comme nous le
montrons dans la question suivante.
8) En par tant de l’élé ment T (n, m) du tableau, la déter mi na tion d’une sous- séquence com -
mune de lon gueur maximale se fait à rebours, depuis le der nier carac tère jus qu’au pre mier,
de la manière sui vante ; si a i = b j alors on conserve la lettre a i et on se place dans la posi -
tion (case) T (i – 1, j – 1) ; si a i 2 b j , on se place dans la posi tion du tableau T ( i – l, j) ou
T (i, j – 1) de valeur maximale.
Ainsi dans notre exemple en par tant de T (6, 5) on suit la tra jec toire sui vante (cette tra jec toire
n’est pas unique) : on se posi tionne en T (5, 5) puisque a 6 5 e 2 b 5 5 t (on aurait aussi bien pu
se posi tion ner en T (6, 4) car Τ (5, 5) = T (6, 4) = 3), ensuite a 5 = b 5 et le carac tère t est conservé et
l’on se posi tionne en T (4, 4), puis en T (3, 4), puis en T (3, 3) où la lettre r est conser vée ; ensuite
on se posi tionne en T (2, 2) puis en T (2, 1), le carac tère a est conservé et l’on arrive en T (0, 0) et
l’algo rithme s’arrête. La plus longue sous- séquence com mune reconnue est donc : art.
4.3 Ce pro blème connu depuis l’Anti quité, jouit d’un cer tain regain d’actua lité, car il est ana logue
à celui de l’éta ge ment des fusées. Les anciens le trai taient par des méthodes arith mé tiques, voire
géo mé triques. Mais il peut consti tuer aussi une appli ca tion de la pro gram ma tion dyna mique.
1) Nous remar que rons sim ple ment que le nombre de voyages effec tués par l’ani mal
décroît de deux chaque fois que la charge dis po nible dimi nue de 100 kg. Cela peut per -
mettre de décom po ser le pro blème en « phases », selon qu’après 2n + 1 voyages il reste
n 3 100 , 1 n 2 12 3 100 , c , 100 kg de nour ri ture dis po nible.
• Partant du point A où 500 kg de nourriture sont disponibles, on va chercher le point B où
l’on peut apporter 400 kg : pour cela la bête parcourra (500 – 400)/0,5 = 200 km constitués
de 4 allers-retours entre A et B, suivis d’un aller AB ; soit au total 9 fois la distance AB ;
ainsi la distance de A à B vaut : 200/9 = 22,22 km.
• Partant de B, on va chercher le point C où on peut apporter 300 kg : pour cela la bête parcourra
(400 – 300)/0,5 = 200 km constitués de 3 allers-retours entre B et C, suivis d’un aller BC ; soit
au total 7 fois la distance BC ; ainsi la distance de B à C vaut : 200/7 = 28,56 km.
• Puis pour constituer un stock de 200 kg en D, la bête fera 2 allers-retours ente C et D, suivis
d’un aller CD ; ainsi CD = 200/5 = 40 km.