Implemantation ChercherMinPremier sans lecture de fichier
authorDralagen <dralagen@dralagen.fr>
Mon, 21 Oct 2013 07:45:56 +0000 (09:45 +0200)
committerDralagen <dralagen@dralagen.fr>
Mon, 21 Oct 2013 07:45:56 +0000 (09:45 +0200)
CollPaires.java [new file with mode: 0644]
Paire.java [new file with mode: 0644]
Permutation.java [new file with mode: 0644]
Prog.java [new file with mode: 0644]

diff --git a/CollPaires.java b/CollPaires.java
new file mode 100644 (file)
index 0000000..94f8c12
--- /dev/null
@@ -0,0 +1,39 @@
+import java.util.Vector;
+
+public class CollPaires
+{
+       private Vector<Paire> c;
+       private Vector<Integer> ids;
+       
+       public CollPaires()
+       {
+               c = new Vector<Paire>();
+               ids = new Vector<Integer>();
+       }
+       
+       public CollPaires(Vector<Paire> c, Vector<Integer> ids)
+       {
+               this.c = c;
+               this.ids = ids;
+       }
+
+       public Vector<Paire> getC()
+       {
+               return c;
+       }
+
+       public void setC(Vector<Paire> c)
+       {
+               this.c = c;
+       }
+
+       public Vector<Integer> getIds()
+       {
+               return ids;
+       }
+
+       public void setIds(Vector<Integer> ids)
+       {
+               this.ids = ids;
+       }
+}
diff --git a/Paire.java b/Paire.java
new file mode 100644 (file)
index 0000000..5ca62c5
--- /dev/null
@@ -0,0 +1,44 @@
+
+public class Paire
+{
+       private int a;
+       private int b;
+       
+       public Paire()
+       {
+               a = 0;
+               b = 0;
+       }
+       
+       public Paire(int a, int b)
+       {
+               this.a = a;
+               this.b = b;
+       }
+       
+       public Paire(int a)
+       {
+                       this.a = a;
+                       b = a + 1;
+       }
+       
+       public int getA()
+       {
+               return a;
+       }
+       
+       public int getB()
+       {
+               return b;
+       }
+       
+       public void setA(int a)
+       {
+               this.a = a;
+       }
+       
+       public void setB(int b)
+       {
+               this.b = b;
+       }
+}
diff --git a/Permutation.java b/Permutation.java
new file mode 100644 (file)
index 0000000..b66d892
--- /dev/null
@@ -0,0 +1,121 @@
+import java.util.*;
+
+
+public class Permutation
+{
+       private int n;
+       private int elts[];
+       private int mins[];
+
+
+       public Permutation()
+       {
+               n = 0;
+               elts = new int[0];
+               mins = new int[0];
+       }
+
+       public Permutation(int n, int elts[])
+       {
+               this.n = n;
+               this.elts = elts;
+               mins = new int[n - 1];
+       }
+
+       public int getN()
+       {
+               return n;
+       }
+
+       public int[] getElts()
+       {
+               return elts;
+       }
+
+       public void setN(int n)
+       {
+               this.n = n;
+               elts = new int[n];
+               mins = new int[n-1];
+       }
+
+       public void setElts(int elts[])
+       {
+               this.elts = elts;
+       }
+
+       public void chercherMin()
+       {
+               int j, t, min;
+               int idMin,idMax;
+               int idVMin,idVMax;
+               for (t = 1; t < n ;t++)
+               {
+                       idVMin = -1;
+                       idVMax = -1;
+                       j = 0;
+      //recherche de l'interval
+                       while (idVMin == -1 || idVMax == -1)
+                       {
+                               if (elts[j] == t+1)
+                               {
+                                       idVMax=j;
+                               }
+                               if (elts[j] == t)
+                               {
+                                       idVMin=j;
+                               }
+
+                               j++;
+                       }
+
+                       idMin = (idVMin<idVMax)?idVMin:idVMax; // position min
+      idMax = (idVMin>idVMax)?idVMin:idVMax; // position max
+
+      //recherche du min dans l'interval
+                       mins[t-1] = elts[idMin];
+      for (int i = idMin+1; i <= idMax ; i++) {
+        if (elts[i] < mins[t-1])
+          mins[t-1]=elts[i];
+      }
+
+               }
+       }
+
+       public String eltsToString()
+       {
+               String s = "{ ";
+               for (int i = 0; i < n - 1 ;i++)
+               {
+                       s += Integer.toString(elts[i]);
+                       s += ", ";
+               }
+               s += Integer.toString(elts[n - 1]);
+               s += " } ";
+               return s;
+       }
+
+       public String minsToString()
+       {
+               String s = "(";
+    for(int i : mins) {
+      s+=" "+i+" ";
+    }
+    s+=")";
+    return s;
+       }
+
+       public void genRandom()
+       {
+               int r, tmp;
+               for (int i = 0; i < n ;i++)
+                       elts[i] = i + 1;
+               for (int i = 0; i < n ;i++)
+               {
+                       r = (int)((Math.random() * n * 10) % n);
+                       tmp = elts[r];
+                       elts[r] = elts[i];
+                       elts[i] = tmp;
+               }
+       }
+}
diff --git a/Prog.java b/Prog.java
new file mode 100644 (file)
index 0000000..946714e
--- /dev/null
+++ b/Prog.java
@@ -0,0 +1,13 @@
+
+public class Prog
+{
+       public static void main(String[] args)
+       {
+               Permutation p = new Permutation();
+               p.setN(50);
+               p.genRandom();
+               System.out.println(p.eltsToString());
+               p.chercherMin();
+               System.out.println(p.minsToString());
+       }
+}