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

C Discussion :

Élimination intervalles inclus


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut Élimination intervalles inclus
    Bonjour,
    voici mon problème:
    j'ai des intervalles voici un exemple: [5,10],[30,90][70,89],[15,45],[67,87],[6,9].....

    comme vous voyez l'intervalle [6,9] est inclut dans [5,10] et l'intervalle [70,89] est inclut dans [30,90] et [67,87] est inclut dans [30,90].
    Moi je veux éliminer ces intervalles et bien en même temps diminuer la taille du tableau d'intervalles.
    voici mon code:
    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
    void table_optimiser(ligne table[], int n){
    int i=0;int j=0;int k=0;
        for(i=0;i<n;i++) //pour fixer chaque intervalle
        {
         for(j=1;j<n;j++) //pour parcourir les autres intervalles et trouver les intervalles inclut.
         {
            if((table[i].posin<=table[j].posin)&&(table[i].posend>=table[j].posend))
            {
                for (k=j;k<n;k++)
                {
                   table[k]=table[k+1]; //pour parcourir le reste du tableau et éliminer l'intervalle inclut
                }
                n--;
            }
         }
        }
        for (j = 0; j < n; j++){affichage_table(table[j],j);}
    }
    est-ce que vous avez une idée? ou une autres approches?
    Merci.

  2. #2
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Par exemple, tu pourrais faire une fonction qui détermine l'intersection de deux ensembles, et une autre qui détermine si un ensemble contient un autre.
    Ca simplifierait la suite du code.

    Tu devrais te pencher sur les listes chainées, plutot que les tableaux.

  3. #3
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut
    est-ce que ma solution n'est pas exacte?

  4. #4
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    exacte, si, ca a l'air, mais elle te coute très très cher.
    Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

    Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir

  5. #5
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut
    Citation Envoyé par leternel Voir le message
    exacte, si, ca a l'air, mais elle te coute très très cher.
    Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

    Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir
    même si la logique est exacte mais elle ne marche pas dans mon cas.

  6. #6
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Billets dans le blog
    21
    Par défaut
    Premier point, comme le dit leternel, la question n'est pas seulement de savoir si un intervalle en inclut un autre mais de savoir s'il y a intersection entre eux: on peut simplifier [5, 10] et [8, 12] par [5, 12].

    Si le tableau est trié la fusion des intervalles se fait en un seul passage. Le tri prend grosso modo n×log n donc au total tu as n*(log n + 1) tandis que tu es à n^3 à première vue.

  7. #7
    Membre actif Avatar de Abacar94
    Homme Profil pro
    L2 Math-informatique
    Inscrit en
    Novembre 2015
    Messages
    103
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Niger

    Informations professionnelles :
    Activité : L2 Math-informatique

    Informations forums :
    Inscription : Novembre 2015
    Messages : 103
    Par défaut
    Citation Envoyé par leternel Voir le message
    exacte, si, ca a l'air, mais elle te coute très très cher.
    Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

    Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir
    ta méthode est plus professionnel.........tu pourrais lui donner un début de code pour qu'il puisse l'essayer; histoire qu'il vois la différence

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

Discussions similaires

  1. Réponses: 22
    Dernier message: 03/03/2014, 16h16
  2. Réponses: 1
    Dernier message: 04/04/2013, 10h37
  3. Inclusion d'intervalles entiers et structure de donnée
    Par SpiceGuid dans le forum Langages fonctionnels
    Réponses: 8
    Dernier message: 03/05/2012, 15h50
  4. Tester l'inclusion d'une valeur dans un ensemble d'intervalle
    Par Benoit_T dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 22/06/2010, 16h19
  5. éliminer un caractere d'un string
    Par no-vice dans le forum Langage
    Réponses: 5
    Dernier message: 09/08/2002, 14h55

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