IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Repartitions p parmis [0..N]


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 102
    Par défaut Repartitions p parmis [0..N]
    Bonsoir tout le monde, c'est encore moi!
    cette fois-ci voici mon problème

    soit une liste d'entier [0..N]
    soit un chiffre p

    j'ai besoin de générer toutes les manières possibles de prendres p chiffres parmis [0..N] sachant que la somme de ces p chiffres doit être égale à N.

    Je veux pas forcément l'algo (quoi que^^) mais au moins une idée de départ

    merci bien

    Yann

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Darksnakes Voir le message
    j'ai besoin de générer toutes les manières possibles de prendres p chiffres parmis [0..N] sachant que la somme de ces p chiffres doit être égale à N.
    Prendre p chiffres avec reprise ? C'est à dire pour N=9, P=3 est-ce que les solutions [0,0,3] ou [1,1,1] sont valides ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 102
    Par défaut
    oui avec reprise, oublier de le préciser!!

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    dans ce cas, la question à été traitée hier:

    http://www.developpez.net/forums/d64...ableau-valeurs

    (regarde à partir du post #8)

    Bon, il faudra quelques adpations pour ton problème particulier, mais la methode est similaire.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    102
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 102
    Par défaut
    parfait, c'est exactement ce qu'il me fallait, merci bcp!!!!!

  6. #6
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Je ne suis pas sûr qu'on parle de la même chose, a priori ses valeurs sont fixées, ça ressemble beaucoup plus à une version légèrement modifiée du problème des partitions d'entiers (voir ce défi pour un tas de programmes plus ou moins optimisés s'attaquant à la question).

    --
    Jedaï

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Je ne suis pas sûr qu'on parle de la même chose, a priori ses valeurs sont fixées, ça ressemble beaucoup plus à une version légèrement modifiée du problème des partitions d'entiers
    Tel que j'ai compris le problème, la recursion ressemblerait à ca:

    Soit X un tableau de taille p tel que Somme{X}=S, alors X = [ v , Y ] avec
    - "v" un entier entre 0 et N (et meme etre 0 et min(S,N))
    - "Y" un tableau de taille p-1 tel que Somme{Y}=S-v

    Ce qui est en gros le code posté dans la discussion que j'indiquais.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Comment bloquer access internet à 20 users parmis 70 ?
    Par kikica dans le forum Autres Logiciels
    Réponses: 2
    Dernier message: 07/09/2005, 17h42
  2. Réponses: 2
    Dernier message: 24/08/2005, 10h59
  3. sélection d'un max parmi plusieurs champs
    Par invitésuprise dans le forum Langage SQL
    Réponses: 2
    Dernier message: 12/08/2005, 13h49
  4. Recuperation d'une seule ligne parmi N via un join
    Par morti dans le forum Langage SQL
    Réponses: 5
    Dernier message: 04/08/2005, 13h48
  5. Réponses: 8
    Dernier message: 05/05/2004, 12h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo