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

Java Discussion :

Problème sur un excercice d'algorithmie


Sujet :

Java

  1. #1
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut Problème sur un excercice d'algorithmie
    Bonjour, je n'arrive pas à résoudre ce problème.

    Mon algo ne passe que 2 test, les autres il est faux et trop lent... Merci d'avance


    ---------------------


    Choisir un manteau pour les vacances est toujours difficile, surtout lorsque l'on ne sait pas encore où l'on part. En effet chaque manteau est adapté à une certaine plage de température et vous aimeriez bien choisir un manteau qui s'adaptera à vos besoins.

    Vous voilà dans un vaste magasin de manteaux, un peu perdu dans l'énorme choix proposé. Pour chacun des manteaux du magasin, vous connaissez l'intervalle de température qui lui correspond.

    Avec votre logique impassible, vous décidez d'inventer un critère qui vous aidera à choisir votre manteau : Le niveau d'un manteau sera défini comme le nombre d'autres manteaux du magasin dont l'intervalle de température est contenu dans l'intervalle de celui-ci.

    Vous décidez de sortir votre ordinateur et d'écrire un programme qui déterminera le niveau maximal que l'on peut trouver.

    LIMITES DE TEMPS ET DE MEMOIRE (Langage : Java)

    Temps : 0.5s sur une machine à 1Ghz.
    Mémoire : 8000 Ko.

    CONTRAINTES

    1 <= nbManteaux <= 20 000.
    0 <= temperature_inf, temperature_sup <= 500 000 000, l'intervalle de température d'un manteau.

    ENTRÉE

    Sur la première ligne de l'entrée, votre programme lira un unique entier : nbManteaux, le nombre de manteaux du magasin.

    Il lira ensuite nbManteaux lignes contenant chacune deux entiers indiquant l'intervalle de température d'un manteau.

    SORTIE

    Votre programme affichera un unique entier : le niveau maximal d'un manteau.

    EXEMPLE

    entrée :
    8
    1 3
    2 5
    5 8
    3 6
    2 5
    3 8
    3 6
    3 8

    sortie :
    4

    COMMENTAIRES

    Dans l'exemple présenté, les niveaux des manteaux sont, dans l'ordre : 0, 1, 0, 1, 1, 4, 1, 4.

    Le résultat à afficher est donc 4.

  2. #2
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 582
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 582
    Par défaut
    Hello,

    Et, hum. Et donc, ton algo, quel est-il ?
    Nous risquons d'avoir du mal à le corriger sans le voir.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  3. #3
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut
    Dans mon code il y a un objet Manteau et un Temperature.

    J'ai fait un tableau de Temperature[] qui est trié.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    Manteau:
        min, max: Températures minimum et maximum du Manteau
        lvl: Le niveau du manteau
     
    Temperature:
        mes: La valeur de la température
        id: L emplacement du Manteau correspondant dans le tableau Manteau[]
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Parcourir le tableau de Temperature[] avec i
      temperatureMax <- (récupère la Temperature max du Manteau)
      j <- i
      Tant que la Temperature à l index j est inférieure à temperatureMax
        Si le Manteau de la Temperature à l index j est dans l intervalle i-temperatureMax alors
          incrémenter le niveau du Manteau
        fin si
      fin tant que
    C est lent mais plus rapide que de tester chauque combinaison de Manteau.


    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    import java.util.Arrays;
     
    import java.util.Scanner;
     
    public class Main{
     
    	public static Manteau[] mants;
     
    	public static Temperature[] temps;
     
    	public static int nbMants;
     
    	public static boolean isMinTemperature(Temperature t){
    		return t.mes == mants[t.id].min;
    	}
     
    	public static void main(final String[] args){
    		Scanner s = new Scanner(System.in);
     
    		nbMants = s.nextInt();
    		mants = new Manteau[nbMants];
    		temps = new Temperature[nbMants * 2];
     
    		for(int i = 0; i < nbMants; i++){
    			int min = s.nextInt(), max = s.nextInt();
     
    			mants[i] = new Manteau(min, max);
     
    			temps[i * 2] = new Temperature(min, i);
    			temps[(i * 2) + 1] = new Temperature(max, i);
    		}
     
    		Arrays.sort(temps);
     
    		// Pour toutes les Temperature
    		for(int i = 0; i < nbMants * 2; i++){
    			Temperature tI = temps[i];
    			Manteau mI = mants[tI.id];
     
    			if(isMinTemperature(tI)){
    				int j;
    				Temperature tJ;
    				Manteau mJ;
    				// Parcours en arrière
    				if(i > 0){
    					j = i - 1;
    					tJ = temps[j];
    					mJ = mants[tJ.id];
     
    					while(tI.mes == tJ.mes && i > 0){
    						if(isMinTemperature(tJ) && mJ.max <= mI.max){
    							mJ.lvl++;
    						}
     
    						j--;
    						if(j >= 0){
    							tJ = temps[j];
    							mJ = mants[tJ.id];
    						}
    					}
    				}
     
    				// Et en avant
    				if(i < nbMants * 2){
    					j = i + 1;
    					tJ = temps[j];
    					mJ = mants[tJ.id];
     
    					while(tI.mes <= mI.max && j < nbMants * 2){
    						if(isMinTemperature(tJ) && mJ.max <= mI.max){
    							mJ.lvl++;
    						}
     
    						j++;
    						if(j < nbMants * 2){
    							tJ = temps[j];
    							mJ = mants[tJ.id];
    						}
    					}
    				}
    			}
    		}
     
    		int lvlMax = 0;
    		for(int i = 0; i < nbMants; i++){
    			lvlMax = Math.max(lvlMax, mants[i].lvl);
    		}
     
    		System.out.println(lvlMax + 1);
    	}
    }
     
    class Manteau{
     
    	public int min, max, lvl = 0;
     
    	public Manteau(int min, int max){
    		this.min = min;
    		this.max = max;
    	}
    }
     
    class Temperature implements Comparable<Temperature>{
     
    	public int mes, id;
     
    	public Temperature(int mes, int id){
    		this.mes = mes;
    		this.id = id;
    	}
     
    	public int compareTo(Temperature o){
    		return new Integer(mes).compareTo(new Integer(o.mes));
    	}
    }

  4. #4
    Membre confirmé Avatar de Tr0n33
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2014
    Messages
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Service public

    Informations forums :
    Inscription : Novembre 2014
    Messages : 69
    Par défaut
    La solution intuitive est simple : parcourir l'ensemble des intervalles et calculer pour chacun d'entre eux le nombre d'intervalles qu'ils contiennent (soit O(n²)). En fait l'important c'est la notion d'intervalles dans ce problème.

    L'objectif est de parcourir une liste d'intervalles et de dénombrer les inclusions (nombre max d'intervalles contenues dans celui qu'on regarde). Grosso modo, j'aurais plutôt utilisé une seule structure de ce style : ([1,3], [2,5], [3,5]...). De mon souvenir la complexité de l'algorithme devrait être en O(n *log n) (Vous me direz le pif, vieille habitude des exercices de l'université sans doute).

    Notons les intervalles I(k) = [Tmin(k), Tmax(k)] (qui sont l'intervalle de température d'un manteau).
    Tous ces intervalles sont contenues dans une liste/tableau de tous les manteaux.

    1- On trie la liste des intervalles par température minimale Tmin(k) croissante et en cas d'égalité par température Tmax(k) max décroissante.
    2- On parcourt la liste (des manteaux) et on enregistre la position p(1, k) de chaque intervalle.
    3- On trie de nouveau la liste mais par température maximaml Tmax(k) décroissante et en cas d'égalité par température Tmin(k) croissante.
    4- On parcourt alors cette liste et on enregistre la position p(2,k) de chaque intervalle.

    Bilan : Le nombre d'intervalles max inclus dans un autre est alors... argmax(k) = (NbManteau - p(1,k) - p(2,k) - 1) pour k compris entre 1 et NbManteau. Pour la première position dans la liste p(i,k) = 0 par convention. On affecte alors à chaque numéro de manteau k, le nombre maximal d'inclusion.

    Est ce que c'est cela que tu indiques avec tes parcours avant/arriere ?



    Après pour l'optimisation purement Java : les déclarations de variables peuvent être positionnées en dehors des boucles (cela évite de réinstancier la donnée à chaque itération, le gain est colossale sur des grosses boucles; le compilateur n'effectuant pas cette optim même en Java 7). Il y a d'autres astuces mais cela fait très longtemps, je pense que le compilateur Java est suffisamment optimisé pour les astuces de comparaison avec 0 et d'écritures. Je suppose que l'optimisation voulu concerne surtout la complexité.

    Je ne sais pas si j'ai bon, ça fait vraiment longtemps que je n'ai plus fait d'algorithmie ^^. Pour ton algorithme, j'essaie de le faire tourner et de te faire une réponse rapidement.

  5. #5
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 582
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 582
    Par défaut
    Hello,

    je dois dire que je me triture l'esprit pour imaginer un algorithme qui marche et qui ne fasse pas du O(n²). Peut-être en triant par taille d'abord...
    Et je me triture aussi la tête pour comprendre comment sont censés marcher les algorithmes que je vois là. J'aurais bien aimé une description je dois dire -_-°.


    Du coup pour l'instant je ne peux rebondir que là-dessus :

    Citation Envoyé par Tr0n33 Voir le message
    Après pour l'optimisation purement Java : les déclarations de variables peuvent être positionnées en dehors des boucles (cela évite de réinstancier la donnée à chaque itération, le gain est colossale sur des grosses boucles; le compilateur n'effectuant pas cette optim même en Java 7).
    Hmm non, en Java il n'y a (ré)instanciation que quand il y a un new. L'endroit où on déclare une variable ne change rien à l'exécution, et n'est qu'un outil de développement pour s'organiser. Au contraire une variable devrait être déclarée au plus profond possible pour limiter sa portée aux seuls endroits où elle a un sens.
    Je ne vois pas où tu as imaginé ce "gain colossal" ni de quelle optimisation on serait en train de parler.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  6. #6
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut
    Mon algo en O(n²) est foutu je pense.

    La limite du sujet étant à 20 000 manteau il tourne à 400 000 000 itérations !

    Ce qui est beaucoup trop pour les 0.5 secondes sur une machine à 1GHz.

    J'ai maximum quelques millions seulement d'itération disponibles avec ce temps...

    PS: Il me viens une idée. Je l'écris pour ne pas l'oublier demain et au cas où ça inspirerait quelqu'un... Et si on triais les manteau en fonction de la différence de temperature (tempMax - tempMin) ?

    Ou... Si on ne triais rien du tout ??

    Car après tout le tri prends déjà O(n log n) ?


    Je vous laisse sur ces deux idées là pour ce soir, je m'y remettrais demain...

  7. #7
    Membre confirmé Avatar de Tr0n33
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2014
    Messages
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Service public

    Informations forums :
    Inscription : Novembre 2014
    Messages : 69
    Par défaut
    Hmm non, en Java il n'y a (ré)instanciation que quand il y a un new. L'endroit où on déclare une variable ne change rien à l'exécution, et n'est qu'un outil de développement pour s'organiser. Au contraire une variable devrait être déclarée au plus profond possible pour limiter sa portée aux seuls endroits où elle a un sens.
    Oula !!! My bad. J'étais sans doute en train de ruminer mon énervement quotidien au boulot. J'ai effectivement dit déclaration à la place d'instanciation. Merci de l'avoir noté, ça fait tâche (sans doute la fixette que je fais sur cette erreur que je vois bien trop souvent).

    Sinon si, j'ai vérifié, c'est bien un algo en O(n * log n) que j'ai proposé.

    Je suis en train de l'implémenter pour le tester mais à priori ça a l'air d'être bon. Il faut trier les intervalles par le minimum, puis par le maximum et faire des soustractions en fonction des positions de la liste (d'ailleurs c'est amusant que dans le problème on est appelé le chiffre que l'on cherche le niveau maximum). Grosso modo, j'ai deux parcours en O(n) et argmax que je calcule en O(n * log n). En fait c'est fondé sur la position dans les listes pour savoir qui est inclus dans quoi. Sur un processus à 1 GHz, normalement avec cette complexité et malgré les 3 étapes tu dois être en dessous de 500 ms.

  8. #8
    Membre confirmé Avatar de Tr0n33
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2014
    Messages
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Service public

    Informations forums :
    Inscription : Novembre 2014
    Messages : 69
    Par défaut
    Tout est fondé sur la position.

    Tableau des manteaux avec ton exemple :
    Intervalle cree : [1,3]
    Intervalle cree : [2,5]
    Intervalle cree : [5,8]
    Intervalle cree : [3,6]
    Intervalle cree : [2,5]
    Intervalle cree : [3,8]
    Intervalle cree : [3,6]
    Intervalle cree : [3,8]

    Trié par min (max decroissant en cas d'égalité)
    [1,3] [2,5] [2,5] [3,8] [3,8] [3,6] [3,6] [5,8]
    Trié par max (min croissant en cas d'égalité
    [1,3] [2,5] [2,5] [3,6] [3,6] [5,8] [3,8] [3,8]

    Tu vois alors rapidement qu'est ce qui est inclu dans quoi en fonction : de la position intiale, et de la position dans les deux tableaux de min.
    Par exemple tu vois que l'intervalle [5,8] est en position 3 dans le tableau de départ, qu'il est en position 8 dans le tableau des min et en position 6 dans le tableau des max. Il est donc inclu... Dans 2 intervalles, qui sont... [3,8] et [3,8]. Même exemple pour [3,6] qui est en position 6 et 7 dans le tableau des min et en position 4 et 5 dans le tableau des max. Il est donc inclu dans... 3 éléments : lui même (puisqu'il apparait 2 fois) et [3,8] deux fois

    On a ainsi non pas les éléments qui sont inclus dans quoi, mais uniquement leur nombre. Il faut bien penser à sauvegarder les positions dans les étapes de tri. L'astuce me semble donc être fondé sur une double comparaison d'un tableau de tri des températures par leur minimum d'un côté et par leur maximum de l'autre, avec une comparaison des positions dans ces tableaux. Ca devrait t'aider pour ton probleme, j'espère.

    Ca permet normalement de faire ton calcul du niveau max non ?

  9. #9
    Membre Expert
    Inscrit en
    Mai 2006
    Messages
    1 364
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 1 364
    Par défaut
    Moi, j'aurais bien tenté d'utiliser un arbre pour résoudre ce probleme grace à la propriété de transitivité évidente du probleme. Avec ca, on pourrait insérer directement chaque éléments au bon endroit.

    Ca donnerait un truc du genre:
    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    class Manteau
    {
      // Si on range directement les Elements dans cette liste triés selon min puis max croissants, ca permet de ne pas avoir à la parcourir.
      List<Manteau> fils = new ArrayList<Manteau>();
     
      int min;
      int max;
      Manteau(int min, int max)
      {
        this.min = min;
        this.max = max;
      }
     
       void addManteau(Manteau manteau)
       {
          int i = 0;
          while(i < fils.size() && manteau.min >= fils.get(i).min)
          {
             if(manteau.max <= fils.get(i).max)
             {
                fils.get(i).addManteau(manteau);
                return;
             }
             ++i;
          }
     
          // i pointe sur le premier manteau dont le min est plus grand ou bien sur fils.size()
          // Maintenant, on regarde si un ou plusieurs manteaux peuvent etre inclus dans le nouveau manteau
          while(i < fils.size() && manteau.max >= fils.get(i).max)
          {
             // Tous les manteaux ici devront etre supprimes de l'element pere (this) et inseres dans le nouvel element
             // Note qu'ici, on peut inserer directement la liste sans avoir a faire les verifications de addManteau (puisqu'elles ont deja ete faites)
             manteau.addManteau(fils.get(i));
             fils.remove(i);
          }
          fils.add(i, manteau);
       }
     
       int compteFils()
       {
          int ret = fils.size();
          for(Manteau manteau : fils)
          {
             ret += manteau.compteFils();
          }
          return ret;
       }
       @Override
       public String toString()
       {
          return "[" + min + "," + max + "]";
       }
    }
     
    Manteau base = new Manteau(0, 0);
    Manteau el;
    ArrayList<Manteau> listManteaux = new ArrayList<Manteau>();
    el = new Manteau(1, 3);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(2, 5);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(5, 8);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 6);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(2, 5);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 8);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 6);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 8);
    base.addManteau(el);
    listManteaux.add(el);
     
    for(Manteau manteau : listManteaux)
    {
       System.out.println("Manteau " + manteau.toString() + " fils=" + manteau.compteFils());
    }
    Note que ce code ne gere pas les doublons donc il faut adapter. Mais je ne vois pas trop comment faire plus efficace...

  10. #10
    Membre confirmé Avatar de Tr0n33
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2014
    Messages
    69
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Service public

    Informations forums :
    Inscription : Novembre 2014
    Messages : 69
    Par défaut
    Citation Envoyé par hwoarang Voir le message
    Moi, j'aurais bien tenté d'utiliser un arbre pour résoudre ce probleme grace à la propriété de transitivité évidente du probleme. Avec ca, on pourrait insérer directement chaque éléments au bon endroit.
    Ca doit pouvoir se faire. J'aime bien aussi cette idée

  11. #11
    Membre Expert
    Inscrit en
    Mai 2006
    Messages
    1 364
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 1 364
    Par défaut
    A la reflexion, il manque aussi une condition d'arret dans mon algo lors du premier parcours des manteaux (en fonction de max). Mais bon, c'est juste pour l'exemple. J'etais parti sur du pseudocode mais je trouve ca moins lisible ^^

  12. #12
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut
    Merci pour vos réponses.

    J'étudie ça dès que j'ai plus de temps.

  13. #13
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut
    Citation Envoyé par hwoarang Voir le message
    Moi, j'aurais bien tenté d'utiliser un arbre pour résoudre ce probleme grace à la propriété de transitivité évidente du probleme. Avec ca, on pourrait insérer directement chaque éléments au bon endroit.

    Ca donnerait un truc du genre:
    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    class Manteau
    {
      // Si on range directement les Elements dans cette liste triés selon min puis max croissants, ca permet de ne pas avoir à la parcourir.
      List<Manteau> fils = new ArrayList<Manteau>();
     
      int min;
      int max;
      Manteau(int min, int max)
      {
        this.min = min;
        this.max = max;
      }
     
       void addManteau(Manteau manteau)
       {
          int i = 0;
          while(i < fils.size() && manteau.min >= fils.get(i).min)
          {
             if(manteau.max <= fils.get(i).max)
             {
                fils.get(i).addManteau(manteau);
                return;
             }
             ++i;
          }
     
          // i pointe sur le premier manteau dont le min est plus grand ou bien sur fils.size()
          // Maintenant, on regarde si un ou plusieurs manteaux peuvent etre inclus dans le nouveau manteau
          while(i < fils.size() && manteau.max >= fils.get(i).max)
          {
             // Tous les manteaux ici devront etre supprimes de l'element pere (this) et inseres dans le nouvel element
             // Note qu'ici, on peut inserer directement la liste sans avoir a faire les verifications de addManteau (puisqu'elles ont deja ete faites)
             manteau.addManteau(fils.get(i));
             fils.remove(i);
          }
          fils.add(i, manteau);
       }
     
       int compteFils()
       {
          int ret = fils.size();
          for(Manteau manteau : fils)
          {
             ret += manteau.compteFils();
          }
          return ret;
       }
       @Override
       public String toString()
       {
          return "[" + min + "," + max + "]";
       }
    }
     
    Manteau base = new Manteau(0, 0);
    Manteau el;
    ArrayList<Manteau> listManteaux = new ArrayList<Manteau>();
    el = new Manteau(1, 3);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(2, 5);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(5, 8);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 6);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(2, 5);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 8);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 6);
    base.addManteau(el);
    listManteaux.add(el);
    el = new Manteau(3, 8);
    base.addManteau(el);
    listManteaux.add(el);
     
    for(Manteau manteau : listManteaux)
    {
       System.out.println("Manteau " + manteau.toString() + " fils=" + manteau.compteFils());
    }
    Note que ce code ne gere pas les doublons donc il faut adapter. Mais je ne vois pas trop comment faire plus efficace...
    Il y a un pb avec cet algo. Mais je suis sur que c'est la bonne base. Je verrais demain, où si vous avez des idées, merci

    Ma sortie:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Manteau [1,3]{  }0
    Manteau [2,5]{ [2,5]{  } }1
    Manteau [5,8]{  }0
    Manteau [3,6]{ [3,6]{  } }1
    Manteau [2,5]{  }0
    Manteau [3,8]{ [3,8]{ [5,8]{  } } }2
    Manteau [3,6]{  }0
    Manteau [3,8]{ [5,8]{  } }1

  14. #14
    Expert éminent
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 482
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 482
    Par défaut
    perso je ferais un algo qui droppe les manteaux au fur et à mesure comme ceci:

    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
    faire une liste de manteaux (ou tableau)
    faire une liste de manteaux potentiel identique
     
     
    pour chaque manteau potentiel M1:
      taille à 0
      faire une liste de travail
      pour chaque autre manteau  M2 dans la liste de travail:
        si M2 rentre dans M1: 
           retirer M2 des potentiels (un plus grand que lui existe il ne pourra jamais être un bon candidat)
           taille +1
        sinon si M1 rentre dans M2:   
           le nouveau candidat est M2
           retirer M1 des potentiels
           taille + 1
           reprendre au début de la liste de travail
        sinon
           passer au suivant de la liste de travail
      fin pour
      si taille > meilleur candidat
        meilleur candidat = celui qu'on a testé
        stocker la meilleur taille
      passer au potentiel suivant.

    L'avantage c'est que 2 conditions sur 3 expurgent définitivement des candidats dans ta liste de potentiel, donc même si c'est du O(n²), le worst case (tout le monde comparé à tout le monde) se produira quand aucun chevauchement n'existe et le o() moyen sera probablement bien plus acceptable.

    Au delà pour augmenter les perfs, faudra recourir à des algos de partitionnement d'espace mais c'est un travail assez long dev avec un prétraitement. On s'approche plus du Travail de fin d'étude que d'un examen

  15. #15
    Membre Expert
    Inscrit en
    Mai 2006
    Messages
    1 364
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 1 364
    Par défaut
    Citation Envoyé par Metogon Voir le message
    Il y a un pb avec cet algo. Mais je suis sur que c'est la bonne base. Je verrais demain, où si vous avez des idées
    Il y a au moins 2 problemes dont j'ai deja parlé:
    - Il n'y a pas de gestion des doublons. Si 2 manteaux identiques sont insérés, le 2e prendra la place du premier. Son compte de niveau sera bon mais pas celui du manteau remplacé.
    - La condition d'arret de la premiere boucle n'est pas suffisante. Comme on suppose la liste de fils classée, il faut ajouter une condition sur le max pour sortir si on trouve une borne min égale et une borne max superieure.

    Il n'y a rien de bien sorcier pour corriger ces problemes. Il faut juste choisir ce que tu veux faire pour la gestion des doublons (suppression du manteau doublon au profit d'un compteur / utilisation d'une sur-classe de stockage / bidouillerie dans la classe / ...)

  16. #16
    Membre à l'essai
    Homme Profil pro
    Collégien
    Inscrit en
    Juin 2015
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Juin 2015
    Messages : 6
    Par défaut
    J'ai un peu cherché ce WE et je me dis qu'il est peut-être possible de résoudre le problème avec un arbre ? Ou bien un arbre de Fenwick?

Discussions similaires

  1. Problème sur la recherche fulltext en v4 !
    Par poppa dans le forum Requêtes
    Réponses: 3
    Dernier message: 13/05/2004, 23h06
  2. Problème sur fiche MDIchild
    Par nivet dans le forum Composants VCL
    Réponses: 6
    Dernier message: 23/01/2004, 08h07
  3. Problème sur GetPrivateProfileString ???
    Par Bordelique dans le forum Langage
    Réponses: 7
    Dernier message: 25/06/2003, 22h15
  4. Problème sur une requête INSERT
    Par Marion dans le forum Langage SQL
    Réponses: 3
    Dernier message: 17/06/2003, 08h45
  5. problème sur une requête!!!!!
    Par Mcgrady_01 dans le forum Langage SQL
    Réponses: 2
    Dernier message: 13/06/2003, 01h17

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