Algorithmes récursifs

[Salimoush]

Salut! Quelqu'un pourrait me donner la solution de ce problème svp?
Ca fait des jours que je me peux la tête dessus :mur:

Problème:
Etant donné un entier positif n, on dit que la suite finie (n1, n2, . . . , nk) est un partage de n en
k parts si
(i) ni > 0 pour i = 1, 2, . . . , k,
(ii) ni ni+1 pour i = 1, 2, . . . , k 1 et
(iii) n1 + n2 + . . . + nk = n.
Par exemple, (5, 3, 2, 2, 1) est un partage de 13 en 5 parts puisque les éléments sont strictement
positifs, en ordre décroissant (pas nécessairement strict) et
5 + 3 + 2 + 2 + 1 = 13.
On a aussi que (13) est un partage de 13 en 1 part.
(a) (6 points) Donnez les 11 partages du nombre 6.
(b) (14 points) On aimerait écrire un algorithme qui calcule la liste de tous les partages d’un
nombre donné n. Il semble difficile de le faire directement, mais il existe une façon de le
faire de fa¸con récursive.
La première idée est d’introduire un paramètre supplémentaire qui indique le nombre de
parts qu’on souhaite dans le partage. Plus précisément, on aimerait implémenter une
fonction Partages(n, k) qui retourne une liste de tous les partages du nombre n en exactement
k parts. Par exemple, on s’attend `a ce que Partages(4, 2) retourne la liste
[(3, 1),(2, 2)], puisque les seuls partages de 4 en exactement 2 parts sont (3, 1) et (2, 2).
En introduisant ce paramètre supplémentaire, il est maintenant plus facile de formuler le
problème de fa¸con récursive. En effet, un partage d’un nombre n en exactement k parts
peut être obtenu de 2 façons :
(i) Soit il est obtenu à partir d’un partage de n 1 en au plus k 1 parts, puis on lui
ajoute une part de 1;
(ii) Soit il est obtenu à partir d’un partage de n;)k en exactement k parts, puis on ajoute
1 à chacune de ces k parts.

Ecrire une fonction récursive qui retourne une liste de tous les partages du nombre n en
exactement k parts. Vous pouvez supposer que la syntaxe et les fonctions suivantes sont
valides et déjà implémentées :
• L [x, y] crée une liste avec les valeurs x, y et la place dans la variable L.
• L [ ] crée une liste vide.
• L.Ajouter(x) ajoute la valeur x `a la fin de la liste L. Par exemple si L = [x, y] et
que vous faites L.Ajouter(z), alors vous obtiendrez la liste [x, y, z].
• p Partage([3, 2, 1]) crée le partage (3, 2, 1) et le place dans la variable p.
• p[i] y modifie la i-ème valeur du partage p. Par exemple, si p est le partage (3, 2, 1),
alors p[0] 4 transforme le partage en (4, 2, 1) (les indices commencent à 0).

En utilisant ce squelette:
1: fonction Partages(n, k : entiers) : liste de partages
2: si n < k alors
3: A compléter
4: sinon si k = 1 alors
5: A compléter
6: sinon si k = n alors
7: A compléter
8: sinon
9: A compléter
10: fin si
11: retourner L . On retourne la liste calculée dans une des trois parties
12: fin fonction

Merci beaucoup pour votre aide!