Palindromes et anagrammes
« kayak », « radar », « ressasser » : ces mots se lisent pareil dans les deux sens. Ce sont des palindromes. Et « chien » et « niche » sont faits des mêmes lettres : ce sont des anagrammes. Deux jolis problèmes pour s'entraîner sur les textes.
Un mot palindrome
Le plus simple : comparer le mot à lui-même, retourné.
fonction estPalindrome(mot)
retourne mot = inverser(mot)
fin fonction
affiche estPalindrome('kayak') // vrai
affiche estPalindrome('radar') // vrai
affiche estPalindrome('bateau') // faux
inverser retourne le texte : « bateau » devient « uaetab », qui est différent.
La méthode à la main
Comment faire sans inverser ? On compare la première lettre avec la dernière, la deuxième avec l'avant-dernière, et ainsi de suite jusqu'au milieu. À la première différence, on sait que ce n'est pas un palindrome.
fonction estPalindrome(mot)
taille1 est un nombre vaut longueur(mot)
pour i de 1 à arrondi_inferieur(taille1 / 2)
si copier(mot, i, 1) <> copier(mot, taille1 - i + 1, 1) alors
retourne faux
fin si
fin pour
retourne vrai
fin fonction
affiche estPalindrome('ressasser') // vrai
affiche estPalindrome('ressasse') // faux
copier(mot, i, 1) est la lettre numéro i en partant du début (les textes commencent à 1).copier(mot, taille1 - i + 1, 1) est la lettre numéro i en partant de la fin.- Il suffit d'aller jusqu'à la moitié : au-delà, on referait les mêmes comparaisons.
Question : Pour vérifier un mot de 9 lettres, combien de comparaisons faut-il au maximum ? — 4. 9 / 2 = 4,5, arrondi à 4 : la lettre du milieu est seule, elle n'a pas besoin d'être comparée.
Une phrase palindrome
« Ésope reste ici et se repose » est un palindrome célèbre... à condition d'ignorer les espaces, les accents et les majuscules. Il faut donc nettoyer la phrase avant de la tester :
fonction nettoyer(phrase)
retourne minuscules(lettres(normaliser(phrase)))
fin fonction
fonction phrasePalindrome(phrase)
propre est un texte vaut nettoyer(phrase)
retourne propre = inverser(propre)
fin fonction
affiche nettoyer('Ésope reste ici et se repose')
affiche phrasePalindrome('Ésope reste ici et se repose') // vrai
affiche phrasePalindrome('La mariée ira mal') // vrai
affiche phrasePalindrome('Engage le jeu que je le gagne') // vrai
affiche phrasePalindrome('Bonjour tout le monde') // faux
Trois fonctions enchaînées, de l'intérieur vers l'extérieur :
normaliser retire les accents : « É » devient « E » ;lettres ne garde que les lettres : plus d'espaces ni de ponctuation ;minuscules met tout en minuscules.
La première ligne affiche esoperesteicietserepose.
Les nombres palindromes
121, 1331, 2002 : un nombre aussi peut être un palindrome. On le transforme en texte pour le tester.
total est un nombre vaut 0
ecriture est un texte
pour n de 1 à 1000
ecriture vaut convertir_texte(n)
si ecriture = inverser(ecriture) alors
total ajoute 1
fin si
fin pour
affiche 'Palindromes entre 1 et 1000 : ' + total // 108
Il y en a 108 : les 9 chiffres, 9 nombres à deux chiffres (11, 22... 99) et 90 nombres à trois chiffres (101, 111... 999).
Les anagrammes
Deux mots sont des anagrammes s'ils contiennent exactement les mêmes lettres, dans un ordre différent. L'astuce : si on trie les lettres de chaque mot, deux anagrammes donnent le même résultat.
fonction lettresTriees(mot)
liste est un tableau
pour i de 1 à longueur(mot)
liste ajoute copier(mot, i, 1)
fin pour
trier(liste)
retourne joindre(liste, '')
fin fonction
fonction sontAnagrammes(mot1, mot2)
retourne lettresTriees(mot1) = lettresTriees(mot2)
fin fonction
affiche lettresTriees('chien') // cehin
affiche lettresTriees('niche') // cehin
affiche sontAnagrammes('chien', 'niche') // vrai
affiche sontAnagrammes('marie', 'aimer') // vrai
affiche sontAnagrammes('lapin', 'sapin') // faux
On range chaque lettre dans un tableau, on trie le tableau, puis joindre recolle les lettres. « chien » et « niche » deviennent tous les deux cehin : c'est leur signature.
Transformer deux choses en une forme commune pour pouvoir les comparer est une technique très courante. Ici, la forme commune est « les lettres dans l'ordre alphabétique ».
En résumé
- Un palindrome est égal à son inverse :
mot = inverser(mot). - À la main, on compare les lettres deux à deux, des extrémités vers le milieu.
- Avant de tester une phrase, on la nettoie :
normaliser, lettres, minuscules. - Deux anagrammes ont les mêmes lettres une fois triées.
