[C] fonction detecte palindrome

Résolu/Fermé
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 - 12 oct. 2010 à 11:51
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 - 13 oct. 2010 à 12:53
Bonjour bonjour tout le monde !!

j'ai dans l'idée de faire une petite fonction en C pour la detection d'un palindrome ( les mots qui sont les même écrit de gauche a droite ou de droite a gauche, exemple basique : "non")

sauf que ... ma fonction marche pas et j'ai beau cherché, je trouve pas l'erreur ...

si vous avez le temps de m'aider , voici le code :
bool palindrome(char *text)
{
    const int taille = strlen(text);
    int i,j = 0;
    char inverse[taille];
    for(i=taille-1;i<=0;i--)
    {
        inverse[j] = text[i];
        j++;
    }
    if(strcmp(inverse,text) == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}



merci a tout ceux qui pourront me donner un ptit coup de main ;-)


7 réponses

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
12 oct. 2010 à 12:22
Bonjour,

Déjà, bool n'est pas un type en C. Soit vous utilisez _Bool en C99, soit tout simplement int.
A moins que vous programmiez en C++...
char inverse[taille];
Ne marche qu'en C99, donc attention à bien activer le mode de votre compilateur. En C89/90, on utilise l'allocation dynamique avec malloc/calloc. De plus, faut faire attention d'allouer un caractère de plus pour le caractère de terminaison ('\0'). Ce qui donne : char inverse[taille+1];
Et une fois que vous avez rempli votre tableau inverse (donc après la boucle for), vous mettez : inverse[taille]='\0';

Idée d'amélioration de votre algorithme :
Pourquoi créer un tableau temporaire ? Un palindrome est un mot "symétrique". Autrement dit, la dernière lettre est égale à la première, l'avant-dernière à la seconde, etc.
Du coup, une seule boucle for avec une condition if, fait amplement l'affaire.

Cdlt,
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
12 oct. 2010 à 13:45
Ok pour stdbool.h, c'est en effet ce qu'il faut faire pour utiliser le type bool. Et il n'y a pas d'inconvénient à utiliser cette bibliothèque.

On attend ton nouvel algorithme ;-)
0
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 100
12 oct. 2010 à 16:57
me revoila avec un algo qui prend en compte vos diverses suggestions ... mais qui ne marche toujours pas, le problème étant qu'il renvoie toujours la valeur false ...

voici le code, j'ai trouvé judicieux de le commenter un peu, pour que vous puissiez comprendre mon raisonnement :
bool palindrome(char *text)
{
    const int taille = strlen(text); // taille egal le nombre de caractere
    printf("%d\n", taille); // on affiche pour verifie la taille
    int i, j, ctr=0; // i et j seront initialisé dans la boucle for
    /*
    on créé une boucle qui se repetera selon
    le nombre de caractere
    */
    for(i=taille,j=0 ; i>=0 ; i--,j++)
    {
        /*
        si le premier charactere est egal au dernier,
        un compteur est incrémenté
        on test ensuite le second avec l'avant dernier etc etc ...
        */
        if(text[j] == text[i]);
        {
            ctr++;
        }
    }
    printf("%d\n", ctr); // on affiche pour verifie le compteur
    /*
    si le compteur est égal a la taille de la chaine,
    tout les test on été positif,
    la chaine est donc un palindrome.
    */
    if(ctr == taille)
    {
        return true;
    }
    else
    {
        return false;
    }
}


peut-être un problème avec la taille des tableaux ? j'avoue ne pas être encore vraiment a l'aise avec leurs utilisation ... aussi j'avais penser divisé la boucle par deux (le mot étant symétrique) mais je testerai ça quand j'aurais résolu déjà ce petit problème.
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
12 oct. 2010 à 17:14
Vous initialisez i à taille alors que le dernier caractère se situe à l'indice taille-1.
De plus, ne mettez surtout pas de point virgule après un if
Sinon côté amélioration, vous pouvez aussi ajouter les points suivant :
Au lieu d'utiliser un compteur, vous pouvez tout simplement faire
for(...) {
   if (... != ...) {
      return false; //si un seul caractère est différent alors ce n'est pas palindrome
   }
}
return true; //si on sort de la boucle for, c'est que tous les caractères sont symétriques, donc palindrome.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
overcode Messages postés 119 Date d'inscription jeudi 6 décembre 2007 Statut Membre Dernière intervention 21 octobre 2011 27
Modifié par overcode le 12/10/2010 à 17:55
Edit : devancé par fiddy ;) Mais je laisse quand même le post

Bonsoir strato-boy,

Ils sont bien longs tous ces algorithmes ! Faut garder les choses simples :D
Pour le test du palindrome, on va parcourir la chaîne des deux côtés : à partir du début et à partir de la fin, en testant si les caractères sont égaux.

A la première différence détectée, le verdict tombe, ce n'est pas un palindrome.
Si le parcours se termine sans détecter de différence, alors on est en présence d'un palindrome.

Tes premiers algorithmes seraient corrects si tu faisais bien attention aux indices.
Dans ton premier algorithme, tu fais une mauvaise copie de ta chaîne (erreur dans les indices + oubli de '\0'). La copie est de toute façon inutile.

Dans le second algorithme, il y a une toute petite erreur sur l'indice i :
for(i=taille-1,j=0 ; i>=0 ; i--,j++)

au lieu de :
for(i=taille,j=0 ; i>=0 ; i--,j++)

En plus de la plus démoniaque des erreurs, celle responsable de mes quelques cheveux blancs :D, regarde bien ici :
if(text[j] == text[i]);

Le point-virgule après le if, quasi indétectable, faut l'enlever :D :D


Je te propose quelque chose de plus court :

Pour les parcours à double sens, on utilisera juste des indices bien calculés : pour le caractères d'indice i, son symétrique se trouve à l'indice taille - 1 - i.


bool palindrome(const char * s) 
{ 
    int n = strlen(s) ;    /* n est la taille de la chaîne */ 
    int i ;        /* indice pour le parcours de la chaîne */ 

    for( i = 0 ; i < n/2 ; ++i ) 
    { 
        if( s[i] != s[n - 1 - i] ) 
        { 
            return false ; 
        } 
    } 

    return true ; 
}


N'hésite pas si tu as d'autres questions :)
0
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 100
12 oct. 2010 à 18:15
effectivement devancé par fiddy mes ton approche est a peu près la même, comme dit plus haut
le point - virgule du if, j'ai honte !! ça faisait longtemp que je n'avait pas fait cette erreur !!

comme tu dis, ton algo est plus simple, mais je vais garder le mien ( tu me donne l'algo tout fait, j'aurais l'impression de juste pompé sur toi, c'est pas marrant ^^) mais bon après le fait de testé juste la moitié de la chaine j'y avait pensé mais bref .

j'ai 2 question pour toi : dans ton algorithme, tu passe en argumant
const char *s


le passage en constante est-il vraiment important ?
0
overcode Messages postés 119 Date d'inscription jeudi 6 décembre 2007 Statut Membre Dernière intervention 21 octobre 2011 27
Modifié par overcode le 12/10/2010 à 18:25
2 questions tu dis ? je n'en vois qu'une seule :)

Le passage en constante n'est pas très très important, mais ça permet 2 choses :

- Rendre la fonction palindrome plus pratique à utiliser, du genre pouvoir faire un appel :
palindrome("engage le jeu que je le gagne") ;

- Plus important, donner une indication au compilateur pour qu'il puisse faire plus de vérifications. La chaîne n'est pas censée être modifiée au sein de la fonction, une errer du genre s[i] = s[j] au lieu de s[i] == s[j] par exemple sera détectée par le compilateur si la déclaration de s est en const char *
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
12 oct. 2010 à 18:45
Pour appeler la fonction palindrome("...."), il n'y a pas besoin que le prototype soit en const. Qui peut le plus peut le moins.
Néanmoins, c'est une bonne idée pour permettre une meilleure performance des algorithmes d'optimisation de la part du compilateur, le programmeur voit de suite que l'argument ne sera pas modifié, ...
Et d'ailleurs, il faudrait même mieux mettre : bool palindrome(const char const*s);

Cdlt,
0
overcode Messages postés 119 Date d'inscription jeudi 6 décembre 2007 Statut Membre Dernière intervention 21 octobre 2011 27
Modifié par overcode le 12/10/2010 à 19:05
Pour le premier point :
Oui, qui peut le plus peut le moins, voire le pire. C'est pour cela que le compilateur te générera un joli warning.

Imagine un peu un fonction de copie à laquelle tu passes des paramètres du genre :
copie_chaine("hello","world") ; 

Même si c'est admis, à l'exécution tu auras de belles surprises (chez moi le programme s'arrête net sans rien afficher comme message d'erreur).

Pour le second point :
Le deuxième const est totalement inutile. s est un pointeur local à la fonction palindrome. C'est une copie du pointeur passé en argument lors de l'appel. Le deuxième const n'aura comme conséquence que d'interdire les algorithmes qui usent de la syntaxe s++ s-- et autres ...

J'espère avoir éclairci un peu les choses :)
0
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 100
12 oct. 2010 à 19:07
ok ok merci pour l'explication du const,

pour la 2eme question ... j'ai simplement dû taper de travers ;-)
0
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 100
12 oct. 2010 à 18:01
rah! le point virgule derrière le if je suis limite honteux !

je n'avait pas pensé au if (... != ...) c'est bien plus efficace ! et je commence a mieux appréhender les chaines de caractère ( et leurs \0 final qui me donne un peux de mal ... )

je passe en résolu et un grand merci pour tout ;-)
0
strato-boy Messages postés 764 Date d'inscription mercredi 11 février 2009 Statut Membre Dernière intervention 19 janvier 2011 100
12 oct. 2010 à 12:41
pour le type bool j'utilise
#include <stdbool.h>

mon prof' d'algo en avait parler, donc je pense que c'est utilisable ... ( après je suis pas un pro non plus (je suis 1er année de DUT info avec des bases relativement bonne en C ), si il y a des inconvénient a utiliser cette bibliothèque, je n'en ai aucune idée ...)

pour l'idée de la boucle avec une condition, c'est une excellente idée ! je n'y avais pas pensé !!

bref je vais essayer de mettre en oeuvres vos idées et je vous tiens au courant. merci bien ;-)
-1