Palindrome
Fermé
boutaina_F
-
Modifié par KX le 6/12/2015 à 21:28
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 8 janv. 2016 à 17:51
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 8 janv. 2016 à 17:51
1 réponse
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
Modifié par mamiemando le 8/01/2016 à 17:52
Modifié par mamiemando le 8/01/2016 à 17:52
Bonjour,
Ah c'est ce qu'on appelle une erreur d'étourderie :-)
Comment trouver ton erreur ?
Dans ce genre de situation, il ne faut pas hésiter à utiliser un debogueur (par exemple
Exemple :
Explication de l'erreur
Au moment où tu initialises
Il suffit dans ton programme d'initialiser
Améliorations possibles
Bon ensuite il y a quelque points améliorables pour ton programme. Notamment :
- les int devraient être des
- la fonction palyndrome devrait retourner un
- même si ce n'est pas gênant dans un fichier cpp, garde à l'esprit que
- on réserve généralement les noms en majuscule (par exemple ici T) aux constantes,
- le programme pourrait s'écrire en O(1) (en une passe) et sans appel récursif.
Intuitivement, il suffit de lire jusqu'au milieu du mot, et comparer le i-ème caractère avec le (n-1-i)-ème caractère. Dès qu'on observe une différence, on retourne
En effet, un appel récursif est plutôt "cher" d'un point de vue performance, car on empile des appels de fonctions, et pire, s'il y en a vraiment beaucoup, on peut provoquer un débordement de pile (ceci dit là il faudrait vraiment un texte extrêmement long !).
Bonne chance
Ah c'est ce qu'on appelle une erreur d'étourderie :-)
Comment trouver ton erreur ?
Dans ce genre de situation, il ne faut pas hésiter à utiliser un debogueur (par exemple
gdbsi tu es sous linux) ou à afficher les valeurs des variables à des endroits stratégiques du programme pour s'en sortir.
Exemple :
#include <iostream>
#include <string>
using namespace std;
int palindrome(string T, int a, int b)
{
std::cout << "T = " << T << " a = " << a << " b = " << b << std::endl;
if (a>=b)
{
return 1;
}
else if (T[a]!=T[b])
{
return 0;
}
else
{
return palindrome(T,a+1,b-1);
}
}
int main()
{
string tab;
int n=tab.size();
cout<< "donnez un mot ou une phrase"<<endl;
cin>>tab;
std::cout << "n = " << n << " n-1 = " << (n-1) << std::endl;
int q=palindrome(tab,0,n-1);
if (q)
{ cout<< "c'est un palindrome "<<endl;
}
else
{
cout<< "ce n'est pas un palindrom"<<endl;
}
return 0;
}
Explication de l'erreur
Au moment où tu initialises
n, la chaîne est vide, donc
nvaut 0. Le fait que la chaîne change par la suite n'a pas d'impact, car
nest un simple entier : il ne fait pas référence à la taille de la chaîne.
Il suffit dans ton programme d'initialiser
naprès avoir lu la chaîne.
cout << "donnez un mot ou une phrase" << endl;
cin >> tab;
int n = tab.size();
Améliorations possibles
Bon ensuite il y a quelque points améliorables pour ton programme. Notamment :
- les int devraient être des
std::size_t(entiers non signés),
- la fonction palyndrome devrait retourner un
bool
- même si ce n'est pas gênant dans un fichier cpp, garde à l'esprit que
using namespace std;ne doit jamais être utilisé dans un fichier hpp.
- on réserve généralement les noms en majuscule (par exemple ici T) aux constantes,
- le programme pourrait s'écrire en O(1) (en une passe) et sans appel récursif.
Intuitivement, il suffit de lire jusqu'au milieu du mot, et comparer le i-ème caractère avec le (n-1-i)-ème caractère. Dès qu'on observe une différence, on retourne
false. Si on n'a observé aucune différence, on retourne
true.
En effet, un appel récursif est plutôt "cher" d'un point de vue performance, car on empile des appels de fonctions, et pire, s'il y en a vraiment beaucoup, on peut provoquer un débordement de pile (ceci dit là il faudrait vraiment un texte extrêmement long !).
Bonne chance