Palindrome en Delphi

Version imprimable

15/01/2007, 12h44
nadir07

Palindrome en Delphi

Svp je débute en delphi! J'aimerais vérifier si une chaîne de caractère est un palindrome. Tout ceci en passant par les boucles. Merci si quelqu'un pouvait m'aider
15/01/2007, 13h09
LadyWasky

Tu as bien une petite idée d'algorithme non ?

Citation:

var Mot:string;
L:integer;
Longeur(Mot)->L

Si Mot[1]=Mot[L]
et Si Mot[2]=Mot[L-1]
et Si Mot[3]=Mot[L-2]
...
et Si Mot[(L div 2)]=Mot[L-(L div 2)+1]
alors c'est un palindrome
sinon ce n'est pas un palindrome

Pour faire le si, il y a donc une boucle à faire (un while devrait bien fonctionner) ;)

Pour celà, tu dois utiliser un booleen (que tu appelles identique), que tu initialise à True, et à chaque fois que tu compares deux lettres, tu le met à jour comme ceci :

Code:

identique:=(identique and (Mot[i]=Mot[L+1-i]));

tu arrètes dès que i>(L div 2) ou dès que identique=false

puis tu récupère le contenu de ton boolean qui te dis si tu as un palinfrome ou non.

Ce ne serait pas un devoir d'école par hasard ? :nono:
15/01/2007, 13h32
thewho

Bonjour,

Attention, avant la comparaison, il faut traiter ta chaîne de caractères.

- supprimer tout ce qui n'est pas une lettre (espaces, symboles ponctuations...)

- transformer tous les caractères avec signe diacritique (accents, cédille...) en leur équivalent simple (par exemple Éôçé devient Eoce)

- Passer toutes les lettres en majuscules OU en minuscules, au choix

Après cela, tu peux tester si c'est un palindrome.

Comme c'est la période, c'est probablement un devoir d'école, comme le suppose waskol.

Bonjour

Voici un exemple qui fonctionne

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
procedure TForm1.Button1Click(Sender: TObject);
 
Var
StrIn : String;
i, l : Integer;
begin
  StrIn := 'elu par cette crapule';
  i := 0;
  while i < Length(StrIn) do
  begin    //  Suppression des espaces
    if StrIn[i] = ' ' then StrIn := Copy(StrIn,0,i-1)+ copy(StrIn, i+1, Length(StrIn)-1);
       Inc(i);
  end;
  l := Length(StrIn);
  For i := 1 to l do
  begin
    if StrIn[i] <> StrIn[l-i+1] then break;
  end;
  if i < l then ShowMessage(StrIn +' n''est pas un palindrome')
                       else ShowMessage(StrIn +' est un palindrome');
end;

Je n'ai fait que supprimer les espaces entre les mots.
Il reste à faire de même pour la ponctuation, les apostrophes, etc..
Et bien sûr, comme le dit TheWho, mettre tout en minuscule et transformer les caractères accentués.

15/01/2007, 14h42
LadyWasky

Oui, et aussi, pour la boucle, ce n'est pas la peine de la faire de 1 à L (de 1 à (L div 2)) devrait suffire (hé oui on compare la moitié gauche du mot avec sa moitié droite, symétrie oblige)

Remarque de puriste, j'apprécie.
Je constate qu'il n'y a pas que les vieux programmeurs, qui devaient pourchasser le gaspillage de mémoire avec le peu qu'en avait leurs machines, qui relèvent la beauté de la programmation minimaliste.

Cela donne donc :
Code:

1 2 3 4 5 6 7 For i := 1 to l Div 2 do begin if StrIn[i] <> StrIn[l-i+1] then break; end; if i < l Div 2 then ShowMessage(StrIn +' n''est pas un palindrome') else ShowMessage(StrIn +' est un palindrome');

15/01/2007, 15h43
LadyWasky

Citation:

Envoyé par defluc

Remarque de puriste, j'apprécie.
Je constate qu'il n'y a pas que les vieux programmeurs, qui devaient pourchasser le gaspillage de mémoire avec le peu qu'en avait leurs machines, qui relèvent la beauté de la programmation minimaliste.

Excuses moi, c'était juste un réflexe pas une remarque de puriste.;)
Mon Oric Atmos, à l'époque, aurait ramé à mort si je n'avais pas opté pour une 'tite optimisation. Le réflexe est resté :aie:

@defluc
pas grand chose, mais si ton test échoue à la dernière itération, i sera quand même égal à (L div 2) non ?

Exemple :

Citation:

ABDA

Je propose ton début de code et celui-ci :;)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 var identique:boolean ... identique=true; i:=1; while ((i<=L div 2) and identique) do begin identique:=identique and (StrIn[i]=StrIn[l-i+1]); inc(i); end; if identique then ShowMessage(StrIn +' est un palindrome') else ShowMessage(StrIn +' n''est pas un palindrome');
En plus, il n'y a ni break, ni boucle for, donc ça va plaire au prof ;)

15/01/2007, 16h22
defluc

Non mais sans blaguer, quand je dis que j'apprécie c'est vraiment que je le prends bien. Etre puriste, c'est une qualité pour moi, surtout à une époque où tout fout l'camp. Il suffit de voir l'orthographe. Je suis du genre à être heureux plutôt que vexé si on me fait progresser dans le sens de la rigueur.

Salut

Puisqu'on est dans les cas d'école, une autre approche sans boucle avec une fonction récursive:

Code:

1
2
3
4
5
6
7
8
9
10
11
 
function EstPalindrome(S: string): Boolean;
begin
  if Length(S) < 2 then
    result := True
  else
    if (S[1] = S[length(S)]) then
      result := EstPalindrome(Copy(S, 2, Length(S) - 2))
    else
      result := False;
end;

15/01/2007, 16h42
LadyWasky

Citation:

Envoyé par defluc

Non mais sans blaguer, quand je dis que j'apprécie c'est vraiment que je le prends bien. Etre puriste, c'est une qualité pour moi, surtout à une époque où tout fout l'camp. Il suffit de voir l'orthographe. Je suis du genre à être heureux plutôt que vexé si on me fait progresser dans le sens de la rigueur.

Ha ? hé bien mille mercis alors, c'est vraiment sympa, j'aprécie de façon réciproque :P
15/01/2007, 17h10
qi130

Citation:

Envoyé par Cl@udius

Salut

Puisqu'on est dans les cas d'école, une autre approche sans boucle avec une fonction récursive:

Oui, mais le contrat stipule l'emploi de boucle :roll:

Sinon, il y avait ReverseString (au moins en D6) ;)
15/01/2007, 17h33
Cl@udius

Citation:

Envoyé par qi130

Oui, mais le contrat stipule l'emploi de boucle :roll:

Me voilà éliminé du défi ! :aie: Dommage je trouvais ça élégant comme approche.

@+ Claudius
15/01/2007, 19h03
qi130

Citation:

Envoyé par Cl@udius

Me voilà éliminé du défi ! :aie: Dommage je trouvais ça élégant comme approche.

@+ Claudius

Ah, mais ça n'enlève rien à l'élégance de ta solution :)

Tant qu'à chercher des petites optimisations, on peut aussi arrêter la boucle dès qu'on a découvert que ce n'était pas un palindrome. De même, on peut utiliser un downto pour ne pas devoir recalculer Length(Str) div 2 à chaque passage...
Code:

1 2 3 4 5 6 7 8 9 function IsPalindrome(const Str : string); var Len1, I : integer; begin Result := False; Len1 := Length(Str)+1; for I := Length(Str) div 2 downto 1 do if Str[i] <> Str[Len1-I] then exit; Result := True; end;
Pour purger la chaîne en un temps relativement court, on peut aussi précalculer un tableau de conversion :
Code:

1 2 3 4 const PurgedChars : array[#$20..#$FF] of Char = ( #0, #33, ... );
Ensuite on peut l'utiliser pour traiter la chaîne en moins de temps qu'il n'en faut pour le dire :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 procedure PurgeString(var Str : string); var I, J : integer; C : Char; begin J := 0; for I := 1 to Length(Str) do begin C := PurgedChars[Str[i]]; if C <> #0 then begin inc(J); Str[J] := C; end; end; SetLength(Str, J); end;
Ah ! Ca détend un peu d'algo après l'exam de maths :mouarf: :aie: