Besoin d'aide projet JAVA bis
Bonjour je souhaiterai extraire une sous suite croissante d'un tableau de permutations des entiers de 1 à n. Le tableau LIS est le tableau qui donne les tailles des sous suites d'indice i, le plus à droite.
Alors maintenant voila ce que j'ai fait, donc en fait je n'ai pas de compilateur chez moi je ne sais pas si j'ai fait des erreurs. Je suis débutant en JAVA donc auriez-vous la bonté de me dire au moins si je suis sur la bonne voie. Je vous remercie énormément. Voilà donc mon code :
Code:
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
| // Analyse
// Question 1) a)
// Les conditions sur T sont T[i]<=T[j] et donc à fortiori on en déduit cette relation :
// LIS[i+1] = max(LIS[j])+1 avec j compris entre 1 et i.
//b)
//On va créer un algorithme qui va dire s'il existe une valeur inférieure à une valeur donnée en argument.
public static boolean inferieur(int [] T, int i, int a){ // avec T la permutation, i la longeur, et a l'entier voulu
for(int j=0; j<i; j++){
if(T[j]<a){
return true;
}
else return false;
}
}
public static int[] remplir(int[] LIS, int[] T, int k){
// On va regarder si il existe une valeur inférieure à T[k] dans T :
boolean x = inferieur(T,k,T[k]);
// Il nous faut un nouveau tableau pour le LIS :
int[] NEWLIS = new int [k+1];
// Distinguons deux cas, soit il existe des valeurs inférieures à i, c'est à dire l'indice le plus à droite, donc on va chercher ces valeurs, soit il n'y en a pas, donc la plus longue sous-suite est de taille 1 :
// Premier cas :
int maximum = 0;
if(x){
for(int i=0; i<k; i++){
if((LIS[maximum]<LIS[i])&&(T[k]>T[i])){
maximum=i;
}
NEWLIS[i]=LIS[i];
}
}
// Second cas :
else{
for(int i=0; i<k; i++){
NEWLIS[k]=1;
}
}
return NEWLIS;
}
// c)
public static int[] longueur(int[] T){
int[] LIS = newint[T.length];
LIS[0]=0;
for(int i=1;i<T.length;i++){
int[] NEWLIS2 = remplir(LIS,T,i);
LIS[i] = NEWLIS2[i];
// On recherche la taille de la plus grande sous-suite
int maximum = 0;
for(int i=0; i<T.length; i++){
if(LIS[i]>maximum){
maximum = LIS[i];
}
}
return maximum;
}
} |
Encore merci!