correction complexité
authorDralagen <dralagen@dralagen.fr>
Wed, 4 Dec 2013 10:02:37 +0000 (11:02 +0100)
committerDralagen <dralagen@dralagen.fr>
Wed, 4 Dec 2013 10:02:37 +0000 (11:02 +0100)
src/ClasseUnion.java
src/ClasseUnionCompress.java
src/Permutation.java
src/Prog.java

index 4819cbb..aba1704 100644 (file)
@@ -22,13 +22,13 @@ public class ClasseUnion {
        }
        
        public int classe(int i) {
-               while (p_[i] != -1 ) {
-                       ChercherMin.comp++; //test
-                       i = p_[i];
-                       ChercherMin.comp++; //affectation
+               ChercherMin.comp++; // test
+               if (p_[i] == -1) {
+                       return i;
+               }
+               else {
+                       return classe(p_[i]);
                }
-               ChercherMin.comp++; //test
-               return i;
        }
        
        public void union(int a, int b) {
index e5fc527..02ffaf9 100644 (file)
@@ -18,7 +18,6 @@ public class ClasseUnionCompress {
                        ens_[i] = new Coll(i);
                        ChercherMin.comp++;
                }
-               
        }
        
        public int classe(int i) {
@@ -37,7 +36,7 @@ public class ClasseUnionCompress {
        public void union(int a, int b) {
                ChercherMin.comp++; // test
                if (classe(a) != classe(b)) {
-                       p_[b] = a;
+                       p_[b] = classe(a);
 
                        ens_[a].add(ens_[b]);
                        ens_[b].resetEns();
index 590e095..38dfe78 100644 (file)
@@ -67,7 +67,7 @@ public class Permutation
                comp += 2; // affectation + test t < n (for)
                for (t = 1; t < n ;t++)
                {
-                       comp+=3; // opération + affectation + test t < n (for)
+                       comp+=2; // opération + affectation + test t < n (for)
                        idVMin = -1;
                        idVMax = -1;
                        j = 0;
@@ -88,26 +88,30 @@ public class Permutation
                                }
                                comp+=3; // +2 pour le 1er if (affectation + opération), +1 pour le 2e
                                j++;
-                               comp+=2; // opération plus affectation
+                               comp++; // opération plus affectation
                        } // end while
                        comp+=3; // 3 tests (while)
+                       
                        idMin = (idVMin<idVMax)?idVMin:idVMax; // position min
-      idMax = (idVMin>idVMax)?idVMin:idVMax; // position max
+                       idMax = (idVMin>idVMax)?idVMin:idVMax; // position max
                        comp+=4; // 2 tests + 2 affectations (2 if précédents)
-      //recherche du min dans l'intervalle
+                       
+                       //recherche du min dans l'intervalle
                        mins[t-1] = elts[idMin];
                        comp+=2; // opération + affectation
+                       
                        comp+=3; // opération + affectation + test (for)
-      for (int i = idMin+1; i <= idMax ; i++)
-      {
-       comp+=3; // incrémentation + test (for)
-        comp+=4; // 2 accès + opération + test (if)
-        if (elts[i] < mins[t-1])
-        {
-               mins[t-1]=elts[i];
-               comp+=4; // 2 accès + opération + affectation
-        }
-      } // end for
+             for (int i = idMin+1; i <= idMax ; i++)
+             {
+               comp+=2; // incrémentation + test (for)
+               
+               comp+=2; // opération + test (if)
+               if (elts[i] < mins[t-1])
+               {
+                       mins[t-1]=elts[i];
+                       comp+=2; // opération + affectation
+               }
+             } // end for
                } // end for
                return comp;
        }
index 42e4027..df30a0b 100644 (file)
@@ -77,7 +77,11 @@ public class Prog
 \r
        public static void main(String[] args)\r
        {\r
-               \r
+\r
+       /******************************\r
+        * Lecture du tous le fichier *\r
+        ******************************/\r
+\r
                ArrayList<Permutation> p = loadAll();\r
 \r
                for (int i = 0; i < p.size(); ++i)\r
@@ -86,21 +90,21 @@ public class Prog
                        p.get(i).chercherMinPremier();\r
                        System.out.println("Solutions :");\r
                        int comp = p.get(i).chercherMinPremier();\r
-                       System.out.println("MinPremiers : " + p.get(i).minsToString() + " Complexité : " + comp);\r
+                       System.out.println("MinPremiers    : " + p.get(i).minsToString() + " Complexité : " + comp);\r
                        ArrayList<Paire> paires = new ArrayList<Paire>();\r
-                       \r
+\r
                        for (int j = 1; j < p.get(i).getN(); j++) {\r
                                paires.add(new Paire(p.get(i).indexOf(j),p.get(i).indexOf(j+1)));\r
                        }\r
-                       \r
+\r
                        int[] mins;\r
                        mins = ChercherMin.CURang(p.get(i),paires);\r
-                       System.out.print("CURang : (");\r
+                       System.out.print("CURang         : (");\r
                        for (int j : mins) {\r
                                System.out.print(" "+j+" ");\r
                        }\r
                        System.out.println(") Complexité : " + ChercherMin.comp);\r
-                       \r
+\r
                        mins= ChercherMin.CURangCompress(p.get(i),paires);\r
                        System.out.print("CURangCompress : (");\r
                        for (int j : mins) {\r
@@ -109,19 +113,36 @@ public class Prog
                        System.out.println(") Complexité : " + ChercherMin.comp);\r
                        System.out.println("**************************************************************");\r
                }\r
-               \r
-               /*\r
-               Permutation p = load(1);\r
-               ArrayList<Paire> paires = new ArrayList<Paire>();\r
-               paires.add(new Paire(1,2));\r
-               paires.add(new Paire(3,7));\r
-               paires.add(new Paire(1,4));\r
-               System.out.println(p.eltsToString());\r
-               ChercherMin.CURang(p,paires);\r
-               System.out.println("**************************");\r
-               ChercherMin.CURangCompress(p,paires);\r
-               */\r
-               \r
+\r
+\r
+       /**************************************\r
+        * Généation aléatoire de Permutation *\r
+        **************************************/\r
+\r
+/*\r
+               for (int i = 3; i < 80 ; ++i) {\r
+                       Permutation pbis = new Permutation();\r
+                       pbis.setN(i);\r
+                       pbis.genRandom();\r
+                       System.out.println("Permutation    : " + pbis.eltsToString());\r
+                       pbis.chercherMinPremier();\r
+                       int comp = pbis.chercherMinPremier();\r
+                       System.out.println("Solutions      : " + pbis.minsToString());\r
+                       System.out.println("MinPremiers    : " + comp);\r
+                       ArrayList<Paire> paires = new ArrayList<Paire>();\r
+\r
+                       for (int j = 1; j < pbis.getN(); j++) {\r
+                               paires.add(new Paire(pbis.indexOf(j),pbis.indexOf(j+1)));\r
+                       }\r
+\r
+                       int[] mins;\r
+                       mins = ChercherMin.CURang(pbis,paires);\r
+                       System.out.println("CURang         : " + ChercherMin.comp);\r
+\r
+                       mins= ChercherMin.CURangCompress(pbis,paires);\r
+                       System.out.println("CURangCompress : " + ChercherMin.comp);\r
+               }\r
+*/\r
        }\r
 }\r
 \r