modif affichage + complexiter minpremier
authorjerome <jerome@fac>
Tue, 3 Dec 2013 17:52:33 +0000 (18:52 +0100)
committerjerome <jerome@fac>
Tue, 3 Dec 2013 17:52:33 +0000 (18:52 +0100)
src/ChercherMin.java
src/Permutation.java
src/Prog.java

index c677fbf..336329b 100644 (file)
@@ -46,7 +46,6 @@ public class ChercherMin {
                        }
                        //System.out.println(C);
                }
-               System.out.println(comp);
                return mins;
        }
        
@@ -94,7 +93,6 @@ public class ChercherMin {
                        }
                        //System.out.println(C);
                }
-               System.out.println(comp);
                
                return mins;
        }
index 69a3ca6..590e095 100644 (file)
@@ -58,42 +58,58 @@ public class Permutation
                this.elts = elts;
        }
 
-       public void chercherMinPremier()
+       public int chercherMinPremier()
        {
+               int comp = 0; // initialisation compteur pour les complexités
                int j, t;
                int idMin,idMax;
                int idVMin,idVMax;
+               comp += 2; // affectation + test t < n (for)
                for (t = 1; t < n ;t++)
                {
+                       comp+=3; // opération + affectation + test t < n (for)
                        idVMin = -1;
                        idVMax = -1;
                        j = 0;
+                       comp+=3; // 3 affectations
       //recherche de l'intervalle
                        while (idVMin == -1 || idVMax == -1)
                        {
+                               comp+=3; // 3 tests (while)
                                if (elts[j] == t+1)
                                {
                                        idVMax=j;
+                                       comp++; // affecation
                                }
                                if (elts[j] == t)
                                {
                                        idVMin=j;
+                                       comp++; // affecation
                                }
-
+                               comp+=3; // +2 pour le 1er if (affectation + opération), +1 pour le 2e
                                j++;
-                       }
-
+                               comp+=2; // 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
-
-      //recherche du min dans l'interval
+                       comp+=4; // 2 tests + 2 affectations (2 if précédents)
+      //recherche du min dans l'intervalle
                        mins[t-1] = elts[idMin];
-      for (int i = idMin+1; i <= idMax ; i++) {
+                       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];
-      }
-
-               }
+        {
+               mins[t-1]=elts[i];
+               comp+=4; // 2 accès + opération + affectation
+        }
+      } // end for
+               } // end for
+               return comp;
        }
 
        public String eltsToString()
index 5e57a35..42e4027 100644 (file)
@@ -82,31 +82,32 @@ public class Prog
 \r
                for (int i = 0; i < p.size(); ++i)\r
                {\r
-                       System.out.println(p.get(i).eltsToString());\r
+                       System.out.println("Permutation " + (i + 1) + " : " + p.get(i).eltsToString());\r
                        p.get(i).chercherMinPremier();\r
-                       System.out.println(p.get(i).minsToString());\r
+                       System.out.println("Solutions :");\r
+                       int comp = p.get(i).chercherMinPremier();\r
+                       System.out.println("MinPremiers : " + p.get(i).minsToString() + " Complexité : " + comp);\r
                        ArrayList<Paire> paires = new ArrayList<Paire>();\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
-                       int[] minsCompress;\r
-                       minsCompress = ChercherMin.CURang(p.get(i),paires);\r
-                       System.out.print("(");\r
-                       for (int j : minsCompress) {\r
+                       int[] mins;\r
+                       mins = ChercherMin.CURang(p.get(i),paires);\r
+                       System.out.print("CURang : (");\r
+                       for (int j : mins) {\r
                                System.out.print(" "+j+" ");\r
                        }\r
-                       System.out.println(")");\r
+                       System.out.println(") Complexité : " + ChercherMin.comp);\r
                        \r
-                       System.out.println("**************************");\r
-                       \r
-                       minsCompress = ChercherMin.CURangCompress(p.get(i),paires);\r
-                       System.out.print("(");\r
-                       for (int j : minsCompress) {\r
+                       mins= ChercherMin.CURangCompress(p.get(i),paires);\r
+                       System.out.print("CURangCompress : (");\r
+                       for (int j : mins) {\r
                                System.out.print(" "+j+" ");\r
                        }\r
-                       System.out.println(")");\r
+                       System.out.println(") Complexité : " + ChercherMin.comp);\r
+                       System.out.println("**************************************************************");\r
                }\r
                \r
                /*\r