algorithme palindrome

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:

---

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 :roll:), 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 =)

Citation:

---

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.

Foa,

Citation:

---

Envoyé par PRomu@ld

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

Citation:

---

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. :koi:

Bie,

Citation:

---

Envoyé par PRomu@ld

J'ai pas saisi la remarque. :koi:

---

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". :)

Et donc l'apport pour le PO ?

Boe,

Citation:

---

Envoyé par PRomu@ld

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.

Citation:

---

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.

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:

---

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 !

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

Citation:

---

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

Code:

---

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

---

:koi:. 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.

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:

---

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ï

Citation:

---

Envoyé par PRomu@ld

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:

---

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?

Salut !

Citation:

---

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:

---

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 !

Citation:

---

Envoyé par lcfseth

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:

---

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ï

Citation:

---

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

---

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

Citation:

---

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.

Citation:

---

Envoyé par PRomu@ld

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. :P

Citation:

---

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" ? :aie:

Citation:

---

Envoyé par PRomu@ld

+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" ? …)

Citation:

---

Envoyé par PRomu@ld

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

---

N O N

:dehors:

Citation:

---

Envoyé par PRomu@ld

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

---

Engage le jeu, que je le gagne ! ;)

Citation:

---

Envoyé par JeitEmgie

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

---

Dans quel contexte ?

Citation:

---

Envoyé par JeitEmgie

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 …

---

J'ai l'impression que tu joues sur les mots rien que pour le plaisir de jouer sur les mots. ;)

J'utilise mot dans le sens élément d'un ensemble de test, jamais dans un sens français/conjugaison/grammaire/vocabulaire/... . C'est le genre de définition ce que tu peux trouver en théorie de la compilation (l'ensemble vide est un mot).

Citation:

---

Envoyé par Dut

N O N

---

Ca me rassure. ;)

Citation:

---

Envoyé par PRomu@ld

Dans quel contexte ?



J'ai l'impression que tu joues sur les mots rien que pour le plaisir de jouer sur les mots. ;)

J'utilise mot dans le sens élément d'un ensemble de test, jamais dans un sens français/conjugaison/grammaire/vocabulaire/... . C'est le genre de définition ce que tu peux trouver en théorie de la compilation (l'ensemble vide est un mot).



Ca me rassure. ;)

---

même en théorie des langages l'ensemble vide n'est pas un mot…
ce n'est pas parce qu'un texte vide est considéré comme syntaxiquement correct dans beaucoup de langages que la notion de "mot vide" a un sens au niveau lexicographique…

Citation:

---

même en théorie des langages l'ensemble vide n'est pas un mot…

---

Il ne faudrait pas confondre mot vide et ensemble vide.

Citation:

---

Envoyé par PRomu@ld

Il ne faudrait pas confondre mot vide et ensemble vide.

---

l'ensemble vide n'est pas un mot, un mot n'est pas une chaîne vide.

Citation:

---

l'ensemble vide n'est pas un mot,

---

On est d'accord.

Citation:

---

un mot n'est pas une chaîne vide.

---

Chaîne vide = mot vide . C'est un élément appartenant aux langages rationnels (si tu omets les espaces, les palindromes sont un sous ensemble des langages rationnels).

Citation:

---

Envoyé par PRomu@ld

On est d'accord.



Chaîne vide = mot vide . C'est un élément appartenant aux langages rationnels (si tu omets les espaces, les palindromes sont un sous ensemble des langages rationnels).

---

les palindromes un langage ou ensemble de langages per se ?