Votre question

mettre en place un algorithme

Tags :
  • Adresse IP
  • Programmation
Dernière réponse : dans Programmation
23 Novembre 2005 19:39:24

Bonjour tt le monde.
Je voudrais savoir si qqun pouvait m'aider sur un algorithme a faire. On me demande d'ecrire une procédure qui prend un nombre entier comme parametre et qui renvoie une liste comportant la liste de toute les decomposition de ce nombre en somme de terme positif
exemple pour n=5
[ [5], [4,1], [3,2], [1,1,3], [1,2,2], [1,1,1,2] ]

en fait ma difficulté c de trouver un systeme de boucle permettant de tout parcourir car si on denombre le nombre de somme possbile.

En fait là ou je voudrais de l'aide c pour mettre en place une boulcle qui permet de trouver toutes les decompositions possibles de n en p chiffres par exemple (ensuite je fera une autre boucle pr faire tous les p) et qui ne tient pas compte des repetitions car ca comlplique le probleme...

-Je fais ca en langage maple mais si vous avez juste une idée (progra en francais sans tenir compte des problemes liés à la syntaxe et tout cà car le pb c de modeliser ceci) ca m'aiderais bcp.
Voilà merci à vous.

si ça peut vous être utile j'ai calculer le nombre de couple obtenus si on ne tient pas compte des repetitions (methode bourrin) je trouve que pr decomposer n en p chiffres :
card= somme(i0=1à n)somme(ip-1<ip-2<ip-3<...<i1<i0<n) de (n-somme(j=0 à p-1) de ij)

Autres pages sur : mettre place algorithme

a b L Programmation
23 Novembre 2005 22:23:50

oui c'est pas évident, il faudrait partir à 1 partout puis répartir la valeur m = n-p sur tous les nombres.
Pour placer une unité, il faut faire une boucle sur tous les éléments.
Il faut faire pareil en déplaçant une autre unité, donc faire une boucle de boucle, et ainsi de suite (m fois) pour les autres.
Donc en fait ce serait un empilement de m boucles (un par unité), chaque boucle déplaçant l'unité.
Le plus simple serait de faire une fonction récursive qui déplace une ième unité et récursivement i - 1 unités.

Donc je pense qu'il faut trouver un moyen plus simple pour tout répartir.
Déjà on peut optimiser en remarquant que dans une boucle, si ai = aj, ce n'est pas la peine de mettre l'unité sur aj, car si on la mettait sur ai, on n'aurait qu'une simple permutation.
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS