Discussion :

[Geek-c0d3r]

Bonjour,
Je doit faire un algorithme qui vérifie si le mot est un palindrome ou non
Voila mon algo, si quelqu'un peut me dire c'est juste ou non, je suis pas encore un programmeur c'est pourquoi je sais pas comment tester mes travaux

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
T:Tableau[1..n]:Car
Var nl,i:Entier
Début
 Ecrire("Entrer le nombre des lettres dans le mot:")
 Lire(nl)
 Redim(T[nl])
 Pour i<--1 à nl Faire
  Lire(T[i])
 FinPour
 Pour i<--1 à nl Faire
  Si T[i]=T[nl] Alors
   nl<--nl-1
    Si i=nl OU nl=i+1 Alors
     Ecrire("Bravo! ce mot est un palindrome")
    FinSi
  Sinon
   Ecrire("Désolé, ce mot n'est pas un palindrome")
   i<--nl
  FinSi
 FinPour
Fin

un autre problème:
Je sais que normalement il ne faut pas demander a l'utilisateur de donner le nombre de lettres dans le mot, je sais pas comment faire (je suis un débutant ), dans mes recherches j'ai trouvé des fonctions prédéfinis tel que Len() et Mid() , est-ce que je peut les utilisés?

PS: désolé si vous trouvé des erreurs d'orthographe, je suis pas français =)

[PRomu@ld]

Je sais que normalement il ne faut pas demander a l'utilisateur de donner le nombre de lettres dans le mot, je sais pas comment faire (je suis un débutant ), dans mes recherches j'ai trouvé des fonctions prédéfinis tel que Len() et Mid() , est-ce que je peut les utilisés?

L'idée c'est que si tu cherches à faire un algo tu n'as pas à faire de telles considérations. Tu supposes deux choses. D'un coté tu as déjà la chaîne de caractère à tester et de l'autre tu as une fonction qui te renvoie la longueur de la chaîne de caractère.

Ensuite pour ce qui est de ta fonction, c'est typiquement quelque chose de récursif (c'est beaucoup plus simple à exprimer). Ensuite pour ce qui est de ta fonction, elle ne fonctionne visiblement pas lorsque tu n'as qu'un seul caractère dans la chaîne.

[droggo]

Foa,

Ensuite pour ce qui est de ta fonction, c'est typiquement quelque chose de récursif (c'est beaucoup plus simple à exprimer).

Je dirais plutôt que c'est typiquement un cas ou se passe très facilement de la récursivité.

[PRomu@ld]

Je dirais plutôt que c'est typiquement un cas ou se passe très facilement de la récursivité

J'ai pas saisi la remarque.

[droggo]

Bie,

J'ai pas saisi la remarque.

Dans ton message précédent, tu as écrit ce que je cite dans le mien, et tu y parles de "c'est typiquement quelque chose de récursif".

[PRomu@ld]

Et donc l'apport pour le PO ?

[droggo]

Boe,

Et donc l'apport pour le PO ?

Il me semble que c'est à toi que je répondais, non ?

Et pour le PO, je mettais en valeur le fait que ton affirmation est fausse.

[PRomu@ld]

Et pour le PO, je mettais en valeur le fait que ton affirmation est fausse.

Ok, il manquait un mot dans ton intervention. Je n'avais pas compris.

Par contre, je ne vois pas pourquoi particulièrement ici on peu se passer de récursivité.

Le problème est il me semble beaucoup plus simple à exprimer en récursif qu'en itératif : un mot est un palindrome si le premier et le dernier caractère sont identiques et que ce qui se trouve au milieu est aussi un palindrome. Ca donne surtout l'avantage de ne pas à avoir à gérer les indices (+1 -1) et ça évite donc l'erreur du PO dont je parlais.

[henderson]

Salut !

De toute façon on est obligé de borner que ce soit par indexes ou par pointeurs.
Mais il ne sert à rien de tester, s'il existe, le caractère central !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
début, fin
tant que début est plus petit que fin faire :
    si caractère de début est différent de caractère de fin retourner faux
    avancer début
    reculer fin
retourner vrai

A plus !

[gss3000]

Salut !
Voilà un bon algo qui teste si le mot est palindrome ou non ...

algo mot_palindrome

variables n,x,y : entier
mot : chaine

debut
ecrire("entrer un mot : ")
lire(mot)
n:=len(mot) //longueur de mot
x:=0
y:=1
pour i=1 à n/2
si milieu(mot,i,1)=milieu(mot,n-i+1,1) alors
x:=1
sinon
y:=0
finsi
finpour

si y:=0 alors
ecrire("Bravo! ce mot est un palindrome")
sinon
ecrire("Désolé, ce mot n'est pas un palindrome")
finsi
fin

AU REVOIR

[PRomu@ld]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Voilà un bon algo qui teste si le mot est palindrome ou non ...

. C'est quoi un bon algo ? Qu'est-ce que ça apporte pour le PO ?

Et en plus ton algo est faux, et ne respecte pas les valeurs de bon codage (variables claires, commentaires, ...)

Merci de ne répondre au PO que lorsque cela l'aide réellement. Si tout le monde poste son algo dans son coin, je ne suis pas certain que cela va aider Geek-c0d3r.

[Jedai]

En rapport avec le sujet, un défi avait été lancé sur la recherche du plus long palindrome dans un texte sur le forum des langages fonctionnels.

En Haskell, avec le type String normal :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
isPalindrome :: String -> Bool
isPalindrome str = str == reverse str

(Ne contient pas l'optimisation classique qui permet de vérifier seulement la moitié du mot.)

--
Jedaï

[lcfseth]

Le problème est il me semble beaucoup plus simple à exprimer en récursif qu'en itératif : un mot est un palindrome si le premier et le dernier caractère sont identiques et que ce qui se trouve au milieu est aussi un palindrome. Ca donne surtout l'avantage de ne pas à avoir à gérer les indices (+1 -1) et ça évite donc l'erreur du PO dont je parlais.

L'idée est bonne mais la méthode est mauvaise ( je dis pas fausse, puisqu'elle marche ). En fait suffit de faire exactement ce que tu dis, sauf qu'au lieu d'utiliser la recursivité, on va simplement la simuler.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
fonction isPalindrome 
entrée 
mot : chaine
sortie
estPalindrome : booleen
variable
debut : entier
longeur : entier
 
debut
  longeur := len(chaine)
  debut := 1
  estPalindrome := vrai
  tanque (longeur > 0) faire // tant que notre mot contient des lettres, il faut faire attention à ne pas faire (longeur != 0) car apres 1 la longeur passe à -1
 
  si chaine[debut] != chaine[longeur - debut + 1]  alors // on remarquera que si longeur = 1 alors on aura chaine[1] != chaine[1] :) pas de probleme donc
     estPalindrome := faux
     longeur := 0 // permet de sortir de la boucle
  sinon
    // Ici on retrouve les même parametre que nous allions passé à notre fonciton recursive :)
     debut := debut +1  // début++ normale
     longeur := longeur - 2 // la longeur diminue par 2
  fin si
 
  fintantque
 
  retourner estPalindrome
fin isPalindrome

Question : une chaine vide est elle un Palindrome?

[henderson]

Salut !

estPalindrome := faux
longeur := 0 // permet de sortir de la boucle

Sauf qu'il y a plus simple et plus économique (on n'a pas à tester ce que l'on sait déjà).
Ici, je ne m'occupe que de l'algorithme (SANS PRENDRE DE PRECAUTIONS) :
C'est juste l'implémentation en C de ce que j'ai décrit dans une précédente intervention.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
bool Palindrome(char *Debut)
{
char *Fin = Debut + strlen(Debut) - 1;
while(Debut < Fin)
    {
    if(*Debut != *Fin) return false;
    Debut++;
    Fin--;
    }
return true;
}

A plus !

[Jedai]

L'idée est bonne mais la méthode est mauvaise ( je dis pas fausse, puisqu'elle marche ). En fait suffit de faire exactement ce que tu dis, sauf qu'au lieu d'utiliser la recursivité, on va simplement la simuler.

Tu m'explique en quoi simuler la récursivité est mieux que de l'utiliser, sachant qu'il s'agit ici d'une récursivité terminale et donc optimisée par tous les compilateurs décents ?

Voyons en Haskell, supposant que ton palindrome soit stocké dans une ByteString donc une structure où l'accès direct est en O(1) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
isPalindrome :: ByteString -> Bool
isPalindrome bs
  | length bs < 2 = True
  | otherwise = head bs == last bs && isPalindrome (middle bs)
 
middle :: ByteString -> ByteString
middle = tail . init

--
Jedaï

[PRomu@ld]

Tu m'explique en quoi simuler la récursivité est mieux que de l'utiliser,

+1, je suis aussi preneur de cette réponse.

Question : une chaine vide est elle un Palindrome?

Oui, un palindrome est un élément (nombre ou chaîne) que l'on peut lire dans les deux sens. Le mot vide se lit dans les deux sens donc c'est un palindrome.

[pseudocode]

Oui, un palindrome est un élément (nombre ou chaîne) que l'on peut lire dans les deux sens. Le mot vide se lit dans les deux sens donc c'est un palindrome.

Mathématiquement oui. Mais je ne suis pas bien sur qu'une chaine vide soit considérée comme un "mot" ou un "nombre" dans la vie courante.

[PRomu@ld]

Mais je ne suis pas bien sur qu'une chaine vide soit considérée comme un "mot" ou un "nombre" dans la vie courante.

En même temps tu te sers souvent des palindromes dans la "vie courante" ?

[JeitEmgie]

+1, je suis aussi preneur de cette réponse.



Oui, un palindrome est un élément (nombre ou chaîne) que l'on peut lire dans les deux sens. Le mot vide se lit dans les deux sens donc c'est un palindrome.

la notion de "mot" != la notion de "chaîne de caractères"…

…non sequitur…

un "mot" n'étant pas une chaîne vide la question ne se pose pas…

… le sens commun de "mot" c'est : "objet" d'un "vocabulaire"…
cela exclut le vide …

maintenant, décider ce qu'une fonction de test de palindrome doit renvoyer si on lui passe une chaîne vide, cela relève d'une convention contextuelle plus qu'autre chose…
et d'un peu de bon sens : qu'est-ce que le fait de renvoyer "vrai" apportera comme réponse intéressante dans la suite des opérations qui dépendent du test…
(et notamment : est-ce la suite est "empty save" ? …)

[Jerome Briot]

En même temps tu te sers souvent des palindromes dans la "vie courante" ?

N O N