[C] fonction detecte palindrome
Résolu
strato-boy
Messages postés
769
Date d'inscription
Statut
Membre
Dernière intervention
-
strato-boy Messages postés 769 Date d'inscription Statut Membre Dernière intervention -
strato-boy Messages postés 769 Date d'inscription Statut Membre Dernière intervention -
A voir également:
- Algorithme palindrome en c
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 pdf - Forum Programmation
7 réponses
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,
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,
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 ;-)
On attend ton nouvel algorithme ;-)
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 :
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.
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.
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
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.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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 :
au lieu de :
En plus de la plus démoniaque des erreurs, celle responsable de mes quelques cheveux blancs :D, regarde bien ici :
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.
N'hésite pas si tu as d'autres questions :)
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 :)
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
le passage en constante est-il vraiment important ?
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 ?
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 :
- 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 *
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 *
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,
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,
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 :
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 :)
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 :)
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 ;-)
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 ;-)
pour le type bool j'utilise
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 ;-)
#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 ;-)
