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 ?

[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ï