Discussion :

[Micawber]

Bonjour tout le monde !

J'essaie de faire l'exercice suivant (gros résumé):
1) Créer une matrice binaire (juste avec des 1 et des 0) en :
a/ entrant une chaine de caractère contenant une suite de 0, de 1 et d'espaces
b/ utiliser "split" pour diviser cette chaîne en un certain nombre de lignes, en se servant des espaces comme séparateurs (je sais pas si j'explique parfaitement ce que fait split, mais j'ai réussi à m'en servir en tout cas).
2) Faire afficher par le programme les "tranches maximales"(drôle de nom) de la matrice, via ce procédé (extrait de l'énoncé) :
" Le programme fourni déclare une variable maxConsecutifList sous la forme d’un tableau dynamique de Integer. Il s’agit :
1/ de stocker dans maxConsecutifList les indices des lignes contenant la plus grande séquence de ’1’ consécutifs dans la matrice;
2/ et d’afficher le contenu de maxConsecutifList"


Moyennant tout un tas de vérification préalables : que la matrice ne contienne que des 1 ou des 0, qu'elle ne soie pas vide, etc. ça j'y suis arrivé sans trop de difficultés (je progresse, ouaiiiis ). C'est le point 2 qui me pose plus souci, première fois que je manipule les array list. J'ai essayé plusieurs choses qui pour l'instant ne marchent pas. Voici mon code actuel :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.ArrayList;
import java.util.Scanner;
 
class TrancheMax {
 
    private static Scanner clavier = new Scanner(System.in);
 
    public static void main(String[] args) {
 
        // Entree de la matrice
        System.out.println("Saisie de la matrice :");
        String matrice = clavier.nextLine();
        System.out.format("Matrice saisie :\n%s\n", matrice);
 
        // stocke les indices des lignes contenant la plus grande sequence de
        // '1' consecutifs dans la matrice
        ArrayList<Integer> maxConsecutifList = new ArrayList<Integer>();
 
        /*******************************************
         * Completez le programme a partir d'ici.
         *******************************************/
        // On vérifie que la matrice n'est pas vide
        if(matrice.length()==0){
        	System.out.println("Matrice vide!");
        	return;
        }
 
        // On vérifie que les lignes ne sont constituées que de 0, de 1, et d'espaces        
        for(int i=0; i<matrice.length(); ++i)
        {
        	if(matrice.charAt(i) != '0' && matrice.charAt(i) != '1' && matrice.charAt(i) != ' ')
        	{
        		System.out.println("Matrice invalide, seulement '1' , '0' et ' ' admis!");        		
        		return;
        	}
        }
 
        // On splitte la matrice
        String[] lignes = matrice.split(" {1,}");
 
        // On vérifie que les lignes sont de même longueur
        for(int i=1; i<lignes.length; ++i)
        {
        	if(lignes[i-1].length() != lignes[i].length())
        	{
        		System.out.println("Matrice invalide, lignes de longueurs differentes!");
        		return;
        	}
        }
 
        // On procède au comptage
        // En cours d'écriture
        int nbCourant=0;
        int nbMax =0;
 
        for(int i=0; i<matrice.length(); ++i){
        	if(matrice.charAt(i) == '1'){
        		nbCourant +=1;
        		if(nbMax <= nbCourant){
        		nbMax = nbCourant;
        		} 
        	} else {
        		nbCourant = 0;
        	}
        }
        System.out.println("Suite la plus longue de 1 (nbMax) :" + nbMax);
 
        // Comment faire le lien entre nbMax et maxConsecutifList ?
 
 
 
        /*******************************************
         * Ne rien modifier apres cette ligne.
         *******************************************/
 
        if (maxConsecutifList.isEmpty()) {
            System.out.println("Pas de lignes avec des 1!");
        } else {
            System.out.println("Ligne(s) avec le plus de 1 consecutifs:");
            for (Integer index : maxConsecutifList) {
                System.out.println(index);
            }
        }
    }
}

Comme vous le voyez j'ai une piste (que j'ai trouvé sur le forum de mon cours) que j'ai réussi à coder, mais ensuite je me demande un peu comment continuer. Il faut que j'arrange quoi ? Et si 'est pas trop demander, c'est quoi ce "index :" à la fin dans Integer index : maxConsecutifList ? Je suis en train de revoir mon cours mais j'ai pas encore trouvé.

Et pour info, la piste que j'ai trouvé sur le forum de mon cours dis ceci :

si tu testes 1100011001000111000
Tu vas parcourir les valeurs les unes après les autres.
tu initialises nbMax=0; nbCourant=0;
Tu incrémentes nbCourant tant que tu as des 1, donc arrivé au rang 2, où il y a un 0, tu auras donc nbCourant=2 (les 2 premiers "1").
nbCourant > nbMax, donc nbMax=nbCourant. (on sauvegarde la valeur maximale)
on remet nbCoiurant a 0, et on continue.
arrivé au rang 5, on recommence a incrémenter nbCourant jusqu'a la fin de la série de "1", soit jusqu'au rang 7
Là, on a nbMax=2, et nbCourant=2.
Donc on ne change pas nbMax, et on remet nbCourant à 0.
la série suivante de "1" nous donnera ,nbCourant=1, donc pareil, on ne change pas.
la dernière série de "1" nous donnera nbCourant=3.
On aura donc nbCourant>nbMax, donc on stocke nbCourant dans nbMax, et on continue.
Arrivé a la fin, tu auras donc sauvegardé le noimbre maximum de "1" consecutifs dans nbMax.

[joel.drigo]

Salut,

Le problème, avant d'être un problème d'algorithme, puis d'encoding Java, c'est avant tout le sens de la question. D'abord ce qu'on entend par "tableau dynamique" ? Une ArrayList ?

Sinon, j'ai beau la lire et la relire, je ne comprends pas le sens de la question dans le contexte d'une seule matrice. Il n'y a pour moi qu'une seule plus longue liste de 1 consécutifs. Dont on peut déterminer l'indice comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int nbMax=0;
int indexOfLineWithMax = -1;
for(int i=0; i<matrice.length(); ++i){
    if(matrice.charAt(i) == '1'){
        nbCourant ++;
        if ( nbCourant > nbMax ) {
            nbMax = nbCourant;
            indexOfLineWithMax = i; // sauvegarde de l'indice
        } 
    } else {
       nbCourant = 0;
    }
}
if ( indexOfLineWithMax==-1 ) {
   System.out.println("Pas de 1 dans cette matrice");
}
else {
   System.out.printf("La ligne %d est la ligne qui contient la série la plus longue de 1 (longueur=%d)%n", indexOfLineWithMax, nbMax);
}

Maintenant, on peut effectivement avoir plusieurs lignes qui ont cette plus grande série de 1. L'objet de l'exercice est peut être de stocker, dans maxConsecutifList, leur indice. A chaque fois qu'on détermine un nouveau nbMax, on ajoute son indice dans maxConsecutifList.

Le problème de l'algorithme utilisé est qu'on identifie le max alors qu'on a pas forcément encore atteint ce max : si on a 01100000 01110110 ...., on a d'abord 2 comme max, donc on va stocker l'indice 0 dans maxConsecutifList, alors que le max est au moins 3. Donc la ligne 0 ne devrait pas être dans maxConsecutifList (cas 1). En plus, on va stocker tous les indices intermédiaire : si on a 011000 011110..., le max sera d'abord 1, puis 2, on va stocker deux fois l'indice 0, puis 3, puis 4, donc on va stocker l'indice 1 deux fois également (cas 2).

On devrait déterminer le max d'abord, puis reparcourir la liste avec le même algorithme, et pour chaque ligne dont on trouve une série aussi longue que max, on stocke la ligne.

Si le but de l'exercice est de faire qu'une seule fois la boucle, il suffit d'ajouter l'indice de la ligne courante dans la ArrayList (add()) à chaque fois qu'on trouve un nouveau nbMax. Il faut juste ajouter un test if ( nbCourant==nbMax ) pour ajouter l'indice des lignes dont la série est de la même longueur que le max.
Pour traiter le cas 1, on peut utiliser clear() pour effacer la liste d'indices précédemment trouvés : en effet, quand on trouve un max, le max précédent est caduque, donc les lignes précemment trouvées ne sont pas celles qui contiennent la plus longue série de 1.
Pour le cas 2, on peut éviter d'ajouter un indice déjà présent, en testant s'il est déjà présent (avec la méthode contains()). On pourrait croire que le clear() est suffisant pour éviter la duplication des indices, mais il faut considérer qu'on peut avoir un nbMax avec 4 et une ligne du type 01111011110.

[Micawber]

Le but c'est, par exemple pour la matrice :

111
001
110

Que l'on a obtenu en faisant String[] lignes = matrice.split(" {1,}"); de la matrice String matrice = "111 001 110",

De déterminer quelle ligne (ou quelles lignes si il y a égalité) a la plus de 1 consécutifs, ici en l'occurrence la ligne 1. On initialise deux variables nbCourant et nbMax et à l'aide d'une boucle, quand il y a un '1', on incrémente nbCourant, et nbMax = nbCourant. Qand il y a un '0', nbCourant est réinitialisé à 0, nbMax garde en mémoire la suite la plus grande de1 précédente, etc. En même temps, on stocke les indices de ces lignes au fur et à mesure dans l'array List maxConsecutifList

Mais j'ai beau lire et relire toutes les infos qu'on me donne sur différents forums, soit j'arrive pas à comprendre ce qu'on me dit, soit j'ai essayé et ça marche pas car j'écris pas correctement....

-J'arrive à avoir le bon nombre de 1 consécutifs quand je parcours la matrice (non splittée) avec une boucle for (comme vous avez fait dans votre réponse si je me m'abuse), mais après je sais pas quoi faire, car ça me donne pas de numéro de ligne.

-Quand j'essaie de parcourir la matrice splittée ça marche pas (car on m'a conseillé d'utiliser la matrice splittée, ce qui paraît logique sinon pourquoi la créer si on l'utilise pas?), la syntaxe doit m'échapper probablement...j'essaye deux boucles for imbriquées comme pour parcourir les tableaux à deux dimensions mais ça a pas l'air d'être adapté, et le programme m'indique à chaque fois que la plus grande suite de 1 est 0.

Ca représente la toute fin de l'exercice alors mais ça compte pour la moitié des points, et je deviens fou là :s. Je demande pas qu'on m'écrive mon code, mais un sérieux coup de pouce pour quoi écrire

[joel.drigo]

Ah oui, pardon, j'avais pas bien lu ton programme, et je n'avais pas fait attention que tu parcourais ta chaine d'entrée (ça me semblait tellement évident de parcourir les lignes). Il faut bien entendu parcourir chaque ligne de la matrice, donc le résultat du split. Voici le code de mon précédent post corrigé. Le reste du message reste valable.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
int nbMax=0;
int indexOfLineWithMax = -1;
for(int indexligne =0; indexligne< indexlignes.length; indexligne++) {
   String ligne = lignes[indexligne];
   for(int i=0; i<ligne.length(); ++i){
       if(ligne.charAt(i) == '1'){
           nbCourant ++;
           if ( nbCourant > nbMax ) {
               nbMax = nbCourant;
               indexOfLineWithMax = indexligne; // sauvegarde de l'indice
          } else {
             nbCourant = 0;
          }
       }
    }
}
if ( indexOfLineWithMax==-1 ) {
   System.out.println("Pas de 1 dans cette matrice");
}
else {
   System.out.printf("La ligne %d est la ligne qui contient la série la plus longue de 1 (longueur=%d)%n", indexOfLineWithMax, nbMax);
}

[Micawber]

Ok merci beaucoup, je vais le lire, tâcher de le comprendre et le ré-écrire moi même !

[Micawber]

Alors j'ai essayé de synthétiser toutes les infos que j'ai trouvé et j'en suis arrivé au code ci dessous, mais ça ne me donne pas les bonnes valeurs de nbCourant et nMax ! Par exemple, pour la matrice

1111
0001
1101

j'ai nbCourant = 5 et nbMax = 5, alors que théoriquement ça devrait être 4.Quand j'essaie sans le -1 après les .length c'est pire et ça donne nbCourant et nbmax égaux à 9 (d'ailleurs je suis pas sûr, il faut le mettre ou pas ce -1 ?). Je lis et relis ma boucle je vois pas ce qui se passe :/ (vu le temps que ça me prend j'ai eu raison de faire biologie et pas informatique on dirait )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int nbCourant = 0;
        int nbMax = 0;
 
        for (int i = 0; i < lignes.length-1; ++i) {
            for (int j = 0; j < lignes[i].length()-1; j++) {
            	if((lignes[i].charAt(j) == '1')){
            		nbCourant += 1;
            		if(nbMax < nbCourant){
            			nbMax=nbCourant;
            			// Envoi de l'indice de la ligne à l'ArrayList
            			if(!maxConsecutifList.contains(i)){
            				maxConsecutifList.add(i);
            			}
 
            		} else {
            			nbCourant = 0;
            		}
            	}  
            }
          }
        System.out.println("nbCourant : " + nbCourant + " -- nbMax : " + nbMax);