Discussion :

[mido1951]

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.

[ternel]

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.

[mido1951]

est-ce que ma solution n'est pas exacte?

[ternel]

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

[mido1951]

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.

[stendhal666]

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.

[Abacar94]

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