Discussion :

[amateurc]

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 :

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

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 :

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

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 ?

[Hedidams]

Code :

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

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.

[contremaitre]

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.

[Lowelace]

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 ) que des fonctions tel Trim existe, qu'il est peut-être pas utile de t'enquiqiner à réécrire un tel algo .
Sinon persévère si tu tiens à l'écrire toi-même.

[amateurc]

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

Code :

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

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

[contremaitre]

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

Code :

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

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 :

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

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)].

[haythem78]

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

[souviron34]

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

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

[Hedidams]

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 :

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

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.

[souviron34]

Je pense que ton algorithme est incomplet.

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

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

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

[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... )).

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

Code :

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

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ï

[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.

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).

[Alp]

Ca fait du O(n) ?

[Trap D]

Ma méthode oui.

[souviron34]

la mienne aussi...

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

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

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...)

[Jedai]

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)

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).

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ï

[souviron34]

je m'incline devant les maitres

j'avais effectivement lu un peu vite...

[Trap D]

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