Algorithme de test d’un palindrome
Plan de tutoriel
1- Principe de l'algorithme
2- Algorithme de test d’un palindrome
3- Programme Python
Principe de l'algorithme
Cet algorithme permet de déterminer si une chaîne de caractères est un palindrome.
Un palindrome est une chaîne qui se lit de la même manière de gauche à droite et de droite à gauche. Par exemple, « radar » est un palindrome.
Dans un premier temps, l’algorithme demande à l’utilisateur de saisir une chaîne de caractères grâce à la fonction saisie(). La chaîne saisie est ensuite transmise à la fonction test_palindrome() afin de vérifier sa propriété de palindrome.
Pour effectuer le test, l’algorithme utilise deux indices : i représente la position du premier caractère et j représente la position du dernier caractère. Les deux caractères situés aux extrémités de la chaîne sont comparés. La méthode upper() permet de convertir les caractères en majuscules afin que la comparaison ne dépende pas des différences entre majuscules et minuscules.
Si les caractères comparés sont identiques, l’indice i avance d’une position et l’indice j recule d’une position. Le processus continue ainsi progressivement vers le centre de la chaîne.
Dès que deux caractères différents sont rencontrés, la chaîne n’est pas un palindrome. Si toutes les comparaisons sont identiques jusqu’au centre, la chaîne est considérée comme un palindrome.
Enfin, le programme principal affiche « ch est palindrome » lorsque le test est positif, sinon il affiche « ch est non palindrome ».
Algorithme de test d’un palindrome
Algorithme du programme Principal
Le rôle de l’algorithme principal Palindrome est de déterminer si une chaîne de caractères saisie par l’utilisateur est un palindrome.
Il commence par appeler la fonction saisie() afin de récupérer la chaîne ch. Ensuite, il appelle la fonction test_palindrome(ch) qui vérifie si la chaîne se lit de la même manière de gauche à droite et de droite à gauche.
Selon le résultat du test, l’algorithme affiche « ch est palindrome » si la chaîne est un palindrome. Sinon, il affiche « ch est non palindrome ».
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Algorithme Palindrome Debut # Appeler la fonction saisie() pour demander # et récupérer la chaîne saisie par l'utilisateur. ch <-- saisie() # Appeler la fonction test_palindrome(ch) # pour vérifier si la chaîne est un palindrome. Si test_palindrome(ch) alors # Afficher un message si la chaîne est un palindrome. Ecrire("ch est palindrome") Sinon # Afficher un message si la chaîne n'est pas un palindrome. Ecrire("ch est non palindrome") Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne des caractères |
La fonction saisie
La fonction saisie() permet de demander à l’utilisateur de saisir une chaîne de caractères, puis de retourner cette chaîne au programme principal.
|
1 2 3 4 5 6 7 8 |
Fonction saisie():chaine # Demander à l'utilisateur de saisir une chaîne # de caractères. Ecrire('Donner une chaine des caractères : ') Lire(ch) # Retourner la chaîne saisie. retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne des caractères |
La fonction test_palindrome
Le rôle de la fonction test_palindrome(ch) est de vérifier si une chaîne de caractères est un palindrome et de retourner une valeur booléenne : Vrai si elle est un palindrome et Faux dans le cas contraire.
La fonction utilise deux indices : i, placé au début de la chaîne, et j, placé à la fin. Elle compare les caractères situés aux deux extrémités, après les avoir convertis en majuscules avec Majus() afin de ne pas tenir compte de la différence entre majuscules et minuscules.
Tant que les caractères comparés sont identiques et que les indices i et j ne se sont pas croisés, i avance vers le centre tandis que j recule vers le centre. Cette opération permet de vérifier progressivement les caractères symétriques de la chaîne.
À la fin, la fonction compare les caractères restants et retourne Vrai si la chaîne est un palindrome, sinon Faux.
|
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 |
Fonction test_palindrome(ch:chaîne):booléen Début # Initialiser i à 0. # i représente l'indice du premier caractère # de la chaîne. i <-- 0 # Initialiser j au dernier indice de la chaîne. # len(ch) donne le nombre de caractères. # Comme les indices commencent à 0, le dernier indice est long(ch)-1. j <-- long(ch) - 1 # Comparer les caractères situés aux deux extrémités # de la chaîne. # Majus() permet de transformer les caractères # en majuscules afin de ne pas tenir compte # de la différence entre majuscules et minuscules. # # La condition i < j permet de poursuivre la comparaison # tant que les deux indices ne se sont pas croisés. Tant que (Majus(ch[i]) = Majus(ch[j]) et (i < j) faire # Avancer i vers le centre de la chaîne. i <-- i + 1 # Reculer j vers le centre de la chaîne. j <-- j - 1 Fin tant que # Après la boucle, vérifier si les deux caractères # actuellement comparés sont identiques. # # Si c'est le cas, la chaîne est considérée # comme un palindrome. Retourner Majus(ch[i]) = Majus(ch[j]) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
Programme en Python
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
# ========================================================== # Fonction de saisie # ========================================================== def saisie(): # Demander à l'utilisateur de saisir une chaîne # de caractères. ch = input('Donner une chaine des caractères : ') # Retourner la chaîne saisie. return ch # ========================================================== # Fonction test_palindrome # ========================================================== def test_palindrome(ch): # Initialiser i à 0. # i représente l'indice du premier caractère # de la chaîne. i = 0 # Initialiser j au dernier indice de la chaîne. # len(ch) donne le nombre de caractères. # Comme les indices commencent à 0, le dernier indice # est len(ch)-1. j = len(ch) - 1 # Comparer les caractères situés aux deux extrémités # de la chaîne. # upper() permet de transformer les caractères # en majuscules afin de ne pas tenir compte # de la différence entre majuscules et minuscules. # # La condition i < j permet de poursuivre la comparaison # tant que les deux indices ne se sont pas croisés. while (ch[i].upper() == ch[j].upper()) and (i < j): # Avancer i vers le centre de la chaîne. i = i + 1 # Reculer j vers le centre de la chaîne. j = j - 1 # Après la boucle, vérifier si les deux caractères # actuellement comparés sont identiques. # # Si c'est le cas, la chaîne est considérée # comme un palindrome. return ch[i].upper() == ch[j].upper() # ========================================================== # Programme principal # ========================================================== # Appeler la fonction saisie() pour demander # et récupérer la chaîne saisie par l'utilisateur. ch = saisie() # Appeler la fonction test_palindrome(ch) # pour vérifier si la chaîne est un palindrome. if test_palindrome(ch): # Afficher un message si la chaîne est un palindrome. print("ch est palindrome") else: # Afficher un message si la chaîne n'est pas un palindrome. print("ch est non palindrome") |
Exécution du programme :
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
