Chercher Algo

[invite717d01ee]

Bonjours ;
Je travaille actuellement sur un sujet qui me tient à coeur pour un but curatif voilà j'ai une combinaison de 06 chiffres qui est la somme d'un nombre je m'explique :
a partir dur nbr 7 je construit une combinaison de 06 chiffres cad :
211111
221110
222100
311110
321100
322000
411100
421000
430000
511000
520000
610000
700000
de façon que chaque ligne de chiffre a la somme de 7
j'ai essayer de construire un algo corespondant masi sans résultats
aider moi svp
Yacine1
### Pas d'adresse mail sur le forum, remplissez le profil
@+
-----

[invite9c9b9968]

Message déplacé en maths du supérieur. Attention à bien faire attention à l'intitulé des rubriques

G.

[invite0cea7419]

En fait, ton problème c'est le problème de la partition d'un entier N en k autres entiers n1, n2, ..., nk tels que leur somme valle N.

Ici, N=7 et k=6, mais on peut essayer de résoudre le problème pour toutes valeurs de N et k (tant que k est inférieur ou égal à N).

D'ailleurs, le nombre de manière de partitionner N en k entiers est le nombre de Stirling de deuxième espèce S(N,k). Ca devient vite assez grand, de mémoire.

Quoi qu'il en soit, je ne vais pas te décrire complètement un algorithme, mais te donner une piste : il me paraît plus simple (et je l'ai fait il y a 4 ou 5 ans) de générer ces partitions dans l'ordre lexicographique. D'abord, générer toutes celles qui commencent par un 1, puis toutes celles qui commencent par un 2, etc. De la sorte, quand tu fixes le premier chiffre à x, ce que tu as derrière est une partition de (N-x) à (k-1) éléments. Tu t'es donc ramené à un problème plus petit, et donc une solution récursive semble plus naturelle (en mémorisant les résultats au fur et à mesure, si c'est possible).

Tu veux sûrement aussi (comme tu le fais dans ton exemple) te restreindre aux partitions écrites dans l'ordre décroissant (4=31 et pas 4=13). Ca simplifie encore plus

[invite717d01ee]

Je vais me penchez sur la question est je vous au courant merci et bon dev
yacine1

[A voir en vidéo sur Futura]