Etude des Palindromes

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

Un anacyclique est un mot ou phrase que l'on peut lire à l'envers ou à l'endroit. Contrairement à un palindrome, un anacyclique a une signification différente selon le sens de lecture. On entend, par définition, que les anacycliques sont aussi des anagrammes.
Exemples :

• « Léon » et « Noël »
  
• « Luc » et « cul »
  
• « tracé » et « écart ».
  
• « mon » et « nom »
  
• « saper » et « repas »
  
• « l'ami naturel » et « le rut animal »
  

Des phrases peuvent être anacycliques quant aux mots qui les composent.
Exemple :

• « Souffrir sans amour, l’oublies-tu parfois ? » et « Parfois, tu oublies l’amour sans souffrir »
  
• « Vivre pour manger » et « manger pour vivre »
  

Merci Lamia
Behi ki kol youm wehed yet3alem haja jdida

Bon courage @+

Lamia: tu as bien choisi les methodes et les attributs. Je te félicite. Tu es bien rodée en JAVA à ce qu'il parait, et c'est rare de trouver des filles qui bossent et qui apprennent à programmer:) [à mon avis]

Une remarque sur la mise en forme de ton message:
Essaie de mettre ton code source entre les balises [ code] et [/ code] pour qu'il soit plus lisible.
Il aura la forme suivante:

Code:

public class palindrome {
    private String str;
    public palindrome(String S) {
        str=S;
    }

    public String inverser(){
        String ch= "";
  ....
}

J'ai une autre remarque qui concerne la conception de la classe.
Pour vérifier qu'une String est palindrome on n'est pas obligé de créer une copie de notre mot qui peu exister dans un texte etc..., mettre cette copie dans "str" en utilisant le constructeur de la classe Palindrome, puis appeler la méthode verifPalindrome().
C'est un peu long, voire inutile de faire tout ça.

Il y a une autre façon plus Orientée Objet qui répond à la question.
Essaie de la deviner...

Merci Sami pour ces remarques, et je vais essayer de chercher cette façon.

Lamia: methodiX a raison.

La vérification si une chaine est palindrome ou non se fait par une simple méthode. Où mettre cette méthode? dans la classe String? non biensur... on doit créer une classe et y mettre uniquement une méthode STATIC qui teste si un mot est palindrome ou non!

J'espère que t'as pris ça comme indication...

ceci est mon essai(en C++);

#include<stdio.h>
#include<string.h>
void main()

{int i,j,compt_true;
char mot;

printf("écrire un mot");
scanf("%c",&mot);

i=1;j=strlen(mot);compt_true=0;
do
{if (mot[i]==mot[j])
{compt_true++;}
i++;
j--;}
while ((i<strlen(mot)) && (j>1));

if (compt_true==strlen(mot))
{printf("%c est un mot-palindrome",mot);}
else{printf("%c n'est pas un mot-palindrome",mot);}
}
commentaire; j'ai utilisé la variable compt_true qui augmente d'un pas si mot[i]=mot[j] donc elle doit être égale à la longueur du mot pour que ce dernier soit palindrome.

ça l'air de marcher. Je l'ai pas encore compilé.

char mot; est pourtant incorrect (il faut déclarer un tableau de char et non pas un caractère). Tu devras écrire par la suite:
scanf("%s",mot); et non pas scanf("%c",&mot);

A part ça, ce n'est pas optimisé du tout
puisque ton programme exécute toujours N comparaisons pù N est la longueur du mot. Alors que si le mot est non palindrome, il suffit de s'arrêter dès qu'on trouve un caractère mal placé!

NB: même si le mot est palindrome, il suffit de faire N/2 comparaisons!

...à suivre @+

je propose la solution suivante:

Code:

public class palindrome {
    public static boolean estPalindrome(String mot) {
          if (mot==null) return false;
          int size = mot.length();
          for (int i=0;i
                if (mot.charAt(i)!=mot.charAt(size-i+1))
                  return false;
          return true;         
      }
}


je l'ai pas compilé... j'attends des commentaires.

Amusez-vous à calculer la complexité en nombre de comparaisons du programme ci-dessus.

j'attends vos réponses !

Je ne vois pas ce qu'est la variable : size

Je propose cette version:

Code:

public static boolean verifPalindrome(String str){
boolean test=true;
int i=0;
while (i < str.length()/2 && test){
if(str.charAt(i)!=Str.charAt(str.length()-1-i))
test=false;
i++;
}
return test;
}

Dans la proposition d'Admin, le test se poursuit meme si on trouve que dés le premier test est False (vu que c'est une boucle for).

manianis a écrit:Je ne vois pas ce qu'est la variable : size

Dans Java size n'existe pas mais plutot len = mot.length()

manianis a écrit:Je ne vois pas ce qu'est la variable : size

Je vais vous expliquer:

ON DOIT UTILISER UNE VARIABLE pour stocker la longueur du mot quelque part. J'ai appelé cette variable SIZE.
Size = mot.length();

Savez-vous pourquoi on doit l'utiliser cette variable ???

Merci, Lamia et Nabil pour l'explication.

Nabil, je dirai qu'une des variables : size ou len est inutile dans votre bout de programme ci-dessus.

Lamia, Nabil dit vrai il est mieux d'utiliser cette variable size pour optimiser le temps d'exécution du programme :
Il est préférable d'appeler la méthode length une seule fois que de l'appeler au début de chaque itération de la boucle for. N'est-ce pas Nabil !

lamia a écrit:Je propose cette version:

Code:

public static boolean verifPalindrome(String str){
boolean test=true;
int i=0;
while (i < str.length()/2 && test){
if(str.charAt(i)!=Str.charAt(str.length()-1-i))
test=false;
i++;
}
return test;
}

Dans la proposition d'Admin, le test se poursuit meme si on trouve que dés le premier test est False (vu que c'est une boucle for).

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

manianis a écrit:Merci, Lamia et Nabil pour l'explication.
Nabil, je dirai qu'une des variables : size ou len est inutile dans votre bout de programme ci-dessus.
Lamia, Nabil dit vrai il est mieux d'utiliser cette variable size pour optimiser le temps d'exécution du programme :
Il est préférable d'appeler la méthode length une seule fois que de l'appeler au début de chaque itération de la boucle for. N'est-ce pas Nabil !

oui exactement, j'ai écrit len = size c'est une faute de copier-coller, je l'ai rectifiée dans le code source.
Il faut utiliser cette variable pour éviter les appels inutiles de la méthode String.Length().

Bienque ça je sois certain qu'elle ne contient aucune boucle dans la classe String (déclarée final malheureusement)

#include<stdio.h>
#include<string.h>

void main()
{int i,j;
char *mot;
bool x;

printf("écrire un mot\n");
scanf("%c",&mot);

i=1;
j=strlen(mot);
x=true;

do
{if (mot[i]==mot[j])
{x=true;
i++;
j--;}
else {x=false;}
while ((x=true) && (i<=strlen(mot)/2)

if (x==true)
{printf(" %c est un mot palindrome",mot);}
else {printf(" %c n'est pas un mot palindrome",mot);}
}

Admin a écrit:...
Il faut utiliser cette variable pour éviter les appels inutiles de la méthode String.Length().

Bienque ça je suis certain qu'elle ne contient aucune boucle dans la classe String (déclarée final malheureusement)

Oui, et voila le code source de cette méthode copié/collé :

Code:

  /**
    * Returns the length of this string.
    * The length is equal to the number of <a href="Character.html#unicode">Unicode
    * code units</a> in the string.
    *
    * @return  the length of the sequence of characters represented by this
    *          object.
    */
    public int length() {
        return count;
    }

je l'ai pas compilé mais, je crois qu'il y a des erreurs:

Code:

printf("écrire un mot\n");
scanf("%c",&mot);

il faut d'abord allouer de l'espace à la variable mot, qui devrait être une chaine de caractère. (%s) et (mot) dans scanf...

le nom des variables: i, j, x, ... il faut choisir de bons noms de variables: avoir de bonnes habitudes de programmation.

"true" n'existe pas en C/C++.

Mais c'est un bon programme surtout que tu l'as écrit sans compilation.

Je propose le code suivant :

Code:


#include <cstdio>
#include <cstring>

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

bool var_bool;

le type bool a été normalisé en C++ et elle n'existe pas normalement en C.