Licence Info
Algorithmique Avancée
TD 5: 24-25/10/05
Programmation Dynamique
- On considère le calcul du nombre de partitions
d'un entier positif n.
Une partition est une division de n en parts où l'ordre des
parts
n'est pas pris en compte. Donc, par exemple, 4 a les 5 partitions,
{4}, {3,1}, {2,2}, {2,1,1} et {1,1,1,1}.
- Dans le cour on vous a donné un algorithme de ce
calcul en utilisant une récurrence sur le
nombre de partitions avec plus grande part i,
- En donner un autre avec une récurrence sur le
nombre de partitions en j parts,
- Quelle est la différence entre les deux
récurrences? Pourquoi?
- Donner un autre algorithme plus performant qui a comme
paramètre un majorant
de la plus grande part (ou du nombre de parts) au lieu du nombre exact.
- Je veux découper une pièce de bois en sections de
superficie maximum 1000 cm2. Le bord supérieur et le
bord inférieur de la pièce sont des lignes brisées
A1,¼,An d'une
part et B1,¼,Bm
de l'autre,
et les extrémités latérales sont les segments A1,B1
et An,Bm.
Je dois couper suivant des traits rectilignes joignant certains des
points Ai
à certains des points Bj
sans faire deux coupes qui se croisent, sauf à un des points Ai
ou Bj.
Il y a deux tableaux Cout et Droite à deux dimensions avec les
données:
Cout[i][j] le coût de faire une coupe de Ai à Bj
et Droite[i][j]
la superficie en cm2 de la partie à droite de cette
coupe.
Donner un algorithme qui calcule le coût minimum de la
découpe
(en utilisant la programmation dynamique).
File translated from
TEX
by
TTH,
version 3.05.
On 21 Oct 2005, 16:11.