1

Bonjour je souhaiterai extraire une sous suite croissante d'un tableau de permutations d'entiers de 1 à n. Les entiers étant deux à deux distincts. Je vous poste par la suite ce que j'ai fait. Le tableau lis correspond à un tableau d'entier qui donnent la taille de la sous suite croissante maximale correspondant à l'indice le plus à droite. Merci d'avance.

2

Poste ce que tu as fait déjà, et ce qui te pose problème.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

3

C'est en effet très simple, il suffit d’exécuter la méthode faisMesDevoirsAMaPlace() dans le package bonne.poire
avatar

4

faisMesDevoirsAMaPlace(): Method not foundComme c'est dommage tsss
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

5

(faut reconnaître que l'exercice a l'air passionnant #trizzz#)

6

Zerosquare (./4) :
faisMesDevoirsAMaPlace(): Method not foundComme c'est dommage tsss

zWrM
(elle poutramort trop cette image love)

7

(oué elle en jette ! tripo)

8

Voici mon code pour vous montrer mon travail. Je teste sur le compilateur de ma classe pour vous dire quelles sont mes erreurs.





// 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 class Projet{
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;
}
}
}

9

// 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 class Projet{
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;
}
}
}

10

Quelle est ta question précisément ? Télécharge un "compilateur" (visiblement tu as internet, et c'est gratuit, donc pas d'excuses), regarde si ton code fonctionne, et s'il ne fonctionne pas alors il y aura probablement des points particuliers sur lesquels tu auras besoin d'aide.

Mais demander à ce que quelqu'un lise ton code et le corrige à ta place alors que tu n'as pas effectué la moindre vérification toi-même, c'est un peu gonflé.
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

11

Je ne suis pas gonflé, je pensais qu'un pro du java pourrait repérer directement mes erreurs, et que cela ne lui prendrait que 5 minutes. Je ne demande pas à ce qu'on me donne un cours particulier, mais juste un coup de main. J'ai déjà essayé de chercher un compilateur mais je n'arrive pas à faire compiler mon programme. Je fais des études de mathématiques et l'informatique n'est pas du tout ma spécialité. J'ai déjà corrigé des problèmes d'autres personnes sur des forums de mathématiques, et cela avec un plaisir d'aider l'autre. Je pensais que c'était le cas de tous les forums...

12

Et pour répondre à ta question zeph, la mienne est de savoir si dans mon code il y a des incohérences, des erreurs flagrantes, car je ne m'en rends pas forcément compte en le faisant. Je te remercie quand même de l'attention que tu portes à mon problème, c'est gentil. hehe

13

C'est le boulot d'un compilateur de détecter les fautes grossières, et s'il fait ça, c'est justement parceque c'est une tâche qui n'est pas forcément facile pour un humain. Sans savoir précisément où sont les erreurs, quelqu'un de ce forum - même expérimenté - a de grandes chances de ne pas voir les fautes dans ton code (ou du moins pas toutes). La solution la plus fiable est donc de faire une première passe avec un compilateur.

Tu dis l'avoir déjà fait, et ça ne fonctionne pas : quelles sont les erreurs que tu as obtenues en essayant ?
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

14

Ah d'accord! Merci Zeph!
Alors le compilateur me dit
2 errors : missing return statement
avec les "}"

Mais j'ai regardé partout et je n'ai pas trouvé où il en manquait. J'ai fermé toutes mes boucles et mes classes.

15

Je ne connais pas trop Java, mais ton dernier "return maximum" est à l'intérieur d'une boucle for. Je ne sais pas si c'est ce que tu voulais faire, mais d'une part ça veut dire que cette boucle ne fera jamais plus d'une seule itération, d'autre part si ta liste ne contient aucun élément alors ta fonction ne retourne aucun résultat, ce qui n'est pas possible puisque son type de retour est "int[]". D'ailleurs je ne sais pas ce qu'elle est supposée faire, mais une fonction "longueur" qui prend un tableau d'éléments et retourne un tableau d'éléments, ça me semble étrange...
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

16

maximum ; } } }
Pour y voir un peu clair :public class Projet
{

   // 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

17

Dans ta fonction "inferieur", je soupçonne que le return false soit mal placé.
Ce que je comprends de ton idée, c'est que tu parcours les éléments du tableau à la recherche "T[j]" inférieur à "a", que si tu en trouves un, tu veux retourner "true" et "false" sinon.
Ton "return false" devrait être après la bouche "for", pas à l'intérieur
En français, ce qu'il faut faire, c'est : dès qu'on trouve un élément qui convient, on est content (=>retourne "true")
Si après avoir parcouru tout le tableau on n'a pas trouvé un élément qui convient, on n'est pas content (=>retourne "false")


Dans ta fonction "longueur", il manque une espace entre new et int sur la ligne "int[] LIS= newint[T.length] ; "
Et sinon il y a un problème comme dans la première fonction avec ton return maximum (comme l'a souligné Zeph d'ailleurs). Cette fonction étant plus obscure que la première... C'est toi le mieux placé pour corriger le problème.
Bon, à titre d'exemple je te donne une correction possible de ta première fonction :
   public static boolean inferieur( int[] T, int i, int a )
   {
      for ( int j= 0 ; j < i ; j++ ) {
         if ( T[j] < a ) {
            return true ;
         }
      }
      return false ;
   }

18

PS : tu as aussi un problème dans ta boucle for "for ( int i= 0 ; i < T.length ; i++ ) {" dans ta fonction "longueur". Tu utilises une variable "i" alors qu'elle est déjà déclarée. Tu dois utiliser un autre nom pour ta variable.

19

Ah d'accord! Super, je vais corriger tout cela et vous dire si ça marche. Sinon pen^2 tu as bien compris le but de ma fonction inferieur. Je vais tenter ta correction. Et zeph, oui mon return je pense qu'il doit bien être en dehors de la boucle. Super! Merci encore!