Déterminer si une chaine de caractères est un palindrome

Bonjour à tous,
j'ai un exercice d'algorithme que j'ai résolu, il demande d'écrire un algorithme qui dit si la chaine est palindrome ou non, en utilisant une chaine de n caractères.
Je vous demande de corriger mes erreurs s'il vous plaît, j'ai énormément besoin de votre aide. Merci d'avance :)

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 30 31 32 33 34 35 36 37

Algorithme mot_palindrome; Var mot: chaine[n]; b: booléen; i, n: entier; Debut Ecrire("Veuillez introduire un mot de plus de 2 caractères: "); Repeter Lire(mot); Jusqu'à(longueur(mot)>2) b<-- vrai; n<-- longueur(mot); i<--1; Si(n mod 2 =0) alors debut Tant que ((b=vrai) et (n<>i+1)) faire // <> veut dire =/= (different) debut Si(mot[i]=mot[n]) alors b<-- vrai; Sinon b<-- faux; i <-- i+1; n <-- n-1; fait; fin; Sinon debut Tant que((b<--vrai) et (n<>i))faire debut Si(mot[i]=mot[n]) alors b<--vrai; Sinon b<-- faux; i <-- i+1; n <-- n-1; fait; fin; Si(b=vrai) alors Ecrire("Le mot introduit est palindrome"); Sinon Ecrire ("Le mot introduit n'est pas palindrome"); FIN.

---

Pourquoi distinguer 2 cas, nombre de lettres pair ou impair ?

Bonjour :coucou:

Tu n'as besoin de parcourir que la moitié du mot.

Bonsoir, merci à vous deux pour votre réponse,

Trap D, j'ai pensé à la parité du nombre de lettres composant le mot, comme j'ai besoin de deux conditions d'arrêt pour les variables (i et n), voici un exemple de déroulement:
Si le nombre de caractères du mot est paire : exemple le mot 'haut'
au début i=1 et n=4 (n étant la longueur du mot=4) on vérifie si h=t, la 2ème étape: i=2 et n=3 on vérifie encore si a=u puis on sort de la boucle, j'ai pensé à ce que l'incrémentation de i et n s'arrête ici, car si on continue on aura ça : i=3 et n=2 le système va comparer si u=a ce qui serait inutile car il a déjà passé par cette comparaison.
Dans le cas où le nombre de caractères est impaire, exemple pour le mot 'bas'
i=1 et n=3 , on vérifie si b=s. 2ème étape i=n=2 on vérifie si a=a, et on s'arrête ici, on sort de la boucle, et on arrête l'incrémentation afin que le système ne refait pas la comparaison qu'il a déjà fait.. Autrement dit, si i=3 et n=1 on retombe sur la première comparaison: s=b qu'on es pas censé refaire.
Je ne vois pas comment écrire l'algorithme avec une seule boucle, pourriez vous me l'écrire afin que je comprenne mieux ? Merci.


Flodelarab, oui en effet, c'est ce que j'ai fait dans la boucle tant que, dans la 1ère Tant que ((b=vrai) et (n<>i+1) dans la 2ème Tant que((b<--vrai) et (n<>i)), mon exemple que j'ai écrit en dessus explique ma façon de parcourir la chaine.

Soit N le nombre de lettres du mot. Il ne bouge pas ! Contrairement à ton n.
Soit i un indice.

La lettre à la i^ème place est la même qu'à la (n-i+1)^ème place, quelque soit la parité de N.

i parcourt les nombres de 1 à N/2 quelque soit la parité et le signe "/" étant la division entière:
6/2=3
5/2=2
4/2=2
Dans un mot de 5 lettres, la lettre centrale n'a pas à être testée puisqu'elle est forcément bonne.

Tu n'as pas besoin de plusieurs boucles, ni d'étudier la parité, ni de dépasser N/2.

Simplifie ton algorithme.

L'algorithme est une simple boucle tant que avec deux conditions et des incrementations.

On peut écrire

Code:

---

1 2 3 4 5 6 7 8 9 10 11

debut initialisation des indices tant que condition_1 et conditions_2 faire (in/de)cremetation des indices fin tant que si condtion alors c'est un palindrome sinon ce n'est pas un palindrome fin si fin

---

A toi de trouver ce qu'il faut ettre à certains endroits ! :mouarf:

PS je trouve plus simple d'utiliser 2 indices plutôt qu'un seul, question de goût.

salut

sur le net il existe une multitude d'algorithme pour les palindrome

ma préférer étant celle-ci

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Fonction Palindrome(T: tab[1..n]: caractère): booléen; Var i, j: entier; résultat: booléen; Debut i := 1; j := longueur(Mot); résultat := Vrai; TantQue ((résultat = Vrai) Et (i < j)) Faire Si(T[i] = T[j]) Alors résultat = Vrai; i = i + 1; j = j - 1; Sinon résultat := Faux; FinSi FinTantQue Renvoyer résultat; Fin

---

tu la trouveras ici

Resultat = vrai est complètement inutile.

Citation:

---

Envoyé par Trap D

Resultat = vrai est complètement inutile.

---

Et aussi le fait d'aller au bout :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Fonction Palindrome(T: tab[1..n]: caractère): booléen; Var i, j: entier; Debut i := 1; j := longueur(Mot); TantQue ( i < j ) Faire Si(T[i] = T[j]) Alors i = i + 1; j = j - 1; Sinon Renvoyer Faux; FinSi FinTantQue Renvoyer Vrai; Fin

---

Moi je l'avais vu sur la forme :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Fonction Palindrome(T: tab[1..n]: caractère): booléen; Var i, j: entier; Debut i := 1; j := longueur(Mot); TantQue ( i < j ) et T[i] = T[j] Faire i = i + 1; j = j - 1; FinTantQue Renvoyer i >= j; Fin

---

Yep mais ceci est un peu..... difficile éventuellement à comprendre..

Code:

---

Renvoyer i >= j;

---

:D

Tu as raison, je suis trop influencé par le C :aie:

Bah

Suffit de l'écrire :

Code:

---

1 2	Si i >= j renvoie vrai sinon renvoie faux

---

et ça se comprend :D

Bonjour,
il y a là une orgie avec le même algo … mais on peut aussi imaginer d'autres approches (pas forcément des plus utiles ou utilisées ou adéquates) :

Une version récursive :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

fonction est_palindrome( chaine, longueur) : booleen début si longueur=0 ou 1 alors revoyer vrai sinon si premiere_lettre(chaine)=derniere_lettre(chaine) alors renvoyer est_palindrome(sous_chaine(chaine,2,longueur-2), longueur-2) sinon renvoyer faux fin si fin

---

Une version autre :

Code:

---

1 2 3 4 5 6 7 8 9 10

fonction est_palindrome( chaine ) : booleen début eniahc=renverser(chaine) si chaine=eniach alors renvoyer vrai sinon renvoyer faux fin si fin

---

...

Citation:

---

Envoyé par Trap D

Resultat = vrai est complètement inutile.

---

exact copier coller malheureux ^^
l'affectation ne sert a rien

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Fonction Palindrome(T: tab[1..n]: caractère): booléen; Var i, j: entier; Debut i := 1; j := longueur(Mot); TantQue ( i < j ) Faire Si(T[i] = T[j]) Alors i = i + 1; j = j - 1; Sinon Renvoyer Faux; FinSi FinTantQue Renvoyer Vrai; Fin

---

je ne suis pas d'accord avec ton écrit les conditions de sortie de boucle dans un algo sont importante
dans ton cas tu fait un mixte entre du pseudo code et du C si je l’écrit en pascal il ne marcheras pas a moins de lui adjoindre un exit après le renvoyer
pour moi un pseudo code ne doit en aucune présumer de quelque langage que ce soit et donc être le plus descriptif possible

Quite à donner des exemples d'algo, j'aime bien celui-là en Prolog :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

palindrome(X) :- phrase(palindrome,X).   palindrome --> % base case for even number of elements []. palindrome --> % base case for odd number of elements [A]. palindrome --> % general case: a palindrome is [A], % some element A... palindrome, % ... followed by a palindrome ... [A]. % ... followed by element A

---