Discussion :

[larchicha]

Bonsoir à tous et à toutes,

Je viens vers vous pour une question assez bebete il me semble mais, ça fait quelques heures que je bûche dessus et j'ai mal à la tête...

Ma vie est sûrement le dernier de vos soucis donc je me lance :

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
void Inserer(B : batière, x : entier) :
	i, j : entiers ;
	b : boolean ;
	b = faux ;
	tant que (b == faux) faire : 
		pour i de 1 à B.n faire :
			pour j de 1 à B.m faire : 
				si (B[i][j] == + l'infini) : 
					B[i][j] = x ; // insère l element x dans la case vide
					b = vrai ;	
				fin si.	
			fin pour
		fin pour
        fin tant que
 
	pour i de 1 à B.n faire :
			pour j de 1 à B.m faire : 			
				Retablir(B,i,j); // retablit le bordel causé par l insertion
                        fin pour
        fin pour
 
fin algo

Que vous ne me traitiez pas de martien, il s'agit d'une batiere (tableau de n lignes * m colonnes triées par ordre croissant dans laquelle les cases vides sont identifiées par + l infini).
B.n et B.m correspondent aux dimensions de la batière.

Le code de la fonction Retablir est ici inutile car ma question est : quelle est la complexité de l'algorithme Insérer ?

Je ne saurais vous donner ma réponse car je bloque sur le while(!b)...sinon pour les 2 doubles boucles "pour" je vois du O(2*n*m) ~~ O(n*m).

Une deuxième chose tant que je vous tiens... concernant l'algorithme en lui même : il y a surement beaucoup plus simple mais je vous donne ma vision des choses :

Il y a un élément à insérer dans la batière (supposée non pleine) et seules les cases "+l'infini" sont vides... seulement il peut y avoir plus d'une case vide, d'où l'emploi du boolean... et à fortiori de la boucle while.

Par contre pour la 2ème double boucle "pour", j'ai pensé que étant donné la triple boucle (while / pour / pour) faites avant , la complexité de ma 2eme double boucle serait "avalé" dans la 1ere [O(2*n*m) ~~ O(n*m)].

Le post est long à lire, je m'en excuse à l'avance et remercie ceux qui voudront bien m'aider.

Cordialement.

[Franck Dernoncourt]

J'ai lu rapidement, je me trompe ou la boucle "tant que" (tant que (b == faux) faire) n'a qu'une seule itération ?

EDIT: une seule ou bien une infinité.

[larchicha]

Bah elle a.autant d iteration qu il faut pour trouver une case qui soit vide... donc pas qu une seule...
ps : pas de ponctuation sur le telephone. desole.

[Franck Dernoncourt]

Mais avec

Code :

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

1
2
pour i de 1 à B.n faire :
   pour j de 1 à B.m faire :

tu parcours déjà toute la matrice B non ?

[larchicha]

En effet mais.que.se.passerait il si il y avait plus d une case.vide dans.mon tableau ? L algorithme est supposé inserer l element x une seule fois... mais pour repondre a ta question oui les 2 boucles pour parcourt l integralite du tableau

[Franck Dernoncourt]

En effet mais.que.se.passerait il si il y avait plus d une case.vide dans.mon tableau ?

Par vide tu veux dire "== + l'infini" ?

L algorithme est supposé inserer l element x une seule fois... mais pour repondre a ta question oui les 2 boucles pour parcourt l integralite du tableau

A quoi sert la boucle tant que alors ?

[larchicha]

Oui pour vide j'entends +l infini...

Je pense que si je n'utilise pas la boucle "tant que" , toutes les cases vides (donc tous les +l infini) seront remplacées par x... alors que non...(enfin toi tu penses que non ;p)

Edit : Donc tu penses que, pour ce que j'ai à faire, ma boucle while et mon boolean ne me servent à rien ?

[Franck Dernoncourt]

Très franchement je n'ai pas du tout réfléchi à l'algorithme, c'est juste qu'en parcourant le code afin de voir la complexité (qui est de O(mn * O(Retablir(B,i,j)) au passage si on enlève la boucle tant que) je ne vois pas à quoi sert la boucle "tant que" car soit il n'y a qu'une seule itération, soit il y en a une infinité.

[larchicha]

J'ai pas très bien cerné le problème mais en tout cas, merci de ton implication.

[larchicha]

Ok je ré-écris l'algo voir si ça a plus de sens à vos yeux :

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
void Inserer(B : batière, x : entier) :
	i, j : entiers ;
	b : boolean ;
	b = faux ; 
	pour i de 1 à B.n faire :
		pour j de 1 à B.m faire : 
                       tant que (!b):
				si (B[i][j] == + l'infini) : // case vide = + l'infini
					B[i][j] = x ; // insère l element x dans la case vide
					b = vrai ;	
				fin si.
                         fin tant que
 	                 Retablir(B,i,j);
		fin pour
	fin pour
fin algo

A mes yeux : Je parcours toute la matrice avec la double boucle pour, tant que mon boolean b est faux, je teste si la matrice comprend une case vide ( = +l'infini ), et si oui j'insère mon élément x, assigne vrai à la variable b , sort de ma boucle tant que puis Rétablir(B,i,j) .

Je suis désolé de vouloir placer à tout prix la boucle tant que mais si vous voyez un moyen plus simple de ne pas remplir toutes les cases vides (+ l infini) par l'élément x, je prends...

Merci d'avance.

[Franck Dernoncourt]

Pour sortir d'une boucle, le plus simple est d'utiliser un break.

Dans le cas de boucles imbriquées, si tu veux sortir de toutes les boucles, comme tu as fait il faut en général utiliser un booléen et l'ajouter dans la condition d'itération. (je dis en général car dans certains langages on peut spécifier la profondeur du break).

[larchicha]

Merci de tes réponses .