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

Mathématiques Discussion :

algorithme de factorisation en somme de nombre


Sujet :

Mathématiques

  1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2009
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2009
    Messages : 78
    Points : 59
    Points
    59
    Par défaut algorithme de factorisation en somme de nombre
    Bonjour à tous

    Je développe une appli en VBA et j'aurais besoin de retrouver toutes les solutions de sommes de termes d'un nombre plus grand. exemple :

    Voici mes nombre sources:
    48 50 51 52 54 56 57 58 60 62 63 64

    Voici le nombre à factoriser : 321

    Solutions :
    - 2*64+58+3*45
    - 6*45+51
    - 5*54+51
    ...

    si je ne me trompe pas, cela reviendrait à trouver les solutions de :
    321 = a*48 + b*50 + c*51 + d*52 + e*54 +...
    sachant que le nombre à factoriser n'est jamais un nombre premier.

    J'avais commencé à faire un code du genre :
    NbPv=321
    Nsource(12)=(48,50,51,52,54,56,57,58,60,62,63,64)

    pour j = 1 à 12
    si NbPv/Nsource(12-j) > 0
    NbNsource = entier(NbPv / Nsource(12-j))
    NbPv = NbPv - NbNsource*Nsource(12-j)
    FinSi
    Suivant

    Mais je me retrouve avec une partie entière qui me gène.

    est ce que vous avez déjà eu à faire une factorisation en somme de termes?
    Quelle méthode vous semble abordable?

    Merci beaucoup pour votre aide!

    Pierre

  2. #2
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    S'il n'y a pas beaucoup de chiffres et qu'ils sont petits, comme dans l'exemple, tu peut tout simplement essayer toutes les combinaisons.

    Je ne sais pas s'il existe un meilleur algorithme, ça ressemble à un problème NP complet.

  3. #3
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    as-tu beaucoup de nombres sources?
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  4. #4
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2009
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2009
    Messages : 78
    Points : 59
    Points
    59
    Par défaut
    Bonsoir,

    Il y a environ 30 sources et les inconnues ne montent jamais au dessus de 20.

    Effectivement, ça peut réduire les possibilités

    Cordialement,

    Pierre

  5. #5
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    ALors 30 c'est beaucoup... ton problème s'apparente à celui "du sac à dos":

    http://interstices.info/jcms/c_19213...e-du-sac-a-dos

    Si ton nombre cible N n'est pas "trop gros" par rapport à tes nombres sources Si, tu peux quand même faire une recherche exhaustive:

    - tu tries tes Si par ordre croissant
    - tu ne considères que les Si<=N, disons S1...Sp
    - tu prends k=1+partie entière du max des N/Si
    - tu testes tous les x1S1+...xpSp avec tous les xi<=k.
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  6. #6
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2009
    Messages
    78
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2009
    Messages : 78
    Points : 59
    Points
    59
    Par défaut
    Effectivement, c'est le problème du sac à dos.

    Merci de ton aide je vais voir ça!

    Bonne journée

    Cordialement,

    pierre

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

Discussions similaires

  1. algorithme de factorisation en somme de nombre
    Par 7ider5 dans le forum Macros et VBA Excel
    Réponses: 9
    Dernier message: 26/02/2010, 10h36
  2. Excel somme de nombre rouge
    Par pavilion dans le forum Macros et VBA Excel
    Réponses: 2
    Dernier message: 12/07/2007, 06h39
  3. algorithme qui détecte et compte le nombre de visages et leur temps d'attention
    Par aptchagi dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 13/06/2007, 15h46
  4. Somme de nombre arrondis
    Par Lou_anne dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 11/05/2007, 17h22
  5. Somme de nombres limitée
    Par DC dans le forum SQL Procédural
    Réponses: 7
    Dernier message: 29/11/2005, 14h54

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