Palindrome

Des mots tels que "radar", "sos" sont des palindromes: on peut les lire dans les deux sens.

def estPalindrome(mot):
    """
    mot -- chaîne de caractères

    renvoie True si mot est un palindrome, False sinon.
    """

    gauche, droite = 0, len(mot)-1
    reponse = 1

    while gauche <= droite:
        if mot[gauche] == mot[droite]:
            gauche = gauche + 1
            droite = droite - 1
        else:
            reponse = 0
            break
    return reponse == 1

Note

L'instruction break fait sortir de la boucle dès qu'elle est exécutée.

• Est-ce que droite est un variant de la boucle?

Réponse

Non. droite prend des valeurs entières décroissantes, mais non strictement décroissantes (cas où l'on exécute else dans le test). La variable pourrait donc, a priori, prendre une infinité de fois une même valeur: elle ne peut garantir la terminaison.

• Montrer que la boucle termine en établissant que d = droite -gauche + reponse est un variant de la boucle.

Une résolution

Soit d = droite -gauche + reponse

• d prend des valeurs entières (car gauche et droite sont initialisés à des valeurs entières ainsi que reponse puis subissent des opérations les laissant entiers).

• d prend des valeurs positives dans la boucle (car on n'entre dans la boucle que lorsque droite ≥ gauche, et reponse est positif ou nul).

• A chaque tour de boucle:

  • soit reponse passe de 1 à 0 (et on sort de la boucle) et dans ce cas d décroît strictement.
  • soit gauche augmente strictement (donc -gauche décroît strictement) et droite décroît strictement, donc d = droite + (-gauche) décroît strictement.

d est donc un variant de boucle.

On a explicité un variant de boucle donc la boucle termine.

Remarque.

On peut allèger légèrement ce code ainsi:

def estPalindrome(mot):
    """
    mot -- chaîne de caractères

    renvoi -- True si mot est un palindrome, False sinon.
    """

    gauche, droite = 0, len(mot)-1

    while gauche <= droite:
        if mot[gauche] == mot[droite]:
            gauche = gauche + 1
            droite = droite - 1
        else:
            return False
    return True