Etude des Palindromes

Rappel du premier message :

Salut,
Un palindrome est un ensemble de mots qui peuvent être lus de droite à gauche et de gauche à droite tout en conservant le même sens.

Exemples de mots-palindromes:
RADAR, ROTOR, ÉTÉ

Exemples de mots-palindromes:
Engage le jeu que je le gagne
Esope reste ici et se repose.
Elu par cette crapule.
Eh, ça va, la vache ?

On se propose de trouver le meilleur algorithme qui vérifie si une chaine de caractère est un palindrome ou non. On entend par "meilleur algorithme" l'algorithme le plus optimisé, le mois coûteux en temps de calcul et complexité etc...

Vous pouvez proposer vos algorithmes (ou bien code sources C, Pascal, JAVA...) et qu'on discute ensemble leur complexité.

Bonne recherche.

Références et liens utiles:
http://martine6.club.fr/musimage/palindrome/palindromes.htm
http://jose.rouillard.free.fr/PlasticML/hypertext-roles-hierarchiques/2.php?role=3

La solution de manianis est très claire et bien rédigée.

Code:

   
while (est_pal && i < j)
    {
      est_pal = (mot[i] == mot[j]);
      i++; j--;
    }


la variable "j" est pourtant inutile à mon avis, non?

La variable j n'est pas si inutile qu'il le semble. La boucle devra s'arrêter au milieu du mot.

je rectifie:
je parle de la décrémentation de "j" qui est inutile à mon avis.
on peut s'en passer et gagner une instruction de moins.

peut être en remplaçant comme ceci :

j = strlen(mot)-1;

while (est_pal && i < j)
{
est_pal = (mot[i] == mot[j-i]);
i++;
}

Attention j'ai remplacé une instruction j++ par j-i qui revient au même.

oui c'est exactement ce que je veux dire...

mais avec:

Code:

while (est_pal && i <= j/2)

C'est le même problème j/2 est évalué avant chaque itération.

il ne reste qu'à les prouver par un test sur des instances de grandes tailles...

Mais, ça prouve à tout le monde qu'il faut accorder une grande importance aux instructions qu'on met dans notre code source.

Admin a écrit:

c'est pas vrai lamia. Le test ne se poursuit pas (haka tawa:p)
Remarque bien l'existence du Return dans la boucle. Il stoppe l'exécution de la méthode dès qu'il y a un caractère mal placé.

Sorry, oui t'as raison. J'ai pas vraiment fait attention

je crois que la complexité de l'algorithme est n/2 où n est la taille du mot.

manianis a écrit:Je propose le code suivant :

Code:


#include
#include

int main()
{
    int i, j;
    char mot[100];
    bool est_pal = true;

    printf("écrire un mot\n");
    gets(mot);

    i = 0;
    j = strlen(mot) - 1;

    while (est_pal && i < j)
    {
      est_pal = (mot[i] == mot[j]);
      i++; j--;
    }

    if (est_pal)
    {
      printf("%s est un mot palindrome\n",mot);
    }
    else
    {
      printf("%s n'est pas un mot palindrome\n",mot);
    }

    return 0;
}

pourquoi on a affecté 0 à i au début?

Pour plusieurs raisons:
(1) elle est utilisée dans la conditions while donc elle doit avoir une valeur initiale
(2) elle est utilise dans la boucle (++i) donc elle doit être initialisée avant cette instruction.

peut-on l'initialiser à 1? et que va donner mot[0] à la première itération? la première lettre du mot?

mot[0] == 1er caractère de la chaine mot.
on ne peut pas l'initialiser à 1. Ca fausse l'algorithme.

informix a écrit:je crois que la complexité de l'algorithme est n/2 où n est la taille du mot.

je crois que c'est correct. C'est n/2 la complexité. C'est un algorithme linéaire.

good man
----
corrigée par le modérateur

Salut , je suis en 3 éme année Info et voila ma solution

Code:

program SnOOpeR;
uses wincrt;
var
i,j:integer;
ch,ch1:string;
msg:boolean;
begin
read(ch);
i:=length(ch)+1;
j:=0;
msg:=true;
repeat
i:=i-1;
j:=j+1;
ch1[j]:=ch[i];
write(ch1[j]);
if ch[i]=ch[j] then
msg:=true
else msg:=false;
until (msg=false) or (j=length(ch));
if msg=true then
write('oui')
else write('non');
end.

@snooper ta solution n'est pas très correcte... tu sais pourquoi?

suppose que c'est CH est une chaine de caractère vide ? ou contenant un seul caractère? Alors ...

Soit tu dois faire un contrôle sur CH, soit tu utilise la boucle WHILE (Tant Que)..

nabiL a écrit:@snooper ta solution n'est pas très correcte... tu sais pourquoi?

suppose que c'est CH est une chaine de caractère vide ? ou contenant un seul caractère? Alors ...

Soit tu dois faire un contrôle sur CH, soit tu utilise la boucle WHILE (Tant Que)..

bon retour ! hal ghiba?