Exercice - LAMSADE

Informatique
UV21
Exercices corrigés sur les boucles Exercice 1 Proposer un algorithme permettant de tester si une chaîne de caractères
(contenue dans une variable s) est un palindrome. Le résultat (vrai/faux)
sera stocké dans une variable booléenne b.
Un palindrome est une chaîne de caractères qui se lit de la même manière de
gauche à droite et de droite à gauche. Par exemple, "kayak" est un
palindrome mais "baobab" n'en est pas un.
Correction : Analyse : on est donc amené à comparer les lettres d'un mot. Pour "baobab"
par exemple, nous comparons la première et la 6eme (et dernière), puis la
2eme et la 5eme, puis la 3eme et la 4eme. Le mot est un palindrome si pour
toutes les comparaisons on a la même lettre, ce qui n'est pas le cas pour
"baobab".
Plus généralement, notons n la longueur (le nombre de lettres) du mot. Il
s'agit donc de comparer les lettres de position 1 et n, puis 2 et n-1, puis
3 et n-2, etc. Autrement dit, il s'agit de comparer les lettres de position
i et n+1-i pour i=1,2,3,... Question : où faut-il s'arrêter ? Il suffit de s'arrêter « au milieu » du
mot. Pour "baobab", qui contient 6 lettres, on s'arrête pour i=3
(comparaison des lettres 3 et 6+1-3=4). Pour "kayak" (de longueur impaire),
on s'arrête pour i=2 (comparaison des lettres 2 et 4). Il est donc inutile
de comparer quand i dépasse (strictement) n/2. Solution 1 : boucle pour Première variante (la plus naturelle) : on initialise b à vrai, et on le
met à faux si l'on trouve une position où le test ne marche pas (le mot
n'est pas un palindrome). Deuxième variante (ça marche aussi...) : on compte le nombre de tests qui
sont justes. Si tous les tests sont justes on met b à vrai, sinon b vaut
faux. Il y a [pic] tests (iquo(n,2) en Maple) - attention à ne pas se
tromper avec les cas n pair et n impair... |Variante 1 | |Variante 2 |
|b:=true: | |c:=0: |
|n:=length(s): | |n:=length(s): |
|for i from 1 to n/2 do | |for i from 1 to n/2 do |
|if s[i]s[n+1-i] then | |if s[i]=s[n+1-i] then |
|b:=false: | |c:=c+1: |
|fi: | |fi: |
|od: | |od: |
|print("La réponse est",b); | |if c=iquo(n,2) then |
| | |b:=true |
| | |else b:=false: |
| | |fi : |
| | |print("La réponse est",b); | Remarques :
- on peut faire une boucle de 1 à n (au lieu de n/2), cela marcherait
tout aussi bien (en changeant le test en conséquence dans la variante
2). Simplement, on ferait des tests inutiles car on ferait chaque test
2 fois.
- Dès que l'on a trouvé un test faux, il est inutile de continuer (le
mot n'est pas un palindrome). On pourrait rajouter une instruction
break: après b:=false: (version 1). Cette instruction fait « sortir »
de la boucle. Là encore, cela économise des tests inutiles. Erreur classique à éviter : Le programme suivant ne fonctionne pas. |b:=true: |
|n:=length(s): |
|for i from 1 to n/2 do |
|if s[i]s[n+1-i] then |
|b:=false: |
|else b:=true: |
|fi: |
|od: |
|print("La réponse est",b); | En effet, si le test est vrai, il ne faut pas remettre b à vrai ! Si b
était déjà vrai, ça ne change rien, mais si b était faux, cela signifie
qu'un test avait montré que le mot n'est pas un palindrome, b doit rester
faux !
Exemple d'exécution avec "rosser". Avant la boucle, b vaut vrai. Quand i=1,
on compare les lettres de position 1 et 6, le test est faux et b vaut vrai.
Quand i=2, on compare "o" et "e" donc b devient faux. Quand i=3, on compare
"s" et "s" donc b redevient vrai !
Solution 2 : boucle tant que Il est également possible d'utiliser non pas une boucle pour mais une
boucle tant que. Voici les deux variantes transformées en boucle tant que. |Variante 1 | |Variante 2 |
|b:=true: | |c:=0: |
|n:=length(s): | |n:=length(s): |
|i:=1: | |i:=1: |
|while i