algo supprimer espaces consecutifs

Bonjour j'essaie de faire un programme qui supprime les espaces en trop dans une chaine de caractère j'ai donc fait l'algo suivant :

Code:

---

1 2 3 4 5

pour i<-1 à longueur(chaine) faire si (chaine[i]=' ') et (chaine[i+1]=' ') alors chaine[i]<-chaine[i+1] fin si fin pour

---

a partir de cela j'ai fait le programme en pascal pour delphi :

Code:

---

1 2 3 4 5 6 7

for i:=1 to length(chaine) do begin if ((chaine[i]=' ') and (chaine[i+1])) then begin chaine[i]:= chaine[i+1]; end; end;

---

mais mon probleme est que ce code ne fonctionne pas et je ne sais pas pourquoi est ce que vous pourriez m'expliquer quelle erreur j'ai fait dans mon algo ?

Citation:

---

Envoyé par amateurc

Code:

---

1 2 3 4 5

pour i<-1 à longueur(chaine) faire si (chaine[i]=' ') et (chaine[i+1]=' ') alors chaine[i]<-chaine[i+1] fin si fin pour

---

---

Bonjour,

Avec ce code, tu ne fais rien de particulier : primo, tu traites uniquement le cas où tu as un seul espace en trop, donc ça ne marchera pas pour deux, trois, etc. espaces ! Secundo, tu ne fais aucune suppression (décalage à gauche) puisque tu affectes l'espace en trop de la droite à celui de la gauche... Donc, tu dois réfléchir à nouveau à ton algorithme.
__________________
- Premièrement, il faudra réfléchir;
- Deuxièment, chercher;
- Finalement, poser son problème en le décrivant correctement.

Citation:

---

Envoyé par amateurc;2969764
[CODE

for i:=1 to length(chaine) do
begin
if ((chaine[i]=' ') and (chaine[i+1])) then
begin
chaine[i]:= chaine[i+1];
end;
end;[/CODE]

---

Regarde ce que j'ai mis en rouge tu as oublié un test.
Et comme le dis paronyme tu ne fait que copier un espace dans un espace ca ne changera pas ta chaine.
Tu pourrais par exemple recopier ta chaine dans une nouvelle chaine, en ne copiant qu'un seul espace maximum si tu en détecte plusieurs à la suite.

Bonjour,

D'après le message, tu as écrit ton programme en pascal pour Delphi.
Il me semble (mais c'est très veiux dans ma mémoire :mrgreen:) que des fonctions tel Trim existe, qu'il est peut-être pas utile de t'enquiqiner à réécrire un tel algo 8-).
Sinon persévère si tu tiens à l'écrire toi-même.;)

A partir de ce que vous m'avez dit j'ai refait un algorithme :

Code:

---

1 2 3 4 5 6 7 8 9 10

pour i<-1 à longueur(chaine) faire si (chaine[i]<>' ') alors chaine2[j]<-chaine[i] fsi si (chaine[i]=' ') et (chaine[i+1]<>' ') alors chaine2[j]<-' ' fsi j=j+1 fpour

---

est ce que vous pouvez m'indiquer si il y a un problème avec celui ci

Ca a l'air bon.
Par contre fait attention tu fait un debordement dans les indices :

Code:

---

si (chaine[i]=' ') et (chaine[i+1]<>' ') alors

---

Comme tu vas jusqu'a longueur(chaine) chaine[i+1] n'existe pas.

Tu peux remplacer ce test par :

Code:

---

si (chaine[i]=' ') et (i <= longueur(chaine) ou (chaine[i+1]<>' ')) alors

---

Normalement si i > longueur de chaine il ne testera pas chaine[i+1] (en C c'est vrai en tout cas, apres je sais pas).

Sinon tu peux aller de 1 a longueur(chaine) - 1 et à la fin recopier chaine[longueur(chaine)].

mon idée est basé juste sur pascal. voilà on va chercher tous les double espace dans la chaine
on va boucler avec "tantque" pour chaque double éspace on va effacer un.
c'est tout
while pos(" ",ch)<>0 do
delete(ch,pos(" ",ch),1);

NB: pos est une fonction prédefini de pascal qui donne la position d'une chaine dans une autre
delete est une procédure qui éfface d'une chaine un nombre de caractère apartir d'une position

c'est testé, amuse toi bien:roll:

bah ton algo initial etait sur une bonne base, mais pas tout a fait...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

vrai = 1   Tant que vrai vrai = 0   si longueur(chaine) > 1 pour i = 1 à i = (longueur(chaine)-1) faire si (chaine[i]=' ') et (chaine[i-1]=' ') alors si i different de (longueur(chaine)-1) pour j = i+1 a j = (longueur(chaine)-1) chaine[j]<-chaine[j+1] fin pour fin si   longueur(chaine) = longueur(chaine) - 1 vrai = 1 sortie pour fin si fin pour fin si fin tant que

---

Bonjour,

Et comment traites-tu le cas où et l'avant dernier et le dernier caractère correspondaient à un espace ? C'est-à-dire, par exemple :

Code:

---

1 2 3 4

longueurChaîne = 10; chaîne = "développ__"; _ : espace

---

Je pense que ton algorithme est incomplet. ;)
__________________
- Premièrement, il faudra réfléchir;
- Deuxièment, chercher;
- Finalement, poser son problème en le décrivant correctement.

Citation:

---

Envoyé par paronyme

Je pense que ton algorithme est incomplet. ;)

---

Bah ça enlève tous les doubles espaces.. ce qui était le titre du post :

Citation:

---

supprimer les espaces consécutifs

---

Si maintenant on veut vérifier que le dernier caractère n'est pas un espace, il suffit de le faire à la fin :P

Et il faut à ce compte-là le faire aussi pour le premier caractère... mais aussi à la fin...

Mais je ne crois pas que c'était le pbe du PO. Mais pour être complet, c'est ça qu'il faudrait faire..

Ces algorithmes semblent être en O(n^2) inutilement (sans parler des petites étourderies dans le code de Souviron34 (où le j de la boucle semble ne servir à rien quoique... ;) )).

Un seul parcours de la chaîne suffit à faire le travail :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Recul := 0   Pour i = 2 à Longueur(Chaine) Si Chaine[i-1-Recul] == ' ' Et Chaine[i] == ' ' Recul := Recul + 1 Sinon Si Recul > 0 Chaine[i-Recul] := Chaine[i] FinSi FinPour   Longueur(Chaine) := Longueur(Chaine) - Recul

---

Ce code ne parcours qu'une fois la chaîne et fait parfaitement le boulot.

--
Jedaï

Moi j'utiliserais une machine à états de ce type :

deux indices de parcours de la chaine
lec pour la lecture caractère par caractère
ecr pour l'écriture caractère par caractère
tous deux initialisés à 0 (si on travaille en C).

Trois etats du programme

etat = 0 => initialisation du programme
etat = 1 => pas d'espace lu
etat = 2 => espace lu

etat est initialisé à 0.

transitions
etat = 0 caractère lu <> espace => etat = 1 on recopie le caractère de lec en ecr on incrémente les deux indices
etat = 0 caractère lu = espace etat = 0, on incrémente lec

etat = 1 caractère lu <> espace etat = 1 on recopie le caractère de lec en ecr on incrémente les deux indices
etat = 1 caractère lu = espace , etat = 2, on recopie le caractère de lec en ecr on incrémente les deux indices

etat = 2 caractère lu <> espace etat = 1 on recopie le caractère de lec en ecr on incrémente les deux indices
etat = 2 caractère lu = espace , etat = 2, on incrémente lec.

En fin de lecture de la chaîne, si on est dans l'état 2, on décrémente ecr de 1.
Dans tous les cas, on n'oublie pas de mettre à 0 le caractère pointé par ecr(si on travaille en C).

Ca fait du O(n) ?

Ma méthode oui.

la mienne aussi... ;)

Citation:

---

Envoyé par Jedai

Ces algorithmes semblent être en O(n^2) inutilement (sans parler des petites étourderies dans le code de Souviron34 (où le j de la boucle semble ne servir à rien quoique... ;) )).

---

Ooops :oops: corrige...

Mais non, il n'est pas en O(n^2) mais en O(n) si on ajoute juste une variable pour redemarrer la boucle au bon endroit (j'avais fait simple pour le premier coup) :

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

vrai = 1 depart = 1 Tant que vrai vrai = 0 si longueur(chaine) > 1 pour i = depart à i = (longueur(chaine)-1) faire si (chaine[i]=' ') et (chaine[i-1]=' ') alors si i different de (longueur(chaine)-1) pour j = i+1 a j = (longueur(chaine)-1) chaine[j]<-chaine[j+1] fin pour fin si longueur(chaine) = longueur(chaine) - 1 vrai = 1 depart = i sortie pour fin si fin pour fin si fin tant que

---

:P

par contre, Jedai, ta methode ne tient pas compte du fait que la longueur change, et que donc tu vas aller dans les choux.... (longueur chaine n'est pas reevaluee a chaque fois...)

Mais ca marcherait en le prenant a l'envers (de la fin vers le debut...) ;)

Citation:

---

Envoyé par Trap D

Moi j'utiliserais une machine à états de ce type :

deux indices de parcours de la chaine
lec pour la lecture caractère par caractère
ecr pour l'écriture caractère par caractère
tous deux initialisés à 0 (si on travaille en C).

Trois etats du programme

etat = 0 => initialisation du programme
etat = 1 => pas d'espace lu
etat = 2 => espace lu

etat est initialisé à 0.
** snip **
En fin de lecture de la chaîne, si on est dans l'état 2, on décrémente ecr de 1.
Dans tous les cas, on n'oublie pas de mettre à 0 le caractère pointé par ecr(si on travaille en C).

---

Congratulation, tu viens de formaliser mon algorithme écris juste au-dessus. (la seule différence c'est que tu retiens deux indices là où j'en retiens un et un décalage)

Citation:

---

Envoyé par souviron34

la mienne aussi... ;)

Mais non, il n'est pas en O(n^2) mais en O(n) si on ajoute juste une variable pour redemarrer la boucle au bon endroit (j'avais fait simple pour le premier coup) :

---

Et non, même avec cette modification il reste fondamentalement en O(n^2) : exécute le simplement sur une chaîne ne comportant que des espaces, il va déplacer (n-2) caractères, puis (n-3), puis (n-4), etc jusqu'à n/2 environ, cette somme est en O(n^2). Plus exactement ta méthode est en O(nm) (avec n le nombre de caractères et m le nombre d'espaces). Tandis que la mienne comme celle de Trap D sont en O(n).

Citation:

---

Envoyé par souviron34

par contre, Jedai, ta methode ne tient pas compte du fait que la longueur change, et que donc tu vas aller dans les choux.... (longueur chaine n'est pas reevaluee a chaque fois...)

---

Tu te trompes, de mon point de vue la longueur de la chaine ne change pas à chaque étape, elle ne change qu'à la fin. Relis attentivement mon code (ou lis l'explication de Trap D si c'est plus facile pour toi).

--
Jedaï

:hola:

je m'incline devant les maitres ;)

j'avais effectivement lu un peu vite... :oops:

Citation:

---

Envoyé par Jedai

Congratulation, tu viens de formaliser mon algorithme écris juste au-dessus. (la seule différence c'est que tu retiens deux indices là où j'en retiens un et un décalage)Jedaï

---

J'ai un peu tendance à penser que ce que j'ai écrit est plus simple à comprendre que ton algo, même si tu dis que c'est le même, n'oublions pas que le P.O. est débutant ;)