Exercice #53 : Algorithme Palindrome - Moyen

Dans cet exercice nous allons écrire un algorithme permettant de vérifier si un mot est un palindrome. Je vous propose en fin d’article le programmes correspondant en JavaScript, PHP et C#.

Tentez de résoudre cet exercice par vous même. Vous trouverez la correction sous la présentation du sujet.

Le sujet

Ecrire un algorithme permettant à un utilisateur de saisir un mot afin de vérifier s’il est un palindrome.
Un message dédié s’affichera à l’écran, après la saisie, pour indiquer si le mot est un palindrome ou non
Pour traiter l’exercice, vous devez créer la fonction « estPalindrome » qui reçoit en paramètre une chaîne de caractères, et retourne la valeur vrai ou faux.
Pour rappel, un palindrome est un mot qui peut se lire de gauche à droite ou de droite à gauche.

Ci-dessous, deux exemples d’affichage produits par l’algorithme programmé et exécuté :

Revoir les boucles

Explications

Avant d’écrire l’algorithme attendu, considérons plusieurs mots pour bien comprendre ce qu’est un palindrome.

Exemple de palindrome :

Exemple de mots qui ne sont pas des palindromes :

L’algorithme écrit en pseudo-code :

Pour écrire l’algorithme attendu, je vais utiliser la stratégie montrée dans l’explication ci-dessus.

Je vais créer un nouveau mot, qui contiendra les mêmes lettres que le mot d’origine, en inversant leur ordre.

Cette stratégie n’est pas la meilleure et j’écrirai une version optimisée ensuite.

L’algorithme principal

Tout d’abord, je peux écrire l’algorithme principal qui est relativement simple.

Je demande à l’utilisateur de saisir un mot, puis j’appelle la fonction « estPalindrome » en lui transmettant celui-ci.

La fonction retournera la valeur VRAI ou FAUX si le mot est un palindrome ou non.

L’algorithme provoque l’affichage d’un message indiquant cette information à l’utilisateur.

Procéder de cette manière permet de « décomplexifier » l’exercice. En effet, je peux m’intéresser dans un second temps à la fonction estPalindrome, qui contient la logique la plus complexe de l’exercice. Mon algorithme principal est quant à lui terminé.

La fonction “estPalindrome”

A ce stade, je sais que la fonction « estPalindrome » doit recevoir en paramètre un mot et doit retourner une valeur booléenne.

Je commence par écrire sa signature :

Je vais appliquer la stratégie définie précédemment, et commencer par créer le mot inverse.

Pour cela je parcours le paramètre « mot » en sens inverse, à l’aide d’une boucle « POUR » et d’un compteur qui se décrémente de 1 en 1. Chaque lettre est placée à la suite dans la variable « motInverse ». En effet, puisqu’une chaine de caractères s’utilise comme un tableau, je peux accéder à la lettre depuis son indice.

A l’issue de cette étape, j’ai dans le paramètre « mot », le mot d’origine, et dans la variable « motInverse », le mot écrit avec les lettres inversées.

Je dois ensuite vérifier si le mot inversé correspond au mot d’origine. Si tel est le cas, cela indiquera que le mot est bien un palindrome. Je vais donc re-parcourir le paramètre « mot » et vérifier pour chaque lettre, si elle correspond à celle du mot inversé.

La vérification à écrire dans la boucle « POUR » est relativement simple. Je compare si la lettre du paramètre « mot » à l’indice « i », correspond à la lettre de la variable « motInverse » à l’indice « i ». Si ce n’est pas le cas, alors je peux directement arrêter le traitement de la fonction et retourner la valeur FAUX, car cela indiquera que le mot n’est pas un palindrome.

A contrario, si la boucle a parcouru tout le mot, et que le bloc « ALORS » du test n’a pas été mis en œuvre, cela indiquera que le mot est bien un palindrome, et la fonction pourra retourner la valeur « VRAI ».

Optimisation de la fonction

Cet algorithme est fonctionnel, mais n’est pas optimal. En effet, j’ai utilisé deux boucles « POUR » afin de parcourir le mot à vérifier, alors qu’il est possible de tout faire en une fois et sans utiliser la variable « motInverse ».

En utilisant les indices, je vais pouvoir vérifier les lettres comme le montre l’image ci-dessous, et avec l’exemple du mot radar :

Dans cet exemple, je dois vérifier :

si la lettre à l’indice 0 correspond à la lettre à l’indice 4 (c’est-à-dire la taille du mot – 1)
si la lettre à l’indice 1 correspond à la lettre à l’indice 3 (c’est-à-dire la taille du mot – 2)

Notez que la lettre à l’indice 2 n’a pas besoin d’être vérifiée car elle ne changera pas de place.

De plus, il est inutile de faire la même vérification dans l’autre sens, à savoir vérifier :

si la lettre à l’indice 3 correspond à la lettre à l’indice 1
si la lettre à l’indice 4 correspond à la lettre à l’indice 0

Avec ces explications, il est possible d’optimiser l’algorithme de cette manière :

La boucle parcours le mot de 1 en 1 jusqu’à sa moitié, et la vérification vérifie si la lettre à l’indice i, correspond à la lettre à l’indice taille du mot – 1 – indice i.

Aller à la liste de tous les exercices