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 :

combinaisons de 0et 1?


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Inscrit en
    Mars 2008
    Messages
    50
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 50
    Points : 37
    Points
    37
    Par défaut combinaisons de 0et 1?
    salut

    je cherche une idée d'un algorithme qui génére les combinaisons des vecteurs de tailles données à partir de 0 et 1.
    par exemple pour la longueur 2 je dois avoir les vecteurs suivants: 00,01,10,11
    pour la longueur 3 je dois avoir les vecteurs suivants: 000,001,010,100,011,101,110,111
    .....etc
    merci d'avance

  2. #2
    Alp
    Alp est déconnecté
    Expert éminent sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Points : 11 860
    Points
    11 860
    Par défaut
    Une méthode possible mais assez lourde peut-être :
    Tu fixes le premier à 0. Tu fixes le second à 0. Etc... jusqu'à N (la taille du vecteur).
    Et en gros, tu vas choisir un ordre (soit en partant du premier, soit du dernier), et tu vas faire varier celui que tu as choisi. Et ainsi de suite jusqu'à tous les avoir fait varier. Mais dès que tu en modifies un, tu recalcules les combinaisons.

    Pour ton problème il doit y avoir des algorithmes connus mais je ne connais pas leurs noms.

  3. #3
    Membre éprouvé

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2007
    Messages
    979
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Décembre 2007
    Messages : 979
    Points : 1 256
    Points
    1 256
    Par défaut
    Salut,
    C'est pas simplement une question de base 2 ?

    0 à 11..1 (n fois 1).
    On connais deja la taille, base 10 de 11..1 + 1 .
    AlloSchool, votre école sur internet.

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Bonjour,

    étant donné que tu veux toutes les combinaisons, tu peux faire une recherche récursive exhaustive.
    Tu génères toutes les combinaisons.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    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 : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Bonjour,

    étant donné que tu veux toutes les combinaisons, tu peux faire une recherche récursive exhaustive.
    Tu génères toutes les combinaisons.
    C'est meme possible en itératif:

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     
    // compute next binary number
    public static boolean next(int[] number) {
    	int i=0;
    	while(i<number.length && number[i]==1) number[i++]=0;
    	if (i>=number.length) return false;
    	number[i]=1;
    	return true;	
    }
     
    // display all binary numbers of a given length
    public static void main(String[] args) {
    	int[] number = new int[]{0,0,0,0};  // 4 bits
    	do {
    		System.out.println( Arrays.toString(number) );
    	} while(next(number));
    }

    Une version pour n'importe quelle base:
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    public static boolean next(int[] number, int base) {
    	int i=0;
    	while(i<number.length && number[i]==(base-1)) number[i++]=0;
    	if (i>=number.length) return false;
    	number[i]++;
    	return true;	
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut !

    Tu peux commencer par générer une suite de nombres entiers de 0 à 2^N-1, puis les décortiquer. En Fortran, c'est assez simple grâce à l'instruction Equivalence et à la fonction BTest. L'exemple ci-dessous devrait t'inspirer.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    C
    C **********************************************************************
    C
          Subroutine AS0112
    C
    C     Représentation d'une variable de type Integer*2
    C
    C **********************************************************************
    C
    C     Déclarations
    C
          Implicit None
    C
          Character*80 S
          Integer*2 I
          Integer*1 I1(2),K
          Equivalence (I1,I)
    C
    C **********************************************************************
    C
    C     Instructions exécutables
    C
          Open (4,File='AS0112.txt')
       10 Write (*,*) ' '
          S='Tapez un entier entre -32768 et +32767'
    	Call U003(S,Len_Trim(S))
    	S='(Ctrl-Z pour quitter)'
    	Call U003(S,Len_Trim(S))
    	Read (*,*,End=99,Err=20) I
    	Go To 30
    C
       20	S='Donnée incorrecte'
          Call U003(S,Len_Trim(S))
    	Go To 10
    C
       30 Write (*,'(/11X,A)') 'Adr+1    Adr'
          Write (*,'(I7,3X,2(1X,8I1))') I,
         *  (-BTest(I1(2),K),K=7,0,-1),(-BTest(I1(1),K),K=7,0,-1)
          Write (4,'(/11X,A)') 'Adr+1    Adr'
          Write (4,'(I7,3X,2(1X,8I1))') I,
         *  (-BTest(I1(2),K),K=7,0,-1),(-BTest(I1(1),K),K=7,0,-1)
    	Go To 10
    C
       99 Close (4)
          Return
          End
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  7. #7
    Nouveau membre du Club
    Inscrit en
    Mars 2008
    Messages
    50
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 50
    Points : 37
    Points
    37
    Par défaut
    salut
    grace a vous réponse j'ai écrit mon programme qui répond a mes besoin
    merci mes amis

  8. #8
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Ceci n'est qu'un cas très particulier de l'ensemble des applications de E dans F où F={0;1} et E ensemble à un deux, trois ou n éléments.
    Voici donc un tout petit pgm Python qui génère TOUTES les applications d'un ensemble dans un autre:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # -*- coding: cp1252 -*-
    #générer toutes les applications de E dans F 
     
    def power(n,F):
        G=[[x] for x in F]
        for i in range (0,n-1):
            G= [y+[x] for y in G for x in F]
        return G
     
    def main():
        E=[1,2,3]
        F=['a','b']
        print power(len(E),F)
     
    if __name__ == '__main__':
        main()
    Ici il suffirait de prendre F=[0,1] dans main pour avoir tous les nombres binaires à 3 chiffres.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  9. #9
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    C'était pas plus simple de faire une boucle sur 0 2^n, de convertir le nombre en binaire en le complétant pas des 0 pour que sa taille soit n ?

    Ca tient en 3 lignes.
    Je ne répondrai à aucune question technique en privé

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

Discussions similaires

  1. [Algo] Trouver un arrangement ou une combinaison d'éléments
    Par Morvan Mikael dans le forum Algorithmes et structures de données
    Réponses: 16
    Dernier message: 20/04/2013, 12h46
  2. [combinatoire] combinaisons de toutes longueur
    Par Toorop dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 16/02/2007, 17h08
  3. Combinaison de deux selects simples
    Par devtrax dans le forum Langage SQL
    Réponses: 5
    Dernier message: 09/09/2004, 15h09
  4. Somme de combinaisons
    Par phig dans le forum Mathématiques
    Réponses: 3
    Dernier message: 24/10/2003, 16h03
  5. Réponses: 2
    Dernier message: 22/07/2002, 19h02

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