Discussion :

[amazircool]

Pouvez vous m’aider ?
Je vais savoir un algorithme qui consiste à vérifier si un mot entré au clavier est un
“Palindrome”. Un palindrome est une chaîne de caractères réversible (chaîne qui peut se lire
dans les deux sens ex : elle, ressasser, … ).
merci :=)

[PRomu@ld]

L'algorithme est relativement simple si tu le conçois de manière récursive :

-> Si tu as aucune ou une seule lettre, c'est un palyndrome.

-> S'il y a deux lettre et plus, tu regardes si la première et la dernière sont identiques, si c'est le cas, tu rappelle la fonction avec le mot otté des premières et dernières lettres.

Voici un pseudo code avec une syntaxe proche d'ada.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
function palyndrome ( S : String(1..N) ) return boolean is
begin
     if S.length = 0 or S.length = 1 then
          return true;
     else
          if S(1) = S(n) then
               return palyndrome( S(2..N-1) );
          else
               return false;
          end if;
     end if;
end;

[Rukia]

Bonjour
Tu peux vérifier s il est palindrome d une autre méthode
Tu déclare deux compteurs le 1 pour le début et le 2 eme pour la fin (le compteur ^rend la taille de la chaine)
Tu incrémente le 1 et tu décrémente le 2 et tu test si ch [1]==ch[2]
L’arrête se feras si le 1compteur dépasse le 2
Bon courage

[droggo]

Jao,

@ PRomu@ld : je ne suis pas d'accord avec ceci :

Code :

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

1
2
     if S.length = 0 or S.length = 1 then
          return true;

Une chaîne de longueur 0 n'est pas un palindrome.

@ rukia-san : pas besoin de 2 compteurs : LE compteur va de 0 à longueur/2, et on compare s[compteur] à s[longueur-1-compteur]

[PRomu@ld]

C'est pour les besoins de l'algorithme (pour l'appel récursif). Ensuite, ça reste une convention, moi je considère que le mot vide peut se lire dans les deux sens, c'est donc un palindrome. Mais je ne connais pas exactement la définition du palindrome, j'ai pris celle ci parce qu'elle m'arrangeait pour la suite. (les mathématiciens en font de même de temps en temps )

Mais si tu as une définition différente, la modification dans l'algorithme est sans problème.

[pseudocode]

moi je considère que le mot vide peut se lire dans les deux sens

lol... j'adore !

au fait, y a combien de lettres imaginaires dans le mot vide ?

[droggo]

Pia,

Les dictionnaires disent, à l'unisson:

Palindrome : Mot, groupe de mots qui peut être lu indifféremment de gauche à droite ou de droite à gauche en conservant le même sens (ex. ressasser, élu par cette crapule)

Une chaîne vide n'est pas un mot, ni, a fortiori, un groupe de mots

[PRomu@ld]

J'ai dit que ça m'arrangeait d'avoir cette définition, un point c'est tout ! Pour moi l'ensemble vide ou le mot vide (epsilon) est un palyndrome, mais si la définition ne vous plait pas, libre à vous de modifier l'algorithme comme je vous l'ai dit juste avant.

C'est d'autant plus normal que factorielle de 0 qui vaut 1, que i^2 = -1 ... .

[pseudocode]

JC'est d'autant plus normal que factorielle de 0 qui vaut 1, que i^2 = -1 ... .

ou que 0 puissance 0 qui vaut heu... rien. Enfin "vide"

[droggo]

Jav,

J'ai dit que ça m'arrangeait d'avoir cette définition, un point c'est tout ! Pour moi l'ensemble vide ou le mot vide (epsilon) est un palyndrome, mais si la définition ne vous plait pas, libre à vous de modifier l'algorithme comme je vous l'ai dit juste avant.

Pas la peine de s'énerver comme ça

C'est d'autant plus normal que factorielle de 0 qui vaut 1, que i^2 = -1 ... .

Pas vraiment, le coup de la factorielle, c'est une convention définie depuis longtemps, et qui a sa raison d'être

[PRomu@ld]

Pas la peine de s'énerver comme ça

Je ne m'énerve pas, ne t'inquiète pas. Le problème c'est que je me suis déjà justifié sur cette convention et visiblement personne ne la lu.

Pas vraiment, le coup de la factorielle, c'est une convention définie depuis longtemps, et qui a sa raison d'être

Non, c'est un artifice qui arrange bien des choses mais qui n'a pas vraiment de logique. (à part peut-être que 1 est l'élément neutre de la multiplication).

Je viens de regarder encore un fois, en théorie des langages, le palindrome est définit pour epsilon (le mot vide) ...

[Korko Fain]

% On supprime les espaces et autres retours à la ligne de la chaine

% Si la longueur de la chaine est impaire (ou qu'elle vaut 0), la chaine n'est pas un palindrome

% Sinon, on test si le premier et le dernier caractère sont égaux. Si oui, on test la meme chose avec les 2 caractères suivants (2eme et avant dernier) et ainsi de suite.

Il sera tres rapide pour des non palindromes et sera un peu plus long pour les palindromes.

On peux le faire en récursif mais aussi en itératif.

[droggo]

Kja,

% On supprime les espaces et autres retours à la ligne de la chaine

% Si la longueur de la chaine est impaire (ou qu'elle vaut 0), la chaine n'est pas un palindrome

% Sinon, on test si le premier et le dernier caractère sont égaux. Si oui, on test la meme chose avec les 2 caractères suivants (2eme et avant dernier) et ainsi de suite.

Il sera tres rapide pour des non palindromes et sera un peu plus long pour les palindromes.

On peux le faire en récursif mais aussi en itératif.

Pour 0, on a réglé le problème, mais où as-tu vu qu'un palindrome avait forcément une longueur paire ? Ça vient de sortir ?

[Rukia]

salut
le mot "NON" est palindrome de longueur impaire

[droggo]

Jai,

salut
le mot "NON" est palindrome de longueur impaire

J'en ai un que je trouve plus approprié, parce que peut-être un peu relié au forum :

ressasser

[Korko Fain]

Oui effectivement, je n'avais pas penser au fait qu'un palindrome puisse avoir une lettre comme pillier.
Je cherchais juste une façon d'optimiser mais c'etait nul

[Zavonen]

On s'excite beaucoup sur l'algo de vérification que la lecture est reversible, passant sous silence les difficultés majeures:
Une chaîne est palindromique ABSTRACTION FAITE de la casse, de la ponctuation, des espaces DES ACCENTS, DES CEDILLES ET AUTRES BIZARRERIES (E dans l'O) DE LA LANGUE FRANCAISE !!!!
Le gros boulot c'est donc d'épurer la chaîne, de la transformer en une suite de caractères de A à Z et c'est tout.
C'est d'autant plus tannant que quand on programme en mode console, par exemple sous windows, le codage des bizarreries n'est pas le même que l'ANSI.