184. Écrivez une fonction **puissance()** qui prend en paramètre deux entiers *n* et *p* et qui renvoie *n* élevé à la puissance *p*, soit $n^p$, en utilisant uniquement l'opérateur de multiplication.

```python
>>> puissance(3, 0) == 1
True
>>> puissance(4, 1) == 4
True
>>> puissance(1, 5) == 1
True
>>> puissance(2, 3) == 8
True
```

## Comptages

185. Écrivez une fonction qui compte le nombre de caractères d'une chaîne, sans utiliser la fonction Python `len()` :

```python
def nombre_charactères(s):
    """
    Renvoie le nombre de caractères d'une chaîne donnée, sans utiliser
    la fonction prédéfinie len().
    Paramètre : s - chaîne de caractères
    Valeur de retour : entier - le nombre de caractères de s
    Contrainte : aucune
    Exemples :
    >>> nombre_charactères("Test") == 4
    True
    >>> nombre_charactères("Un autre test. ") == 15
    True
    >>> nombre_charactères('') == 0
    True
    """
```

186. Écrivez une fonction qui compte le nombre d'espaces présents dans une chaîne de caractères :

```python
def nombre_espaces(s):
    """
    Renvoie le nombre d'espaces présents dans une chaîne donnée
    Paramètre : s - chaîne de caractères
    Valeur de retour : entier - le nombre d'espaces
    Contrainte : aucune
    Exemples :
    >>> nombre_espaces("Test") == 0
    True
    >>> nombre_espaces("Un autre test. ") == 3
    True
    >>> nombre_espaces('') == 0
    True
    """
```

187. Écrivez une fonction qui compte le nombre de signes de ponctuation suivants : “.”, “?”, “!” dans une chaîne :

```python
def nombre_ponctuations(s):
    """
    Renvoie le nombre de caractères ".", "?", "!" présents dans une chaîne donnée
    Paramètre : s - chaîne de caractères
    Valeur de retour : entier - le nombre de caractères ".", "?", "!"
    Contrainte : aucune
    Exemples :
    >>> nombre_ponctuations("Test.") == 1
    True
    >>> nombre_ponctuations("Un autre test ! Pour voir.") == 2
    True
    """
```
>>> nombre_ponctuations('') == 0
True
"""

188. Écrivez une fonction qui compte le nombre d'occurrences d'un caractère donné dans une chaîne de caractères :

def occurrences_caractere(s, carac):
"""
Renvoie le nombre d'occurrence d'un caractère donné dans une chaîne
Paramètres :
- s : chaîne de caractères
- carac : chaîne de (un) caractère
Valeur de retour : entier - le nombre d'occurrences de carac dans s
Contrainte : len(carac) == 1
Exemples :
>>> occurrences_caractere("Test.", 't') == 1
True
>>> occurrences_caractere("Un autre test ! Pour voir.", 't') == 3
True
>>> occurrences_caractere('', 't') == 0
True
"""
# Exercices niveau intermédiaire

## Accumulation

### Suite

189. Écrivez une fonction `terme Suite()` qui prend en paramètre un entier positif `n` et qui renvoie la valeur du terme $u_n$ de la suite définie par

$$ \begin{cases} u_0 = 1 \\ \forall n \ge 1, \quad u_n = 2u_{n-1} + 3 \end{cases} $$

Exemples :

```
>>> terme Suite(0) == 1
True
>>> terme Suite(1) == 5
True
>>> terme Suite(2) == 13
True
```

*(On procédera avec une boucle `for`, sans utiliser la formule de calcul du terme général d'une suite arithmétique-géométrique.)*

## Table de multiplications

190. Définissez une fonction `chaîne_multiplier()` paramétrée par 2 entiers `a` et `b` et qui renvoie la chaîne de la forme « *a* x *b* = *c* », où *c* est le résultat de la multiplication, comme dans l'exemple ci-dessous.

```
>>> chaîne_multiplier(6, 7) == '6 x 7 = 42'
True
```

191. Définissez une fonction `table_multiplier()` paramétrée par un entier `n` et renvoyant une chaîne contenant la table de multiplications de *n* entre 0 et 10, présentée comme ci-dessous.

```
>>> table_multiplier(3) == '0 x 3 = 0 | 1 x 3 = 3 | 2 x 3 = 6 | 3 x 3 = 9 | 4 x 3 = 12 | 5 x 3 = 15 | ...'
True
```

## Boucles imbriquées

### Chaîne des paires

Nous souhaitons produire une chaîne de caractères pour écrire toutes les paires d'un itérable donné.

192. Proposez une fonction préliminaire `paire2str()` :

```
def paire2str(a, b):
    """Renvoie une écriture de la paire {a, b}
    Paramètres :
        a, b : entiers - composantes de la paire
        Valeur de retour : str - l'écriture de la paire
    Contraintes : aucune
    Exemples :
        >>> paire2str(2, 2)
```
'{2,2}'
>>> paire2str(2, 6)
' {2,6}'
"""

193. Proposez une fonction `les_paires()` qui renvoie une chaîne de caractères contentant l'ensemble des paires d'entiers compris entre 1 et une valeur *n* donnée en paramètre. Cet ensemble de paires inclut les paires dont les deux composantes sont égales. Par exemple :

>>> les_paires(2)
' {1,1} {1,2} {2,2} '
>>> les_paires(4)
' {1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4} '

Une seconde version pourra éviter de produire un caractère espace en fin de chaîne :

>>> les_paires(2)
' {1,1} {1,2} {2,2} '
>>> les_paires(4)
' {1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4} '

## Affichage de motifs

194. Écrivez une procédure `affiche_ligne()` qui prend en paramètre un entier *n* positif et qui affiche à l'écran une séquence de caractères `0` de taille *n*. Cette procédure ne doit pas utiliser l'opérateur `*` et s'écrit à l'aide d'une seule boucle, voir l'exemple ci-dessous.

>>> affiche_ligne(5)
00000
>>> affiche_ligne(3)
000

195. Écrivez une première version d'une procédure `affiche_bloc()` qui prend en paramètre un entier *n* positif et qui affiche à l'écran un bloc de *n* lignes composées de *n* caractères `0`, comme dans l'exemple ci-dessous. Cette version doit utiliser la procédure `affiche_ligne()`.

>>> affiche_bloc(3)
000
000
000

196. Écrivez une deuxième version d'une procédure `affiche_bloc()` qui utilise deux boucles imbriquées.

197. De même, écrivez deux versions d'une procédure `afficheTriangle()` qui produit l'affichage suivant :

>>> afficheTriangle(3)
0
00
000

198. Écrivez une fonction `affiche_diagonale()` qui met un `X` sur la diagonale du bloc et un `0` dans le reste du bloc, voir l'exemple ci-dessous.

>>> affiche_diagonale(3)
X00
0X0
00X
# Exercices niveau confirmé

Version provisoire qui sera complétée

## Accumulation

### Majuscules

199. Proposez une fonction `en_majuscules()` qui transforme les caractères d'une chaîne de caractères qui sont des lettres minuscules en majuscule. Les autres caractères restent inchangés. On utilisera la fonction Python prédéfinie `upper()` qui renvoie la lettre majuscule correspondant à une lettre minuscule :

```python
>>> 'k'.upper()
K
>>> en_majuscules('des kakis et des kiwis')
'DES KAKIS ET DES KIWIS'
>>> en_majuscules('des kakis et des kiwis !')
'DES KAKIS ET DES KIWIS !'
>>> en_majuscules('des Kakis et des Kiwis')
'DES KAKIS ET DES KIWIS'
>>> en_majuscules('')
''
```

200. Proposez une fonction `en_capitale()` qui remplace dans une chaîne passée en paramètre

* la première lettre, et

* chacune des lettres précédées d'une espace

par la lettre majuscule correspondante :

```python
>>> en_capitale('des kakis et des kiwis')
'Des Kakis Et Des Kiwis'
>>> en_capitale('Des Kakis Et Des Kiwis')
'Des Kakis Et Des Kiwis'
>>> en_capitale('DES KAKIS ET DES KIWIS')
'DES KAKIS ET DES KIWIS'
>>> en_capitale('')
''
```

### Chaîne miroir

201. Proposez une fonction `miroir()` qui produit le miroir d'une chaîne de caractères :

```python
>>> miroir('Python')
'nohtyP'
>>> miroir('super')
'repus'
>>> miroir('')
''
```

### Anacyclique et palindrome

Un *anacyclique* est un mot ou un groupe de mots qui conserve un sens lorsqu'on le lit de droite à gauche
Par exemple, « zen » et « nez » ou « super » et « repus » sont anacycliques. C'est aussi le cas de « l'ami naturel » et « le rut animal » si l'on ne tient pas compte des caractères qui ne sont pas des lettres.

Dans le cas général, le texte est différent selon que l'on lit dans le sens normal de lecture ou en sens inverse.
Lorsque le texte est identique, il s'agit d'un *palindrome*.

Par exemple, « été » et « kayak » sont des palindromes. C'est aussi le cas de la phrase « Engage le jeu que je le gagne. ».

(source : page Wikipédia « Anacyclique » fr.wikipedia.org/wiki/Anacyclique. Consultez cette page pour découvrir d'autres anacycliques.)

On dira que deux mots ou groupes de mots sont *frères anacycliques* s'ils forment un couple d'anacycliques, lecture l'un de l'autre de droite à gauche.

L'objectif de l'exercice est de déterminer si deux chaînes de caractères données sont frères anacycliques. Donc de proposer un prédicat **anacycliques()** :

>>> anacycliques('zen', 'nez')

True

>>> anacycliques("l'ami naturel", 'le rut animal')

True

Une première version pourra être « stricte » et tenir compte de tous les caractères, sans distinguer lettres et autres caractères.

Une version standard pourra procéder par étape : supprimer l'ensemble des caractères qui ne sont pas des lettres avant de réaliser la comparaison des chaînes.

Une version avancée pourra ne pas tenir compte des signes diacritiques (accents, trémas, cédilles) et ainsi confondre « e », « é », et « ê », ou « c » et « ç ».

## Annexe

On pourra utiliser la primitive `isalpha()` pour déterminer si un caractère est une lettre :

>>> 'e'.isalpha()

True

>>> 'E'.isalpha()

True

>>> '3'.isalpha()

False

>>> '!'.isalpha()

False

>>> 'é'.isalpha()

True
# Exercices complémentaires

Une fiche d'exercices indépendants de la progression habituelle débutant / intermédiaire / confirmé.

Au menu :

1. découverte de la tortue et du module `turtle` de Python

2. dessiner des carrés, dessiner avec des carrés

3. dessiner avec des ordres (L-Systèmes)

## Dessiner avec le module `turtle`

La tortue désigne un robot virtuel capable de se déplacer dans un plan en laissant une trace ou non de son passage. Elle a été inventée dans les années 1960 au MIT par Seymour Papert qui a conçu un langage informatique – Logo – et une philosophie de l'éducation (voir la page Wikipédia « Logo (langage) » fr.wikipedia.org/wiki/Logo_(langage)).

De nombreux langages informatiques ont repris cette idée de tortue. Le module `turtle` met en œuvre une telle tortue.

On utilise les fonctions du module après un `import turtle`.

Il est possible de commander le paramétrage du crayon par :

* `turtle.down()` qui abaisse le stylo

* `turtle.up()` qui relève le stylo

* `turtle.pencolor(color)` qui change la couleur (`'red'`, `'green'`, `'blue'`, etc.)

On déplace la tortue avec :

* `turtle(forward(length))` qui avance d'un nombre de pas donné;

* `turtle backward(length)` qui recule;

* `turtle.right(angle)` qui tourne vers la droite d'un angle donné (en degrés);

* `turtle.left(angle)` qui tourne vers la gauche.

On peut également déplacer la tortue à un point donné ou modifier son orientation avec :

* `turtleopher(x, y)` qui déplace la tortue jusqu'au point `(x, y)`;

* `turtle.setheading(angle)` qui oriente la tortue à l'angle donné en degrés, le 0° étant à l'est, le 90° au nord, etc.

La fenêtre par défaut est 950 pixels en largeur et 800 pixels en hauteur. Le point (0,0) est au centre de l'écran. Au départ, la tortue est en (0,0), orientée à 0°.

D'autres fonctionnalités sont disponibles, on consultera éventuellement la documentation docs.python.org/fr/3/library/turtle.

La majorité des primitives fournies par le module `turtle` sont des procédures. Elles ne renvoient pas de valeur. Elles modifient l'état du « système », le « système » étant compris comme la fenêtre dans laquelle évolue la tortue, et l'état étant compris comme ce qui est dessiné sur cette fenêtre, la position de la tortue, son orientation, etc.

Voici un exemple :

```python
import turtle

def spiral(n):
    turtle.pencolor("red")
```
```python
for i in range(n):
    turtle(forward(i * 10)
          turtle.right(144))
```

Essayez :
>>> spiral(20)

<figure><img src="image_13.png" /></figure>

## Dessiner avec des carrés

202. Proposez une procédure `carre()` qui dessine un carré dont la longueur des côtés est fournie en paramètre. Ce carré sera dessiné depuis l'état courant de la tortue. À la fin du dessin l'état de la tortue sera identique à son état initial.

203. Proposez une procédure `cinq_carres()` qui dessine cinq carrés emboîtés ayant comme sommet commun la position initiale de la tortue. Les longueurs des carrés sont comprises entre 10 à 50 (inclus). Les longueurs de chacun des carrés varient de 10 en 10.

Vous pouvez également proposer une variante `cinquante_carres()` qui dessine cinquante carrés de longueurs comprises entre 10 et 500 inclus. C'est plus joli, mais il est plus difficile de vérifier qu'il y a bien 50 carrés dessinés.

<figure><img src="image_14.png" /></figure>

204. Proposez une procédure `dix_carres()` qui dessine dix carrés de côtés 50 espacés de 5 comme sur la figure. Vous pouvez proposer une variante qui accepte en paramètre la longueur des carrés.

<figure><img src="image_15.png" /></figure>

Remarquez qu'à l'issue de l'exécution de la procédure, la tortue se trouve à la base du dernier carré dessiné.

205. Proposez une procédure `cent_carres()` qui dessine dix lignes de dix carrés comme sur la figure.
<figure><img src="image_16.png" /></figure>

206. Proposez une procédure `carres_tournants()` qui dessine *n* carrés de côté 100 pivotant autour d'une sommet commun pour faire un tour complet. L'angle entre deux carrés successifs est donc de $360 \div n$ degrés. Cette procédure est paramétrée par le nombre de carrés à dessiner.

Voici le résultat pour 3, 7, et 9 carrés.

<figure><img src="image_17.png" /></figure>

207. Proposez une procédure `carres_emboites()` qui dessine de manière répétée un certain nombre de carrés emboités comme dans la figure ci-dessous (exemple pour 9 carrés). Cette procédure admet un paramètre, la longueur du carré le plus grand. Le dessin peut se faire en dessinant les carrés depuis le plus grand jusqu'au plus petit. La taille de deux carrés successifs est alors dans un rapport de $\sqrt{2}$.

<figure><img src="image_18.png" /></figure>

## Dessiner avec des ordres

On souhaite donner une séquence d'ordres à la tortue sous forme d'une chaîne de caractères.

Étant donnés

* une longueur *l*

* un angle $\alpha$ exprimé exprimé en degrés

La tortue interprètera chacun des caractères de la chaîne comme une commande à effectuer :

<table><thead><tr><th>caractère</th><th>ordre</th></tr></thead><tbody><tr><td>'F'</td><td>avancer de <i>l</i></td></tr><tr><td>'G'</td><td>avancer de <i>l</i> (identique à 'F')</td></tr><tr><td>'+'</td><td>tourne vers la gauche de <i>α</i></td></tr><tr><td>'-'</td><td>tourne vers la droite de <i>α</i></td></tr></tbody></table>

Par exemple, la chaîne de caractères `'+F-F--F-F'` pour des valeurs de $l = 100$ et $\alpha = 45$ permettrait de tracer une « maison ».

## Dessiner un ordre

208. Proposez une procédure `dessine()` qui prend en paramètres :

* une chaîne de caractères, séquence d'ordres
* une longueur,

* un angle,

et réalise à l'aide la tortue le tracé correspondant aux ordres.

Testez cette procédure sur l'exemple précédent.

209. Proposez des procédures utilisant un unique appel à `dessine()` et réalisant le tracé

* d'un carré

* d'un hexagone régulier

Chacune de ces procédures accepte un paramètre correspondant à la longueur de la figure à tracer.

210. Proposez une procédure généralisant les précédentes pour dessiner un polygone régulier. Cette procédure acceptera un paramètre entier indiquant le nombre de côtés, et un paramètre correspondant à la longueur de la figure à tracer.

211. Proposez une procédure qui trace l'ensemble des polygones réguliers entre deux nombres de côtés *min* et *max* donnés en paramètre. Par exemple

```python
>>> dessine_des_poygones(3, 12, 100):
```

produira le dessin suivant

<figure><img src="image_19.png" /></figure>

## Dériver un ordre

Dériver un ordre consiste à remplacer chacun des caractères 'F' d'un ordre donné par une autre chaîne de caractères.

Par exemple, la dérivation de `F+F` par `F-F` produit `F-F+F-F`.

212. Proposez une fonction `derive()` qui accepte deux chaînes en paramètres, et renvoie la dérivation de la première par la seconde.

Il est possible de dériver plusieurs fois de suite un ordre par une autre chaîne de caractères. On obtient alors la dérivation *n*-ième de l'ordre par la chaîne.

Par exemple les dérivations successives de 'F' par '+F-' produisent :

```python
>>> derive_nieme('F', '+FF', 1)
'+FF'
>>> derive_nieme('F', '+FF', 2)
'++FF+FF'
>>> derive_nieme('F', '+FF', 3)
'+++FF+FF++FF+FF'
```

213. Proposez une fonction `derive_nieme()` qui accepte deux chaînes et un entier *n* en paramètres, et renvoie la dérivation *n*-ième de la première chaîne par la seconde.
<figure><img src="image_20.png" /></figure>

Pour dessiner les figures suivantes, utilisez la fonction `speed()` du module `turtle` pour accélerer le déplacement de la tortue.

214. Proposez une fonction `koch()` qui accepte un paramètre entier $n$ et dessine les dérivations $n$-ième de `F` par `F+F-F-F+F` pour $n$ variant de 1 à 4, et pour une longueur de 4 et un angle de 90°.

215. Proposez une fonction `flocons()` qui accepte un paramètre entier $n$ et dessine les dérivations $n$-ième de `F--F--F` par `F+F--F+F` pour une longueur de 40 et un angle de 60°.

216. Proposez une fonction pour tracer les dérivations $n$-ième, pour $n$ compris entre 0 et 5, une longueur $l = 3^{5-n}$ et un angle $\alpha = 60$ de la séquence d'ordres `F--F--F` par la chaîne `F+F--F+F`.

Consultez la page Wikipédia « L-Système » fr.wikipedia.org/wiki/L-Système pour découvrir d'autres fractales à dessiner.
7. Chaînes de caractères
# Rappels sur les chaînes de caractères

## Coup d'œil

On révise:

* ce qu'est une chaîne de caractères

* les opérateurs applicables aux chaînes

* les fonctions et méthodes liées aux chaînes

## Chaînes de caractères

Les chaînes de caractères sont des séquences de caractères et sont donc des itérables. Les caractères sont des symboles qui peuvent être écrits, que ce soit des lettres, des chiffres, des symboles de ponctuation ou des lettres d'autres alphabets.

La chaîne vide ne contient aucun caractère.

Chaîne de caractères se dit *string* en anglais, et le type Python associé est *str*.

## Itération sur les chaînes

La boucle *for* permet la répétition d'un bloc d'instructions sur chaque caractère d'une chaîne.

Le code ci-dessous compte le nombre de lettres minuscules d'une chaîne *s* à l'aide de la variable *compteur*.

```python
compteur = 0
for c in s:
    if c.islower():
        compteur = compteur + 1
```

## Caractères spéciaux

Une chaîne de caractères littérale s'écrit entre délimiteurs, ' ou ".

Certains caractères ne peuvent pas être écrits tels quels, par exemple les délimiteurs eux-mêmes.

On utilise alors le caractère d'échappement \ (contre-barre ou anti-slash) avant le caractère spécial.

La table suivante présente quelques exemples de caractères spéciaux :

<table><thead><tr><th>écriture</th><th>caractère</th><th>exemple de chaîne</th><th>écriture Python</th></tr></thead><tbody><tr><td>\"</td><td>guillemet</td><td>Des "guillemets".</td><td>"Des \"guillemets\"."</td></tr><tr><td>\'</td><td>apostrophe</td><td>Des 'apostrophes'.</td><td>'Des \'apostrophes\'.'</td></tr><tr><td>\n</td><td>passage à la ligne</td><td>Ligne 1<br>Ligne 2</td><td>"Ligne 1\nLigne 2"</td></tr><tr><td>\t</td><td>tabulation</td><td>Avant Après</td><td>"Avant\tAprès"</td></tr><tr><td>\\</td><td>contre-barre</td><td>2 contre-barres \ et \</td><td>"2 contre-barres \\ et \\"</td></tr></tbody></table>

Remarquez que l'écriture Python donnée en dernière colonne n'est qu'une des écritures possibles (et pas toujours la plus simple).
# Opérateurs applicables aux chaînes

## Concaténation

L'opérateur `+` concatène deux chaînes : il produit une nouvelle chaîne composée des deux chaînes mises bout à bout.

```
>>> s1 = "Je commence. "
>>> s2 = "Tu finis."
>>> s1 + s2
'Je commence. Tu finis.'
```

## Répétition

L'opérateur `*` appliqué à un entier $n$ et une chaîne répète la chaîne $n$ fois.

```
>>> s1 = "Ah ! "
>>> s1 * 3
'Ah ! Ah ! Ah ! '
```

## Égalité entre chaînes

Deux chaînes de caractères sont égales si et seulement si elles contiennent exactement les mêmes caractères, dans le même ordre.

Les lettres minuscules et majuscules sont distinctes.

```
>>> 'test' == 'Test'
False
>>> "C'est cool !" == 'C\'est cool !'
True
>>> 'Ah ! Ah ! Ah ! ' != 3 * "Ah ! "
False
```

## Fonctions et méthodes liées aux chaînes

Le tableau ci-dessous reprend les fonctions et méthodes prédéfinies liées aux chaînes de caractères déjà rencontrées :

<table><thead><tr><th>nom</th><th>exemple d'expression</th><th>valeur de l'expression</th></tr></thead><tbody><tr><td>len()</td><td>len("Test")</td><td>4</td></tr><tr><td>str()</td><td>str(3.1416)</td><td>'3.1416'</td></tr><tr><td>int()</td><td>int("12")</td><td>12</td></tr><tr><td>float()</td><td>float('3.1416')</td><td>3.1416</td></tr><tr><td rowspan="2">str.islower()</td><td>"Test".islower()</td><td>False</td></tr><tr><td>"test".islower()</td><td>True</td></tr><tr><td rowspan="2">str.isupper()</td><td>"Test".isupper()</td><td>False</td></tr><tr><td>"TEST".isupper()</td><td>True</td></tr><tr><td rowspan="2">str.isdigit()</td><td>"Test".isdigit()</td><td>False</td></tr><tr><td>"12".isdigit()</td><td>True</td></tr></tbody></table>

Pour plus d'informations sur ces fonctions et pour en découvrir d'autres, vous pouvez consulter la documentation du langage Python : docs.python.org/fr/3/library/stdtypes.html?#string-methods.

## Memento

* une chaîne de caractères est une séquence de caractères et donc un itérable

* les opérateurs `+` et `*` sont utilisés pour concaténer ou répéter des chaînes de caractères

* les opérateurs `==` et `!=` sont utilisés pour comparer les chaînes

* Python propose de nombreuses fonctions et méthodes prédéfinies pour manipuler les chaînes
# Indices pour les chaînes de caractères

## Coup d'œil

On découvre :

* comment accéder à un caractère donné d'une chaîne

* une nouvelle façon de parcourir une chaîne à l'aide de boucles `for`

* comment accéder à une sous-chaîne

## Accès à un caractère d'une chaîne

Une chaîne est une séquence ordonnée de caractères.

Chacun des caractères peut être désigné par sa place dans la séquence à l'aide d'un **indice**.

On parle aussi d'**index**.

L'accès à un caractère se réalise simplement en faisant suivre la chaîne par l'indice du caractère entre crochets.

Par exemple :

```python
>>> s = "Informatique"
>>> s[2]
'f'
```

Remarquez que l'indice 2 ne correspond pas au second mais au troisième caractère.

En effet, les caractères d'une chaîne sont indicés **à partir de zéro** (et non à partir de un).

L'indice du dernier caractère de la chaîne est donc égal à la longueur de la chaîne moins un. Par exemple avec la chaîne `s` définie précédemment :

```python
>>> s[len(s) - 1]
'e'
```

Attention, toute tentative d'accès à un caractère en dehors de la chaîne, se traduit par une `IndexError`, erreur d'indice, indice en dehors de l'intervalle :

```python
>>> s[12]
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
IndexError: string index out of range
```

## Itération sur les indices

Les indices des caractères d'une chaîne sont donc compris entre 0 inclus, et la longueur de la chaîne, exclue.

Une boucle `for` parcourant cet intervalle va permettre d'accéder successivement aux caractères de la chaîne.

Par exemple :

```python
s = "Test"
for i in range(len(s)):
    print("----------------")
    print(i, "\t", s[i])
print("================")
```

L'affichage obtenu est le suivant :
0 T
1 e
2 s
3 t
================

L'itération sur les indices permet de parcourir différemment les chaînes, par exemple en allant à l'envers :

```python
s = "Test"
for i in range(len(s)-1, -1, -1):
    print("--------------------")
    print(i, "\t", s[i])
print("==================")
```

qui affiche

3 t
2 s
1 e
0 T
================

ou uniquement les caractères d'indice pair :

```python
s = "Test"
for i in range(0, len(s), 2):
    print("--------------------")
    print(i, "\t", s[i])
print("==================")
```

qui affiche

0 T
2 s
================

## Autres indiçages

L'accès à un caractère d'une chaîne par indiçage est une opération courante dans la plus part des langages de programmation.

Python propose d'autres indiçages.

### Accès à une sous-chaîne

Une **tranche** d'une chaîne de caractères est une séquence de caractères consécutifs de la chaîne.

Les indices d'une tranche forment un intervalle : de l'indice du premier caractère (inclus) à l'indice du dernier caractère (exclu).

L'accès à une tranche se fait en écrivant cet intervalle entre crochets, comme par exemple :

```python
>>> s = "Informatique"
>>> s[0:4]
'Info'
```

La valeur d'une telle expression est une chaîne de caractères, sous-chaîne de la chaîne accédée.
## Accès avec un indice négatif

Python autorise l'individage des caractères d'une chaîne à parti de la fin de chaîne.
Ces indiçages se font avec des valeurs d'indice négatives.

L'indice -1 est utilisé pour désigner le dernier caractère, l'indice -2 pour désigner l'avant dernier, ainsi de suite jusqu'à la valeur de `-len(chaîne)` pour désigner le premier caractère.

Exemple :

```python
>>> s = "Informatique"
>>> s[-1]
'e'
>>> s[-2]
'u'
>>> s[-len(s)]
'I'
```

## Memento

* l'accès à un caractère d'une chaîne se fait via son indice, noté entre crochets

* les indices vont de 0 inclus à `len(chaine)` exclu

* l'itération sur une chaîne peut se faire via ses indices

* l'accès à une tranche d'une chaîne se fait par un indiçage par un intervalle

* l'individage à partir de la fin de chaîne se fait avec des valeurs d'indices négatives
Dans ce jeu de caractères ASCII, les caractères de code compris entre 0 et 31, et le caractère de code 127 sont appelés caractères *de contrôle*.

On y trouve par exemple :

* le caractère de code ASCII 9 : la tabulation, abrégé `ht` pour *horizontal tab*, et noté `\t` dans les chaînes de caractères

* le caractère de code ASCII 10 : le retour à la ligne, abrégé `nl` pour newline, et noté `\n` dans les chaînes de caractères

Les autres caractères, de code compris entre 32 et 126 sont les caractères dits *imprimables*.

On y trouve par exemple :

* le caractère de code ASCII 32 : l'espace, abrégé `sp`

* des caractères de ponctuations et d'autres symboles divers

* les 10 chiffres, de 0 de code 48, à 9 de code 57

* les 26 lettres de l'alphabet latin en version majuscules, de `A` de code 65, à `Z` de code 90

* les 26 lettres de l'alphabet latin en version minuscule, de `a` de code 97, à `z` de code 122

## Autres codes, ISO 8859 et Unicode

Le code ASCII défini au début des années 1960 est limité. Ce code d'abord américain ne permet pas de représenter les lettres accentuées ou les lettres d'al alphabets non latins.

Plusieurs extensions ont été proposées au fil des années pour prendre en compte une nécessaire internationalisation

* dans années 1985 les standards de la famille ISO 8859, comme le ISO 8859-1 – souvent appelée Latin-1 – qui intègre les lettres accentuées des langues de l'Europe occidentale

* à partir de 1990, le standard **Unicode** qui réunit en un même code l'ensemble des alphabets latin, cyrillique, grec, arabe, etc.

Unicode est actuellement dans sa neuvième version. Ce code recense 128.172 caractères, et attribue à chacun d'eux un nom et un numéro.

L'**UTF-8** est la méthode standard la plus connue pour le codage des caractères selon la norme Unicode. Elle est utilisée par la très grande majorité des pages web, et sur les systèmes GNU/Linux.

Il est essentiel de noter que ces codes ISO ou Unicode sont des **extensions du code ASCII** : ils reprennent les 127 codes ASCII et ajoutent d'autres caractères pour les codes supérieurs à 127.

## Fonctions `ord()` et `chr()`

En Python, il est possible de consulter la table de codage des caractères, et en particulier la table ASCII, via les deux fonctions prédéfinies `ord()` et `chr()` :

* pour un caractère donné, `ord()` renvoie son code

* pour un code donné, `chr()` renvoie le caractère correspondant

Par exemple :

```python
>>> chr(9)
'\t'
>>> ord('\n')
10
>>> ord('0')
48
>>> chr(65)
'A'
```

## Ordre des caractères, comparaison de caractères

Un code comme l'ASCII définit un **ordre** sur les caractères : le caractère `0` de code 48 est inférieur au caractère `A` de code 65.

Cet ordre est utilisé par les opérateurs de comparaison Python `<`, `<=`, `<>`, `>=`, et `>:` appliqués aux caractères :
>>> 'O' < 'A'

True

Les comparaisons de caractères qui ont le plus de sens sont celles comparant deux lettres minuscules ou deux lettres majuscules entre elles, l'ordre alphabétique (celui du dictionnaire) est alors respecté :

>>> 'a' <= 'e'

True

>>> 'A' <= 'E'

True

Par contre, toutes les lettres majuscules ont un code inférieur à toute lettre minuscule. Les comparaisons entre minuscules et majuscules sont donc de peu d'intérêt :

>>> 'a' <= 'A'

False

>>> 'E' <= 'a'

True

## Comparaison de chaînes de caractères

### Ordre lexicographique

L'ordre alphabétique permet d'ordonner les lettres et, par extension, les mots entre eux.

Pour ordonner des chaînes quelconques qui peuvent contenir des caractères autres que des lettres, il faut étendre l'ordre alphabétique. On parle d'**ordre lexicographique**.

L'ordre sur les caractères défini par le codage des caractères, par exemple ASCII, est ainsi étendu aux chaînes de caractères.

### Comparaison de chaînes

En Python, les opérateurs de comparaison `<`, `<=`, `>`, et `>=` sont aussi utilisés pour comparer des chaînes de caractères.

La comparaison de deux chaînes procède ainsi :

* les chaînes sont comparées caractère par caractère, de gauche à droite

* le premier caractère de la première chaîne est comparé au premier caractère de la seconde chaîne, le second avec le second, etc.

* dès qu'un caractère est supérieur à un autre, la chaîne qui le contient est dite supérieure à l'autre et la comparaison s'arrête.

Lors de la comparaison de deux chaînes de différentes longueurs, la plus courte des deux peut être supérieure à l'autre. Par exemple :

>>> "Programme" < "Python"

True

parce que 'r' < 'y'.

### Lien avec l'ordre alphabétique

L'ordre sur les caractères et les chaînes de caractères ne respecte pas l'ordre alphabétique traditionnel :

* en raison de l'ordre défini entre les lettres majuscules et les lettres minuscules,

* en raison de l'ordre défini sur les lettres accentuées et autres signes.

Pour éviter les situations telles

>>> "programmation" < "programme"

True

>>> "programmation" < "Programme"

False

ou
>>> 'e' < 'i'

True

>>> 'é' < 'i'

False

ou encore

>>> "porte" < "porter"

True

>>> "porté" < "porter"

False

et

>>> "portemine" < "porte-savon"

False

>>> "portée" < "porte-savon"

False

On se limitera par exemple aux comparaisons de mots composés uniquement de lettres minuscules non accentuées, ou uniquement de lettres majuscules non accentuées.

## Memento

* la table du code ASCII définit un code entier pour nos caractères les plus courants, mais pas les lettres accentuées

* la comparaison des caractères est basée sur ce code

* la comparaison de minuscules et majuscules est trompeuse

* l'ordre lexicographique étend à tous les caractères l'ordre alphabétique habituel

* les opérateurs Python de comparaison de chaînes <, <= et autres sont à manier avec précaution
# Non mutabilité des chaînes de caractères

## Coup d'œil

On découvre :

* la notion de mutabilité

* comment modifier une chaîne à une position donnée

* comment modifier un caractère donné dans une chaîne

## Mutabilité

Nous avons vu précédemment que les séquences sont des collections ordonnées d'éléments. Elles sont un cas particulier d'itérables car il existe des itérables non ordonnés, tels que les dictionnaires ou les ensembles que nous découvrirons plus tard.

Parmi les séquences, nous connaissons les intervalles (range) et les chaînes de caractères. Ces deux itérables ne sont pas mutables, c'est-à-dire que l'on ne peut pas en modifier les valeurs.

Il est logique de ne pas pouvoir modifier un élément d'un intervalle. Sinon, on modifierait la définition même de cet intervalle. En Python, contrairement à d'autres langages de programmation, on ne peut pas non plus modifier un caractère individuel d'une chaîne. En d'autres termes, on ne peut pas affecter une nouvelle valeur à un caractère donné d'une chaîne.

```python
>>> s = "Informatique"
>>> s[0] = 'i'
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
TypeError: 'str' object does not support item assignment
```

Le seul moyen de modifier une variable de type `str` est de créer une nouvelle variable qui reprend le contenu de l'ancienne, aux modifications près. Cette variable peut avoir le même nom que l'ancienne.

## Modification d'une chaîne à une position donnée

Il s'agit de créer une nouvelle chaîne qui est la modification d'une chaîne à une position connue à l'avance.

## Ajout de caractères

L'ajout d'un ou plusieurs caractères en début ou fin de chaîne se fait à l'aide d'une concaténation entre la chaîne d'origine `s` et les caractères à ajouter, placés devant ou derrière `s`.

```python
>>> s = "ordinaire"
>>> prefixe = "extra"
>>> s = prefixe + s
>>> s
'extraordinaire'
>>> s = s + " !"
```
```
>>> s
'extraordinaire !'
```

L'ajout d'un ou plusieurs caractères à une position connue d'une chaîne se fait en découpant la chaîne de part et d'autre de la position d'insertion et en concatenant les sous-chaînes obtenues avec les caractères à ajouter, dans le bon ordre.

```
>>> s = "Il fait beau."
>>> s[0:4] + "ais" + s[4(len(s))]
'Il faisait beau.'
```

## Suppression de caractères

La suppression d'un ou plusieurs caractères à des positions données d'une chaîne se fait en concatenant les sous-chaînes que l'on veut conserver.

```
>>> s = 'Il faisait beau.'
>>> s[0:6] + s[9(len(s))]
'Il fait beau.'
```

## Remplacement de caractères

La remplacement de caractères revient à faire en même temps une suppression et un ajout.

```
>>> s = "Il fait beau."
>>> s[0:8] + "froid" + s[-1(len(s))]
'Il fait froid.'
```

## Modification de caractères donnés d'une chaîne

Dans cette partie, la position des caractères à modifier n'est pas connue. Seuls les caractères à modifier le sont. Il est donc nécessaire de parcourir la chaîne afin de localiser les caractères à modifier.

Une nouvelle variable est initialisée vide avant l'entrée dans une boucle `for`. Cette boucle parcourt la valeur de la chaîne à modifier caractère par caractère et l'affecte à l'identificateur de boucle. Si le caractère pointé par l'identificateur est le caractère à modifier, la modification est répercutée dans la nouvelle variable. Sinon, ce caractère est ajouté à la nouvelle variable.

### Ajout de caractères

L'exemple suivant illustre l'ajout systématique d'un ou plusieurs caractères avant et/ou après un caractère donné dans une chaîne. La fonction `entoure_espaces()` crée une nouvelle chaîne dans laquelle le caractère `*` est ajouté avant et après les espaces présents dans la chaîne passée en paramètre. Une nouvelle variable, `res`, est initialisée vide. Une boucle parcourt la valeur de `s` caractère par caractère et l'affecte à l'identificateur `carac`. Si le caractère pointé est une espace, `*` est ajouté avant et après `carac` et le tout est concatené à `res`, sinon `carac` est concatené seul à `res`.

```python
def entoure_espaces(s):
    """
    s (str) -> s avec les espaces entourés de *
    Contrainte : aucune
    Exemples
    >>> entoure_espaces("valeur de la chaîne") == 'valeur* *de* *la* *chaîne'
    True
    >>> entoure_espaces("test") == "test"
    True
    >>> entoure_espaces("  ") == '* * * *'
    True
    """
    res = ""
    for carac in s:
        if carac == ' ':
            res = res + '*' + carac + '*'
        else:
```
```python
res = res + carac
return res
```

## Suppression de caractères

L'exemple suivant illustre la suppression systématique d'un caractère donné dans une chaîne. La fonction `supprime_espaces()` crée une nouvelle chaîne dans laquelle tous les espaces sont supprimés de la chaîne s passée en paramètre. De la même manière, une boucle `for` parcourt la valeur de s caractère par caractère. Si `carac` n'est pas une espace, il est concatené à `res`, sinon l'espace ne l'est pas. Ainsi, seuls les caractères autres que des espaces sont présents dans `res`.

```python
def supprime_espaces(s):
    """
    s (str) -> s sans espace
    Contrainte : aucune
    Exemples
    >>> supprime_espaces("valeur de la chaîne") == 'valeurdechaîne'
    True
    >>> supprime_espaces("test") == "test"
    True
    >>> supprime_espaces(" ") == ''
    True
    """
    res = ""
    for carac in s:
        if carac != ' ':
            res = res + carac
    return res
```

## Modification de caractères

L'exemple suivant illustre la modification systématique d'un caractère donné dans une chaîne. Cette modification consiste à créer une nouvelle chaîne dans laquelle tous les espaces sont remplacés par le caractère `_`. La chaîne à modifier, s est passée en paramètre de la fonction `remplace_espaces()`. Dans la boucle parcourant s, si le caractère pointé est une espace, le caractère `_` est concatené à `res`, sinon c'est `carac`. Ainsi, les espaces sont remplacés par `_`.

```python
def remplace_espaces(s):
    """
    s (str) -> s avec les espaces remplacés par _
    Contrainte : aucune
    Exemples
    >>> remplace_espaces("valeur de la chaîne") == 'valeur_de_la_chaîne'
    True
    >>> remplace_espaces("test") == 'test'
    True
    >>> remplace_espaces(" ") == '__'
    True
    """
    res = ""
    for carac in s:
        if carac == ' ':
            res = res + '__'
        else:
            res = res + carac
    return res
```
Memento

* On ne peut pas modifier un élément d'une séquence non mutable

* `range()` et `str` sont non mutables

* pour modifier une chaîne à une position donnée, il est conseillé d'utiliser les sous-chaînes

* pour modifier des caractères donnés d'une chaîne, il est conseillé de parcourir la chaîne à l'aide d'une boucle `for` est de construire la chaîne modifiée à partir des caractères de la chaîne d'origine
# Exercices niveau débutant

## Indiçage

217. N'utilisez pas tout de suite l'interpréteur Python et anticipez les valeurs des expressions ci-dessous. Ensuite, vérifiez la validité de votre réponse en utilisant l'interpréteur.

```python
s = "Bonjour"
s[1]
s[len(s)]
s[-1]
s[0:3]
s[3:1len(s)-1]
```

## Ordre lexicographique

218. Aidez-vous de la tables de caractères ASCII donnée en cours pour classer toutes les chaînes suivantes dans l'ordre croissant.

'Bonjour' 'bonjour' 'bonjour' 'Bonjour.' 'Bonjour !' '@univ' '1' '11' '100' '[10]' '{10}' '(10)'

219. Écrivez une fonction maximum() prenant en paramètre deux chaînes de caractères et renvoyant la plus grande de ces 2 chaînes.

220. Écrivez une fonction minimum() prenant en paramètre deux chaînes de caractères et renvoyant la plus petite de ces 2 chaînes.

221. Est-ce que le code de ces fonctions diffère de celui que vous avez écrit pour comparer des entiers dans les exercices sur les instructions conditionnelles ? Que pouvez-vous en déduire sur les types tolérés en paramètre de ces fonctions ?

## Parcours d'une chaîne à l'aide de ses indices

222. Écrivez une fonction miroir() qui prend en paramètre une chaîne et qui renvoie la chaîne inversée, caractère par caractère. Cette fonction utilisera les indices pour parcourir la chaîne à l'envers.

```python
>>> miroir('abc') == 'cba'
True
>>> miroir('') == ''
True
>>> miroir('a') == 'a'
True
>>> miroir('bonjour') == 'ruojnob'
True
>>> miroir('Vive Zorglub !') == '! bulgroZ eviV'
True
```

223. Écrivez une fonction un_caractere_sur_deux() qui prend en paramètre une chaîne et qui renvoie une chaîne constituée d'un caractère sur deux de la chaîne passée en paramètre, en gardant le premier.

```python
>>> un_caractere_sur_deux('abc') == 'ac'
True
>>> un_caractere_sur_deux('') == ''
```
True
>>> un_caractere_sur_deux('a') == 'a'
True
>>> un_caractere_sur_deux('bonjour') == 'bnor'
True
>>> un_caractere_sur_deux('Vive Zorglub !') == 'Vv ogu '
True

224. Écrivez une fonction dernier_indice_caractere() qui renvoie l'indice de la dernière occurrence du caractère passé en paramètre, dans la chaîne passée en paramètre.
On considère que ce caractère est obligatoirement présent dans la chaîne.

>>> dernier_indice_caractere("Bonjour", "B") == 0
True
>>> dernier_indice_caractere("Bonjour", "o") == 4
True
>>> dernier_indice_caractere("Bonjour", "r") == 6
True

225. Écrivez une fonction premier_indice_caractere() qui renvoie l'indice de la première occurrence du caractère passé en paramètre, dans la chaîne passée en paramètre.
On considère que le caractère recherché est présent dans la chaîne.

>>> premier_indice_caractere("Bonjour", "B") == 0
True
>>> premier_indice_caractere("Bonjour", "o") == 1
True
>>> premier_indice_caractere("Bonjour", "r") == 6
True
# Exercices niveau intermédiaire

## Parcours de chaînes

Un palindrome est un mot qui se lit de la même façon de gauche à droite et de droite à gauche. Par exemple, ICI, ELLE et RADAR sont des palindromes. Dit autrement, les palindromes sont des mots ou des chaînes qui sont égales à leur version miroir.

226. Écrivez une première version du prédicat `est_palindrome()` prenant en paramètre une chaîne et renvoyant `True` si cette chaîne est un palindrome et `False` sinon. Cette version utilisera la fonction `miroir()` précédemment écrite.

227. Écrivez une deuxième version de ce prédicat qui compare la 1re lettre de la chaîne à la dernière, puis la 2e à l'avant dernière et ainsi de suite jusqu'à atteindre le milieu de la chaîne. Si ces paires de lettres sont toutes identiques, alors la chaîne est un palindrome.

## Application aux séquences nucléiques

Les questions qui suivent sont une application concrète de l'utilisation de chaînes de caractères à une autre science, la biologie. Vous n'avez pas besoin de connaissances préalables en biologie pour y répondre.

Une séquence d'ADN peut être représentée par une chaîne ne contenant que les quatre lettres A, C, G et T, comme par exemple la chaîne :

ACGGTAGCTAGTTTCGACTGGAGGGGTA

Ces lettres représentent les nucléotides, c'est-à-dire les briques de base de la molécule d'ADN : A = adénine, T = thymine, G = guanine et C = cytosine.

## Fonctions utiles pour commencer

228. Réalisez une fonction nommée `est_ADN()` qui vérifie si la chaîne passée en paramètre ne contient aucun autre caractère que les quatre bases A, C, G et T. Cette fonction retourne la valeur `True` si tel est le cas, et la valeur `False` dans le cas contraire. De plus, elle renvoie `True` si la chaîne est vide.

```
>>> est_ADN('ATGCGATC')
True
>>> est_ADN('ACKT')
False
>>> est_ADN('ACTK')
False
>>> est_ADN("")
True
```

Il est possible de générer aléatoirement une séquence ADN. La version naïve suppose que les 4 bases ont la même probabilité d'apparaître à une position donnée.

229. Réalisez une fonction nommée `genere_ADN()` qui renvoie une séquence ADN générée aléatoirement et dont la taille est passée en paramètre.

## Un brin et son complémentaire

Dans les cellules vivantes, l'ADN est sous la forme double brin, c'est-à-dire que 2 séquences ADN se font face. Une séquence est lue de gauche à droite et l'autre de droite à gauche. De plus, les bases complémentaires l'une
de l'autre se font face. Par exemple, les 2 séquences suivantes sont complémentaires-inversées l'une de l'autre et peuvent ainsi former un double brin :

GTACA

TGTAC

Les bases A et T sont complémentaires entre elles, ainsi que les bases G et C.

230. Réalisez une fonction nommée `base_complementaire()` qui renvoie la base complémentaire de l'unique base passée en paramètre. Une contrainte d'utilisation de cette fonction est que son paramètre est bien une et une seule des quatre bases (A, T, G ou C).

>>> base_complementaire('G')

‘G’

>>> base_complementaire('T')

‘T’

231. Réalisez une fonction nommée `sequence_complementaire_inversee()` qui construit la séquence ADN complémentaire et inversée de celle passée en paramètre. Pour cela, cette fonction fera appel à la fonction `base_complementaire()`. Une contrainte d'utilisation de cette fonction est que son paramètre est bien une séquence ADN.

>>> sequence_complementaire_inversee('ACTG')

‘CAGT’

## Recherche de motifs

Certaines des enzymes qui interagissent avec l'ADN reconnaissent des motifs ADN, c'est-à-dire une suite de nucléotides.

232. Réalisez une fonction nommée `nombreتيres()` qui compte le nombre fois où le motif passé en paramètre est présent dans la séquence d'ADN passée également en paramètre.

>>> nombreتيres_motif('ACG', 'GCTACGGAGCTTCGGAGCACGTAG')

2

>>> nombreoccurrences_motif('TTC', 'AGTCGACTT')

0

## Modification de chaînes

233. Définissez une fonction `ajout_tirets()` qui renvoie la chaîne prise en paramètre avec des tirets - insérés derrière chacun de ses caractères.

>>> ajout_tirets("Bonjour") == "B-o-n-j-o-u-r-"

True

>>> ajout_tirets("a") == "a-"

True

234. Que se passe-t-il si vous passez en paramètre une chaîne vide ? Pourquoi ?

235. Définissez une deuxième version de cette fonction qui n'ajoute pas de tiret après le dernier caractère.

>>> ajout_tirets_v2("Bonjour") == "B-o-n-j-o-u-r-"

True

>>> ajout_tirets_v2("a") == "a"

True

>>> ajout_tirets_v2("") == ""

True

236. Définissez une fonction `supprime_caractere()` prenant en paramètre une chaîne *s* de taille quelconque et un seul caractère *c* et renvoyant la chaîne *s* privée du caractère *c*.

>>> supprime_caractere("valeur de la chaîne", " ") == 'valeurdelachaine'

True

>>> supprime_caractere("test", "t") == "es"

True
```python
>>> supprime_charactere("test", "a") == "test"
True
```

237. Une phrase palindrome est une phrase qui forme un palindrome lorsque l'on enlève tous les espaces qui la compose. La chaîne obtenue n'a pas de sens, mais doit être palindromique. En utilisant certaines des fonctions codées précédemment, écrivez une fonction `est_phrase_palindrome()` qui renvoie `True` si la phrase passée en paramètre est une phrase palindrome. Par exemple, "eh ca va la vache" devient "ehcavalavache" sans les espaces et cette chaîne est un palindrome.

```python
>>> est_phrase_palindrome("eh ca va la vache")
True
>>> est_phrase_palindrome("engage le jeu que je le gagne")
True
>>> est_phrase_palindrome("Engage le jeu que je le gagne.")
False
```

## Exploitation du code ASCII

Les exercices suivant proposent d'écrire des fonctions déjà fournies par la bibliothèque Python.

L'objet des exercices est de travailler directement sur les chaînes de caractères, sans appels aux fonctions prédéfinies, en se basant sur les propriétés de la table ASCII.

On utilisera donc uniquement les deux fonctions reflétant cette table : `ord()` et `chr()`.

### Chiffre et nombres

238. Proposez une fonction `chiffre` qui renvoie la valeur entière d'un chiffre donné sous la forme d'un caractère. Par exemple :

```python
>>> chiffre('0')
0
>>> chiffre('4')
4
```

239. Proposez une fonction `entier()` qui renvoie la valeur entière d'une suite de chiffres donnée sous la forme d'une chaîne de caractères

```python
>>> entier('3142')
3142
```

240. Proposez une évolution de la fonction `entier()` pour prendre en compte des nombres précédés d'une éventuel signe :

```python
>>> entier('3142')
3142
>>> entier('-3142')
-3142
>>> entier('+3142')
3142
```

### Minuscules et majuscules

241. Proposez prédicat `est_lettre_majuscule()` qui renvoie la valeur vrai si et seulement si le caractère fourni en paramètre est une lettre majuscule.

Proposez de même un prédicat `est_lettre_minuscule()`

242. Proposez une fonction `lettre_majuscule()` qui renvoie la lettre majuscule d'une lettre minuscule donnée.

243. Proposez une évolution de la fonction `lettre_majuscule()` qui renvoie la lettre majuscule correspondante à y un caractère donné, ou ce caractère inchangé si ce n'est pas une lettre minuscule.

244. Proposez une évolution de la fonction `en_majuscule()` qui renvoie une chaîne passée en paramètre dans laquelle chacune des lettres minscules a été remplacée par la majuscule correspondante.

```python
>>> en_majuscule('vive Python !')
'VIVE PYTHON !'
```
# Exercices niveau confirmé

## Expressions bien parenthésées

Dans ces exercices, le mot expression désigne une chaîne de caractères ne contenant que des parenthèses ouvrantes et fermantes comme par exemple "((()))", "((()") et "((()))".

Une expression est bien parenthésée :

* si le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes,

* et si quelque soit la position dans l'expression, le nombre de parenthèses ouvrantes qui précèdent cette position est toujours supérieur ou égal au nombre de parenthèses fermantes qui précèdent.

Ainsi :

* "((()))" est une expression bien parenthésée

* "((()" est mal parenthésée car il y a 3 parenthèses ouvrantes et seulement 2 parenthèses fermantes

* "((()))" est mal parenthésée car le cinquième caractère est la troisième parenthèse fermante, alors qu'il n'y a que deux parenthèses ouvrantes qui précèdent

## Bien parenthésée

Soit l'algorithme suivant :

Dans un parcours de gauche à droite d'une expression, on utilise un compteur qu'on incrémente à chaque fois qu'on rencontre une parenthèse ouvrante et qu'on décrémente à chaque fois qu'on rencontre une parenthèse fermante,

245. Indiquez à quelle condition sur les valeurs prises par ce compteur l'expression est bien parenthésée. Illustrez votre réponse avec les trois exemples ci-dessus.

246. Réalisez un prédicat *bien parenthesee()* qui renvoie la valeur booléenne vrai si et seulement si la chaîne passée en paramètre est bien parenthésée.

## Factorisation

Par la suite, on ne travaille qu'avec des expressions bien parenthésées.

On appelle factorisation d'une expression un découpage de cette expression en expressions bien parenthésées consécutives.

Chacune de ces expressions étant appelée facteur.

Voici quelques factorisations d'expressions bien parenthésées :

* "((()))" → "((()))" – un seul facteur

* "()((()" → "()" + "((()" – deux facteurs

* "((()()()" → "()" + "()" + "((()" – trois facteurs

247. Réalisez une fonction *nbre_facteurs()* calcule le nombre de facteurs que possède une expression bien parenthésée donnée.

248. Réalisez maintenant une fonction *decoupe_facteurs()* qui renvoie tous les facteurs d'une expression bien parenthésée en insérant entre eux le caractère '*' :

```
>>> decoupe_facteurs('((()())') == '(()())'
True
>>> decoupe_facteurs('((()()()()()') == '(())*(()*(()())'
True
```
# Modification de chaînes

## Censure (épisode 1)

On souhaite pouvoir censurer une sous-chaîne dans un texte donné.

```python
>>> censure1('La fonction `print()` peut être pratique.', 'print')
'La fonction `*****()` peut être pratique.'
>>> censure1('Bal tragique à Colombey : 1 mort', 'o')
'Bal tragique à C*l*mbey : 1 m*rt'
```

Définissez une fonction `censure1()`, paramétrée par deux chaînes, et renvoyant le texte de la première, en remplaçant chacune des occurences de la seconde par autant d'étoiles * que la *longueur* de la seconde.
8. Itération conditionnelle - while
# Itération conditionnelle

## Coup d'œil

On découvre :

* comment répéter l'exécution de certaines parties d'un programme tant qu'une condition est respectée

* ce qu'est une itération conditionnelle

## Itération conditionnelle

Pour répéter une séquence d'instructions, il est possible dans certains cas d'utiliser un itérable et une boucle `for` si l'on connait à l'avance le nombre d'itérations de la boucle.

On peut aussi vouloir répéter une séquence d'instructions tant qu'une certaine condition est – ou n'est pas – vérifiée.

Le nombre d'itérations n'est alors pas connu à l'avance.

Par exemple une recherche de seuil comme : « à partir de quelle valeur la somme des premiers entiers $1 + 2 + 3 + \dots + n$ dépasse 1000 ? ».

Il nous faut pouvoir identifier :

* la condition : ce sera une valeur booléenne.

* la ou les instructions à répéter : ce sera un bloc d'instructions, repéré par une indentation supplémentaire.

Dans notre exemple :

* la condition sera que la somme ne dépasse pas 1000

* les instructions à répéter devront mettre à jour la valeur de `n` et la somme

Une telle structure est une boucle appelée *itération conditionnelle*.

## Instruction while

En Python, on utilisera le mot clé `while` et on écrira par exemple :

```python
n = 1
somme = 1
while somme <= 1000 :
    n = n + 1
    somme = somme + n
```

Que l'on peut lire : « tant que la somme est inférieure à 1000, ajouter 1 à `n` et ajouter `n` à `somme` ».

## Flot d'exécution

Rappelons que le flot d'exécution est l'ordre dans lequel les instructions sont exécutées.

Considérons le code suivant :

```python
...
while condition :
    instructions
```
Le flot d'exécution correspondant peut être illustré par le graphe :

<figure><img src="image_21.png" /></figure>

* la condition est évaluée. On obtient une valeur booléenne.

* si cette valeur est `vrai`

- les instructions associées au `while` sont exécutées

- on retourne au point précédent pour évaluer à nouveau la condition

* si cette valeur est `faux`

- on passe à l'exécution des instructions suivantes (...).

## Exemple complémentaire

Des épidémiologistes estiment que le nombre de cas positifs double tous les trois jours.

Des médecins connaissent le nombre de cas positifs actuels, et voudraient calculer le temps au bout duquel ce nombre de cas positifs atteindra une valeur donnée.

Par exemple pour une population contenant 100 cas positifs :

* au bout de 3 jours, il y a aura 200 cas positifs,

* au bout de 6 jours, il y aura 400 cas positifs, et

* au bout de 9 jours il y en aura 800.

On dépassera alors, par exemple :

* le seuil de 400 au bout de 6 jours,

* le seuil de 401 au bout de 9 jours, et

* le seuil de 799 au bout de 9 jours également.

Pour calculer cette durée, écrivons une fonction `duree()` paramétrée par deux entiers : `cas_initiaux` représentant le nombre de cas positifs au jour 0, `seuil` représentant le seuil atteint.

Dans cette fonction, nous utiliserons deux variables :

* `jours` pour compter le nombre de jours,

* `cas` pour compter le nombre de cas.

Ces deux variables seront initialisées respectivement à 0 et `cas_initiaux`.

Les instructions qui doivent être répétées sont l'incrémentation de `jours` par 3, et le doublement de `cas`.

La condition devant être respectée pour continuer les itérations est `cas < seuil`: tant que le seuil n'est pas atteint ou dépassé, on continue de compter les jours.

def duree(cas_initiaux, seuil):

"""Renvoie le temps requis pour qu'une population de cas_initiaux cas positifs atteigne le seuil en doublant tous les trois jours.

Paramètres :

- `cas_initiaux`: `int`, nombre de cas positifs au jour 0

- `seuil`: `int`, nombre de cas positifs à atteindre ou dépasser

Valeur de retour : `int`, temps exprimé en nombre de jours

Exemples :

>>> duree(100, 400)

6
```python
>>> duree(100, 401)
9
>>> duree(100, 799)
9
"""
jours = 0
cas = cas_initiaux
while cas < seuil :
    jours = jours + 3
cas = cas * 2
return jours
```

# Remarques et compléments

## Évolution de la valeur de la condition

Observons le code suivant :

```c
# (1)
while condition :
    # (2)
    instructions
    # (3)
# (4)
```

dans lequel les commentaires (1), (2), (3) et (4) servent à indiquer un emplacement dans le flot d'exécution.

1. Juste avant la boucle – au point (1) –, l'expression booléenne `condition` peut prendre les valeurs

* True, auquel cas on est sûr qu'il y aura au moins une itération, ou

* False, auquel cas on est sûr qu'il n'y aura aucune itération.

2. Au début d'une itération – au point (2) –, l'expression booléenne `condition` est nécessairement vraie.

3. À la fin d'une itération – au point (3) –, l'expression booléenne `condition` peut valoir

* True, auquel cas la boucle continuera pour une autre itération au moins, ou

* False, auquel cas, la boucle s'arrêtera.

4. Juste après la boucle – au point (4) –, l'expression booléenne `condition` est nécessaire fausse.

## Boucle infinie

Le nombre d'itérations d'une boucle `while` n'est a priori pas connu.

Il peut y avoir aucune itération : les instructions ne seront pas exécutées.

Il peut aussi arriver que la condition de la boucle `while` soit toujours vérifiée.
On parle de boucle infinie.

L'exécution du code ne termine pas...

```c
i = 1
while i > 0 :
    i = i + 1
```

## Boucle imbriquée

Nous avons vu que les boucles `for` peuvent être imbriquées sans nuire à la lisibilité du code.

Dans le cadre de ce cours, on évitera d'imbriquer une boucle `while` dans une autre boucle.

Si nécessaire, on préfèrera appeler une fonction auxiliaire – contenant une boucle `while` – dans une autre boucle.
Memento

* l'instruction d'itération conditionnelle *while* permet d'exécuter un bloc d'instructions tant qu'une condition est vérifiée
# Utilisations typiques de boucles 'while'

## Coup d'œil

On découvre

* quelques problèmes courants dont la résolution passe par l'utilisation d'itérations conditionnelles

## Appartenance

On cherche à savoir si un caractère `c` appartient à une chaîne `s`.

Pour cela, on parcourt la chaîne, et on s'arrête une fois le caractère trouvé.

Il est inutile de continuer le parcours de la chaîne une fois le caractère trouvé.

Le nombre d'itérations ne peut pas être connu à l'avance. Nous allons donc utiliser une boucle `while`.

## Fonction appartient()

Le principe est le suivant :

* on utilise un indice `i` commençant à 0, qui parcourra les indices des caractères de la chaîne

* on ne parcourra pas les caractères après que le caractère `c` soit trouvé.

La condition d'arrêt de la boucle sera alors : « le parcours de la chaîne n'est pas fini et le caractère `c` n'a pas été trouvé ».

Une fois la boucle terminée, on se pose la question de l'arrêt : la fin de la boucle implique

* soit que la chaîne a été parcourue complètement, et dans ce cas `i == len(s)` est vraie, Le caractère `c` n'appartient pas à la chaîne `s`.

* soit que `c` a été trouvé, et dans ce cas `i < len(s) et s[i] == c` sont vraies. Le caractère `c` appartient à la chaîne `s`.

La valeur de l'expression `i < len()` permet de déterminer ce pourquoi la boucle s'est terminée, et de conclure sur l'appartenance ou non du caractère `c` à la chaîne `s`.

On obtient la fonction suivante :

```python
def appartient(c, s):
    """Renvoie True ssi la chaîne s contient le caractère c.
    Paramètres :
        c (str) : caractère recherché
        s (str) : chaîne dans laquelle on recherche c
    Valeur de retour (bool) : c appartient à s
    Contraintes : len(c) == 1
    Exemples :
        >>> appartient('e', 'panier')
        True
        >>> appartient('o', 'desert')
        False
        """
        i = 0
```
```python
while i < len(s) and s[i] != c:
    i = i + 1
return i < len(s)
```

## Exemples d'exécution

Exécutons cette fonction sur deux exemples simples.

```python
>>> appartient('a', 'bac')
True
```

On initialise la variable `i` à la valeur 0. Cela signifie qu'on s'apprête à regarder la valeur de `s[0]`, le premier caractère de la chaîne `s`.

La boucle `while` commence :

* on évalue l'expression booléenne : `0 < len(s)` est vraie, puis `s[0] != 'a'` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 1.

* on évalue l'expression booléenne : `1 < len(s)` est vraie, puis `s[1] != 'a'` est fausse, la conjonction est donc fausse. La boucle s'arrête.

On évalue alors `1 < len(s)`. Comme cette expression est vraie, on renvoie `True`.

```python
>>> appartient('a', 'bcd')
False
```

On initialise la variable `i` à la valeur 0. Cela signifie qu'on s'apprête à regarder la valeur de `s[0]`, le premier caractère de la chaîne `s`.

La boucle `while` commence :

* on évalue l'expression booléenne : `0 < len(s)` est vraie, puis `s[0] != 'a'` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 1.

* on évalue l'expression booléenne : `1 < len(s)` est vraie, puis `s[1] != 'a'` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 2.

* on évalue l'expression booléenne : `2 < len(s)` est vraie, puis `s[2] != 'a'` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 3.

* on évalue l'expression booléenne : `3 < len(s)` est fausse, et on n'a donc pas besoin d'évaluer `s[3] != c` (cette évaluation déclencherait d'ailleurs une erreur d'indexation car `s[3]` n'existe pas).

On évalue alors `3 < len(s)`. Comme cette expression est fausse, on renvoie `False`.

## Exemple d'utilisation de la fonction appartient()

Le prédicat `est_lettre_française()` qui permet de savoir si un caractère est une des quarante-deux lettres de l'alphabet français pourrait être défini en utilisant le prédicat `appartient()`.

(au sujet des 42 lettres de l'alphabet français, voir par exemple la page fr.wikipedia.org/wiki/Alphabet_français)

```python
def est_lettre_française(c):
    """Renvoie True si c est une lettre française (peut importe la casse) et
    False sinon.

    Paramètres :
        c (str) : le caractère à tester
        Valeur de retour (bool) : c est une lettre française
        Contraintes : len(c) == 1

    Exemples :
        >>> est_lettre_française('É')
        True
        >>> est_lettre_française('Ω')
        False
        """
```
```python
return (c >= 'a' and c <= 'Z' or c >= 'A' and c <= 'Z'
        or appartient(c, 'ÀàÂâÆÇçÉéÈeÊêËeÎîÏiÔôŒœÛùÛúÛüÝÿ'))
```

## Indice

On cherche maintenant l'indice d'un caractère c dans une chaîne s.

Ce problème est en fait mal défini :

* que se passe-t-il dans une chaîne ne contenant pas c ?

* que se passe-t-il dans une chaîne contenant plusieurs fois c ?

Pour répondre à ces ambiguïtés, on précise le problème : on cherche

* le plus petit indice d'un caractère c dans une chaîne s (donc l'indice de la première occurrence de c),

* ou la taille de s si cette chaîne ne contient pas c.

Le code d'une fonction solution de ce problème est très similaire à celui du prédicat appartient() :

```python
def indice(c, s):
    """Renvoie l'indice de première occurrence du caractère c dans la chaîne s si cette dernière contient c, len(s) sinon.
    Paramètres :
        c (str) : caractère recherché
        s (str) : chaîne dans laquelle on recherche c
        Valeur de retour (int) : indice de 1ère occurrence de c ou len(s)
    Contraintes : len(c) == 1
    Exemples :
        >>> indice('b', 'abba') == 1
        True
        >>> indice('o', 'desert') == len('desert')
        True
        """
        i = 0
        while i < len(s) and s[i] != c:
            i = i + 1
        return i
```

## Pour tous

On cherche à vérifier si tous les éléments d'un itérable vérifient une propriété.

On cherche par exemple à savoir si tous les caractères d'une chaîne sont des lettres françaises.

Comme cela ne sert à rien de continuer de parcourir la chaîne si on a découvert un caractère qui n'est pas une lettre française, on utilisera une boucle while.

```python
def que_des_lettres_francaises(s):
    """Renvoie True si tous les caractères de s sont des lettres françaises, et
    False sinon.
    Paramètres :
        s (str)
        Valeur de retour (bool)
    Exemples :
        >>> que_des_lettres_francaises('œdème')
        True
        >>> que_des_lettres_francaises('top50')
        False
        """
        i = 0
        while i < len(s) and est_lettre_francaise(s[i]):
            i = i + 1
        return i == len(s)
```
## Exemples d'exécution

Exécutons cette fonction sur deux exemples simples.

```python
>>> que_des_lettres_francaises('H20')
False
```

On initialise la variable `i` à la valeur 0. Cela signifie qu'on s'apprête à regarder la valeur de `s[0]`, le premier caractère de la chaîne `s`.

La boucle `while` commence :

* on évalue l'expression booléenne : `0 < len(s)` est vraie, puis `est_lettre_francaise(s[0])` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 1.

* on évalue l'expression booléenne : `1 < len(s)` est vraie, puis `est_lettre_francaise(s[1])` est fausse, la conjonction est donc fausse, et la boucle s'arrête.

On évalue alors `1 == len(s)`. Comme cette expression est fausse, on renvoie `False`.

```python
>>> que_des_lettres_francaises('été')
True
```

On initialise la variable `i` à la valeur 0. Cela signifie qu'on s'apprête à regarder la valeur de `s[0]`, le premier caractère de la chaîne `s`.

La boucle `while` commence :

* on évalue l'expression booléenne : `0 < len(s)` est vraie, puis `est_lettre_francaise(s[0])` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 1.

* on évalue l'expression booléenne : `1 < len(s)` est vraie, puis `est_lettre_francaise(s[1])` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 2.

* on évalue l'expression booléenne : `2 < len(s)` est vraie, puis `est_lettre_francaise(s[2])` est vraie, la conjonction est donc vraie.
  On exécute alors l'instruction `i = i + 1`, et `i` prend alors la valeur 3.

* on évalue l'expression booléenne : `3 < len(s)` est fausse, et on n'a donc pas besoin d'évaluer `est_lettre_francaise(s[3])` (cette expression déclencherait d'ailleurs une erreur d'indexation car `s[3]` n'existe pas).

On évalue alors `3 == len(s)`. Comme cette expression est vraie, on renvoie `True`.
# Autres utilisations typiques de boucles
'while'

## Coup d'œil

On découvre

* d'autres problèmes courants dont la résolution passe par l'utilisation d'itérations conditionnelles

## Suite de Syracuse

D'après fr.wikipedia.org/wiki/Conjecture_de_Syracuse :

En mathématiques, on appelle suite de Syracuse une suite d'entiers naturels définie de la manière suivante : on part d'un nombre entier plus grand que zéro ;

* s'il est pair, on le divise par 2 ;

* s'il est impair, on le multiplie par 3 et on ajoute 1.

En répétant l'opération, on obtient une suite d'entiers positifs dont chacun ne dépend que de son prédécesseur.

Par exemple, à partir de 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2...

C'est ce qu'on appelle la suite de Syracuse du nombre 14.

Après que le nombre 1 a été atteint, la suite des valeurs (1, 4, 2, 1, 4, 2...) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.

On n'a jamais trouvé d'exemple de suite obtenue suivant les règles données qui n'aboutisse pas à 1, puis au cycle trivial.

On cherche à connaître la *durée du vol* de Syracuse d'un nombre strictement positif *n*, c'est-à-dire le nombre d'étapes nécessaires pour atteindre 1.

Par exemple, pour 14, il faudra 17 étapes.

Le nombre d'étapes n'est pas connu a priori (c'est d'ailleurs la valeur que l'on cherche à calculer !). On utilisera donc une boucle `while`.

def vol_syracuse(n):

"""Nombre d'étapes nécessaires pour atteindre 1 en partant de n dans la suite de Syracuse.

Paramètres :

- n (int)

Valeur de retour (int) : nombre d'étapes

Contraintes : n > 0

Exemples

>>> vol_syracuse(14) == 17

True

>>> vol_syracuse(1) == 0

True

"""
```
etape = 0
terme = n
while terme != 1:
    if terme % 2 == 0:
        terme = terme // 2
    else:
        terme = terme * 3 + 1
etape = etape + 1
return etape
```

## Comme des lapins !

Un couple de lapereaux est déposé sur une île.

1. Au bout du premier mois, ces lapins deviennent adultes et peuvent se reproduire. Il y a donc 1 couple de lapins adultes sur l'île, et 0 couple de jeunes.

2. Au bout du deuxième mois, ils donnent naissance à un couple de jeunes et continuent de se reproduire. Il y a donc 1 couples d'adultes sur l'île, et 1 couple de jeunes.

3. Au bout du troisième mois, le couple d'adultes encore naissance à des jeunes et continuent de se reproduire. Le couple de jeunes devient un couple d'adultes et commencent à se reproduire. Il y a donc 2 couples d'adultes et 1 couple de jeunes.

4. Au bout du quatrième mois, les deux couples d'adultes donnent chacun naissance à un couple de jeunes, et le couple de jeunes devient 1 couple d'adultes. Il y a donc 3 couples d'adultes et 2 couple de jeunes.

Et ça continue !

Chaque mois, tous les couples de jeunes deviennent un couple d'adultes, et tous les couples d'adultes donnent chacun naissance à un couple de jeunes. On se demande au bout de combien de mois ce nombre de couples de lapins dépassera un certain seuil.

Nous allons résoudre ce problème en utilisant une boucle dans laquelle chaque itération représentera un mois.

```
def population_lapins(seuil):
    """Renvoie le nombre de mois au bout duquel le nombre de couples de lapins
dépassera le `seuil`.

    Paramètres :
        - seuil (int) : seuil à dépasser (exprimé en nombre de couples de lapins)
        - Valeur de retour (int) : nombre de mois

    Contraintes : seuil ≥ 0
    >>> population_lapins(4)

    4
    """

    # Au tout début, il y a 1 couple de jeunes et 0 couple d'adultes
    mois = 0
couples_jeunes = 1
couples_adultes = 0
while couples_jeunes + couples_adultes < seuil:
    # les jeunes deviennent adultes
couples_ados = couples_jeunes
couples_jeunes = 0
    # les adultes donnent naissance à des jeunes
couples_jeunes = couples_adultes
    # les ados rejoignent les adultes
couples_adultes = couples_adultes + couples_ados
    # un mois s'est écoulé
mois = mois + 1
return mois
```

L'évolution de cette population de lapins suit la célèbre suite de Fibonacci.
# PGCD

Pour calculer le plus grand diviseur commun entre deux nombres naturels, on peut utiliser l'algorithme d'Euclide, basé sur les deux égalités suivantes :

$$ \forall (a, b) \in \mathbb{N} \quad \text{pgcd}(a, b) = \begin{cases} a & \text{si } b = 0 \\ \text{pgcd}(b, a - kb) & \text{\textbf{\quad} \forall k \text{ sinon}} \end{cases} $$

**TODO** l'introduction de *k* est-elle utile ? Donner les égalités pour la seule valeur de *k* considérée ?

On prendra ici *k* le quotient de *a* dans la division euclidienne par *b* (et donc *a* − *kb* vaudra le reste de *a* dans la division euclidienne par *b*).

Comme on ne sait pas combien d'itérations seront nécessaires, on utilise une boucle `while`.

```python
def pgcd(x, y):
    """Renvoie le plus grand diviseur commun de x et y
    Paramètres :
        x (int)
        y (int)
    Valeur de retour (int) : le pgcd de x et y
    Contraintes : x ≥ 0 et y ≥ 0 et (x,y)≠(0,0)
    Exemples :
        >>> pgcd(7, 5) == 1
        True
        >>> pgcd(42, 2020) == 2
        True
        """
        # a, b = x, y
        a = x
        b = y
        while b > 0:
            # a, b = b, a%b
            reste = a % b
            a = b
            b = reste
        return a
```

Observons le comportement de cette fonction sur un exemple simple.

```python
>>> pgcd(51, 42)
3
```

Nous allons représenter dans un tableau les différentes valeurs prises par les variables *a* et *b* juste avant la boucle, puis en fin de chaque itération.

<table><thead><tr><th>a</th><th>b</th></tr></thead><tbody><tr><td>51</td><td>42</td></tr><tr><td>42</td><td>9</td></tr><tr><td>9</td><td>6</td></tr><tr><td>6</td><td>3</td></tr><tr><td>3</td><td>0</td></tr></tbody></table>

Si on applique l'algorithme d'Euclide à la main, on obtient :

$$ 
\begin{align*}
51 &= 42 \times 1 + 9 \\
42 &= 9 \times 4 + 6 \\
9 &= 6 \times 1 + 3 \\
6 &= 3 \times 2 + 0
\end{align*}
$$

On remarque alors que chaque ligne (sauf la dernière) du tableau des valeurs correspond à une étape dans l'exécution de l'algorithme d'Euclide. *a* correspond alors au dividende et *b* au diviseur.
# Exercices niveau débutant

## Quotient et reste dans la division euclidienne

Observez la procédure suivante :

```python
def divmod_verbeux(a, b):
    """Affiche les calculs qu'un élève de CE1 ferait pour
    obtenir le quotient et le reste de la division euclidienne
    de a par b.
    Contraintes : a >= 0 et b > 0
    """
    reste = a
    nb_soustractions = 0
    print("Au début, on a fait", nb_soustractions, "soustractions,",
           "et le reste est", reste)
    # début de la boucle
    while reste >= b:
        nb_soustractions = nb_soustractions + 1
        reste = reste - b
        print("Après", nb_soustractions, "soustractions, le reste vaut", reste)
    # fin de la boucle
    print("Au final, on a fait", nb_soustractions, "soustractions,",
           "et le reste est", reste)
```

249. Créez une procédure `main()` qui appelle `divmod_verbeux()` sur différentes valeurs de `a` et `b` respectant les contraintes.

Testez votre programme affichant dans la console les calculs effectués pour la division euclidienne de 42 par 5.

Que pouvez-vous dire de la condition `reste >= b` avant l'exécution de la boucle ? Après l'exécution de la boucle ?

250. Définissez une fonction `reste()` renvoyant le reste dans la division euclidienne du premier paramètre par le second. Cette fonction ne devra pas utiliser les opérateurs `//` et `%`.

251. Définissez une fonction `quotient()` renvoyant le quotient dans la division euclidienne du premier paramètre par le second. Cette fonction ne devra pas utiliser les opérateurs `//` et `%`.

## Le blob

Le blob (*physarum polycephalum*) est un organisme mono-cellulaire qui double de taille tous les jours. On veut connaitre le nombre de jours nécessaires pour atteindre une taille de 1m.

252. Définissez une fonction `croissance_blob()` paramétrée par un flottant représentant la taille initiale en mètres, et renvoyant le nombre de jours après lesquels le blob atteindra ou dépassera 1 mètre.

## Période radioactive

La période radioactive ou demi-vie d'un isotope est le temps nécessaire à la désintégration de la moitié des noyaux d'un fragment de cet isotope.
On cherche à calculer le nombre de périodes radioactives nécessaire à la disparition d'une partie des noyaux d'un isotope. Par exemple, pour faire disparaître les trois quarts des noyaux d'un isotope donné, il faut attendre deux périodes radioactives. En effet, au bout d'une période, il en reste la moitié, et au bout de deux périodes il en reste un quart. Les trois quarts ont donc disparu...

253. Définissez une fonction `nb_periodes_rad()` paramétrée par un flottant représentant la part de noyaux d'un isotope que l'on veut voir disparaître et qui renvoie le nombre de périodes radioactive nécessaires à cette disparition.

## Racine carrée entière

La racine carrée entière d'un nombre entier $x$ naturel est le plus grand entier vérifiant $n^2 \le x$. Si on nomme $r$ cette racine carrée entière, alors $r$ vérifie $r^2 \le x < (r+1)^2$.

Pour calculer cette racine carrée entière, on teste conséutivement les entiers $n$ en commençant à 0, en s'arrêtant quand $n^2$ dépasse $x$.

254. Définissez une fonction `racine_carree_entiere()` qui renvoie la racine carrée entière du nombre passé en paramètre.

```python
>>> racine_carree_entiere(9)
3
>>> racine_carree_entiere(8)
2
>>> racine_carree_entiere(10)
3
```

## Retour sur des exercices précédents

Les semaines précédentes, vous avez proposé certaines solutions d'exercices faisant des itérations inutiles.

Vous pourrez ici corriger ces fonctions en utilisant une boucle `while` à la place d'une boucle `for`.

255. Proposez un prédicat `sont_minuscules()` qui vérifie que tous les caractères d'une chaîne de caractères sont des lettres minuscules ou des espaces. On utilisera la fonction Python prédéfinie `islower()` pour vérifier qu'un caractère est une lettre minuscule :

256. Écrivez une troisième version du prédicat `est_palindrome()` qui vérifie si la chaîne passée en paramètre est un palindrome. Cette fonction renvoie la valeur `True` si tel est le cas, et la valeur `False` dans le cas contraire.

257. Réalisez une fonction nommée `est_ADN()` qui vérifie si la chaîne passée en paramètre ne contient aucun autre caractère que les quatre bases A, C, G et T. Cette fonction renvoie la valeur `True` si tel est le cas, et la valeur `False` dans le cas contraire. De plus, elle renvoie `True` si la chaîne est vide.

```python
>>> est_ADN('ATGCGATC')
True
>>> est_ADN('ACKT')
False
>>> est_ADN('ACTK')
False
>>> est_ADN('')
True
```

## Vol de Syracuse

Dans le cours on a donné la solution pour déterminer à quel rang la suite de Syracuse atteint 1.

258. Définissez une fonction `altitude_max_syracuse()` qui donne la valeur maximale durant la durée du vol (cette valeur est appelée altitude maximale).

Utilisez par exemple les exécutions suivantes pour tester votre fonction :

```python
>>> altitude_max_syracuse(1024)
1024
```
>>> altitude_max_syracuse(871)
190996
# Exercices niveau intermédiaire

## Test de primalité naïf

Un entier $p$ est dit premier si il est supérieur ou égal à 2 et si aucun des entiers compris entre 2 et $p-1$ inclus ne divise $p$.

259. Définissez un prédicat nommé `est_premier_naif()` renvoyant `True` si l'entier passé en paramètre est un nombre premier, et `False` sinon.

```python
def est_premier_naif(p):
    """Renvoie True ssi p est premier.
    Paramètres :
        p (int) : entier dont on veut tester la primalité
        Valeur de retour (bool) : primalité de p
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> est_premier_naif(1)
        False
        >>> est_premier_naif(13)
        True
        >>> est_premier_naif(2020)
        False
        """
```

Les intervalles peuvent aussi être indexés, comme les chaînes.

```python
>>> range(2, 6)[1]
3
```

260. Définissez un prédicat `au.moins.un_premier` paramétré par un intervalle, et renvoyant `True` si et seulement si l'intervalle passé en paramètre contient au moins un nombre premier. Par exemple l'intervalle `range(12)` contient 2, qui est premier, alors qu'aucun des trois éléments de l'intervalle `range(8, 11)` (qui sont 8, 9 et 10) n'est premier.

```python
def au.moins_un_premier(intervalle):
    """Renvoie True si intervalle contient au moins un nombre premier.
    Paramètres :
        intervalle (range)
        Valeur de retour (bool)
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> au.moins_un_premier(range(12))
        True
        >>> au.moins_un_premier(range(8,11))
        False
        """
```

## Écriture décimale d'un nombre

Dans tout cet exercice, il sera interdit d'utiliser `str()`.
261. Définir une fonction somme_chiffres() renvoyant la somme des chiffres dans l'écriture décimale du nombre passé en paramètre.

Voici comment pourrait marcher l'algorithme sur 2021 :

1. On initialise une variable somme à 0 et une autre variable reste à 2021.

2. On incrémente la somme du reste dans la division euclidienne de 2021 par 10 (somme vaut donc 1) et on change la valeur de reste en le quotient dans la division euclidienne de 2021 par 10 (reste vaut donc 202).

3. On incrémente la somme du reste dans la division euclidienne de 202 par 10 (somme vaut donc 3) et on change la valeur de reste en le quotient dans la division euclidienne de 202 par 10 (reste vaut donc 20).

4. On incrémente la somme du reste dans la division euclidienne de 20 par 10 (somme vaut donc 3) et on change la valeur de reste en le quotient dans la division euclidienne de 20 par 10 (reste vaut donc 2).

5. On incrémente la somme du reste dans la division euclidienne de 2 par 10 (somme vaut donc 5) et on change la valeur de reste en le quotient dans la division euclidienne de 2 par 10 (reste vaut donc 0).

6. Comme reste vaut 0, on s'arrête et on renvoie somme

```python
def somme_chiffres(n):
    """Renvoie la somme des chiffres de n
    Paramètres :
        - n (int)
    Valeur de retour (int) : somme des chiffres de n
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> somme_chiffres(2021) == 5
        True
        """
```

262. Définir une fonction miroir_chiffres() renvoyant le nombre dont l'écriture décimale est la symétrique de celle du nombre passé en paramètre. Par exemple miroir_chiffres(2021) a pour valeur 1202.

```python
def miroir_chiffres(n):
    """Renvoie le nombre dont l'écriture est la symétrique de celle de n
    Paramètres :
        - n (int)
    Valeur de retour (int)
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> miroir_chiffres(2021) == 1202
        True
        >>> miroir_chiffres(2020) == 202
        """
```

## Sous-chaînes

On dit que la chaîne *p* est préfixe de la chaîne *s* s'il existe une chaîne *w* telle que *s* == *p* + *w*, autrement si la chaîne *s* commence par la chaîne *p*. Remarquez que `''` la chaîne vide est préfixe de toute chaîne (`w` = *s* convient), et toute chaîne *s* est préfixe d'elle-même (`w` = `''` convient).

263. Définissez un prédicat est_prefixe() renvoyant True si son premier paramètre est préfixe du second et False sinon.

```python
def est_prefixe(p, s):
    """Renvoie True ssi p est préfixe de s.
    Paramètres :
        - p (str)
        - s (str)
    Valeur de retour (bool)
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> est_prefixe("bon", "bonjour")
```
True
>>> est_prefixe("bonjour", "bon")
False
>>> est_prefixe("cuba", "cacao")
False
>>> est_prefixe("bon", "bon")
True
"""

264. Définissez un prédicat `est_souschaine()` renvoyant `True` si son premier paramètre est sous-chaîne du second, et `False` sinon.

def est_souschaine(sc, s):
    """Renvoie True ssi sc est préfixe de s.
    Paramètres :
        - sc (str)
        - s (str)
    Valeur de retour (bool)
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> est_souschaine("lit", "ponctualité")
        True
        >>> est_souschaine("pilote", "avion")
        False
        >>> est_souschaine("fin", "Début de la fin")
        True
        """

## Mots de Dyck

On dit qu'une chaîne est *bien parenthésée* si à chaque parenthèse ouvrante est associée une parenthèse fermante plus loin dans la chaîne.

Par exemple `((()())` est bien parenthésée, par contre `()()()`, `()()` et `()()` ne le sont pas.

265. À la main, définissez un compteur initialisé à 0, et parcourez la chaîne. À chaque occurrence de parenthèse ouvrante, incrémentez ce compteur, et décrémentez-le à chaque occurrence de parenthèse fermante.

Appliquez cet algorithme sur les 4 exemples précédents. À quelles conditions sur ce compteur au cours du parcours de la chaîne et à la fin du parcours une chaîne est-elle mal parenthésée ? (*Indication : si vous n'avez pas trouvé ces conditions, vous pouvez consulter l'exercice sur les expressions bien parenthésées dans la partie avancée des exercices sur les chaînes.*)

266. Définissez un prédicat `est_bien_parenthesee()` qui renvoie `True` si la chaîne passée en paramètre est bien parenthésée et `False` sinon.

def est_bien_parenthesee(s):
    """Renvoie True ssi s est bien parenthésée.
    Paramètres :
        - s (str)
    Valeur de retour (bool)
    Contraintes : À COMPLÉTER !
    Exemples :
        >>> est_bien_parenthesee('()')('')
        False
        >>> est_bien_parenthesee('()()')
        True
        >>> est_bien_parenthesee('()')
        False
        >>> est_bien_parenthesee('()')
        False
        """
## Anagrammes

Pour faire cet exercice, vous aurez besoin de la fonction `supprime_charactere()` de la feuille d'exercices intermédiaires sur les chaînes.

267. Définissez une fonction `nombrerizulations()` paramétrée par un caractère `c` et une chaîne `s` et renvoie le nombre d'occurrences de `c` dans `s`. (Indication : utilisez une boucle `for`.)

Pour savoir si deux chaînes sont des anagrammes, il suffit de compter les nombres d'occurrences du premier caractère de la première chaîne dans chacune des deux chaînes, et, si ces nombres sont égaux, de réitérer sur les deux chaînes obtenues en supprimant toutes les occurrences de ce caractère.

268. Définissez un prédicat `sont_anagrammes()` paramétré par deux chaînes et renvoyant `True` si ces deux chaînes sont anagrammes l'une de l'autre et `False` sinon, en mettant en œuvre la méthode proposée ci-dessus.

def sont_anagrammes (s1, s2):

"""Renvoie True ssi s1 est un anagramme de s2.

Paramètres :

- s1 (str)

- s2 (str)

Valeur de retour (bool)

Contraintes : À COMPLÉTER !

Exemples :

>>> sont_anagrammes('chien', 'niche')

True

>>> sont_anagrammes('chien', 'nicher')

False

>>> sont_anagrammes('abba', 'baaa')

False

###
# Exercices niveau confirmé

## Formatage (épisode 1)

Dans un but de remplissages de messages ou formulaires automatiques, on souhaiterait utiliser une fonction permettant de construire une chaîne à partir d'un modèle et d'une chaîne de substitution.

```python
>>> format1('{}', {}, {} !', 'Beetlejuice')
'Beetlejuice, Beetlejuice, Beetlejuice !'
>>> format1("Cher {}", vous êtes l'unique gagnant !", 'Marinette')
"Cher Marinette, vous êtes l'unique gagnant !"
```

Définissez une fonction `format1()`, paramétrée par une chaîne de modèle et une chaîne de substitution qui renvoie une chaîne obtenue en remplaçant toutes les occurences de la sous-chaîne `{}` par la chaîne de substitution.

Libre à vous de choisir le comportement de la fonction si la chaîne de modèle contient une accolade ouvrante `{` sans accolade fermante `}` consécutive. Ce comportement devra néanmoins être documenté.

Envisagez aussi cette situation :

```python
>>> format1("Allons jusqu'au {}", "bout.") == "Allons jusqu'au bout."
True
```

## Génération d'une chaîne sans doublons de lettres qui se suivent

Nous allons créer une fonction, `tirage_non_repet()`, qui génère aléatoirement une chaîne de caractères qui ne contient jamais deux lettres identiques qui se suivent. Cette fonction prendra en paramètre un entier naturel représentant la taille de la chaîne à générer.

Elle utilisera une fonction auxiliaire, `tirage_lettre()`, qui ne prend pas de paramètre et qui renvoie une lettre minuscule tirée au sort. Nous rappelons que les codes ASCII des lettres minuscules sont compris entre 97 et 122 (inclus).

Exemples d'utilisation de ces fonctions :

```python
>>> tirage_lettre()
'o'
>>> tirage_lettre()
'x'
>>> tirage_non_repet(5)
'ympwup'
>>> tirage_non_repet(30)
'zmrpdknwgsgqnfebxalchukpigwolnz'
```
9. Listes Python - 1re partie
# Découvrir les listes Python

## Coup d'œil

On découvre

* comment manipuler des collections de valeurs

* comment écrire des listes Python

* comment parcourir une liste Python ou accéder à un de ses éléments

## Liste

Il est parfois nécessaire de manipuler une collection de valeurs.

Par exemple le nombre de jours de chacun des mois de l'année, ou les notes de l'ensemble des étudiants de lre année de licence...

En Python, on utilisera par exemple les *listes*.

Ces listes Python sont des structures capables de contenir un nombre quelconque de valeurs.

Comme les chaînes de caractères ou les intervalles *range*, les listes sont des *itérables* : on va donc pouvoir réaliser une même instruction sur chacun des éléments d'une liste.

Comme les chaînes de caractères ou les intervalles *range*, les éléments des listes sont *indicés* : on va donc pouvoir accéder à un élément via son *indice* dans la liste.

Nous découvrirons ensuite d'autres caractéristiques des listes Python.

## Liste — en Python

En Python, une liste de valeurs écrites entre crochets [ et ], et séparées par des virgules, forme une liste.

On écrit par exemple

```python
>>> [31, 28, 31, 30]
[31, 28, 31, 30]
>>> [12.0, 10.5, 9.5, 19., 14.5]
[12.0, 10.5, 9.5, 19.0, 14.5]
```

Le type de ces valeurs est *list*, indépendamment du type des éléments :

```python
>>> type([31, 28, 31, 30])
<class 'list'>
>>> type([12.0, 10.5, 9.5, 19., 14.5])
<class 'list'>
```

## Complément — Tableau et liste en informatique

En informatique, un *tableau* est une structure de données constituée d'une séquence d'éléments auxquels on peut accéder par leur indice.

En informatique, une *liste* est une structure de données qui permet de regrouper des *éléments*, et qui autorise :

* d'ajouter un élément à la liste,

* retirer un élément à la liste,
* savoir si la liste est vide.

Ces deux structures de données classiques se retrouvent dans beaucoup de langages de programmation. Les tableaux ou listes de certains langages peuvent avoir des caractéristiques propres.

Le cas de Python est particulier. La structure de données *liste Python* est plus proche de ce que l'on nomme habituellement *tableau*.

Nous nous en tiendrons pour le moment à l'étude des listes Python.

# Construire des listes

## Séquence d'éléments

Une liste peut donc être écrite comme une suite entre crochets d'éléments séparés par des virgules.

Tous les types sont acceptés :

```python
>>> [31, 28, 31, 30]
[31, 28, 31, 30]
>>> [12.0, 10.5, 9.5, 19., 14.5]
[12.0, 10.5, 9.5, 19.0, 14.5]
>>> ["une", "liste", "Python"]
['une', 'liste', 'Python']
>>> [True, False, False, True]
[True, False, False, True]
```

De manière plus générale que ces premiers exemples, les éléments sont donnés sous forme d'expressions qui sont évaluées :

```python
>>> l = [3 * 14, 42 // 7]
>>> l
[42, 6]
>>> [3 < 14, '3' < '14', 3.14 < pi, type(pi) == float]
[True, False, True, True]
```

Une liste peut ne contenir qu'un unique élément. On écrit logiquement :

```python
>>> singleton = [42]
>>> singleton
[42]
```

Une liste peut ne contenir aucun élément. C'est la *liste vide*.

On écrit alors :

```python
>>> []
[]
```

## Concaténation et répétition

Les opérateurs maintenant habituels de concaténation `- + -`, et de répétition `*` peuvent être utilisés sur les listes :

```python
>>> [31, 30] * 2
[31, 30, 31, 30]
>>> seq5 = ([31, 30] * 2) + [31]
>>> annee = [31, 28] + seq5 * 2
>>> annee
[31, 28, 31, 30, 31, 30, 31, 30, 31, 30, 31]
```

## Transtypage d'itérables

Il est possible de convertir un itérable en liste en utilisant la fonction prédéfinie `list()`.
Cette fonction crée une liste dont les éléments sont ceux de l'itérable.

Nous pouvons l'utiliser sur les itérables que nous connaissons, intervalles `range` et chaînes de caractères :
>>> conversion_range = list(range(5, 14))
>>> conversion_range
[5, 6, 7, 8, 9, 10, 11, 12, 13]
>>> conversion_str = list("bonjour")
>>> conversion_str
['b', 'o', 'n', 'j', 'o', 'u', 'r']

## Accéder aux éléments d'une liste

Les éléments d'une liste sont indicés. Il est donc possible d'accéder à un élément à partir de son indice.

Comme pour les chaînes de caractères, les indices débutent à 0.

De même, la fonction prédéfinie `len()` renvoie le nombre d'éléments d'une liste, et l'indice du dernier élément d'une liste `l` est `len(l)-1`.

On accède à un élément avec la même syntaxe que pour les chaînes.

On écrit donc par exemple :

>>> notes = [12.0, 10.5, 9.5, 19., 14.5]
>>> notes[1]
10.5
>>> len(notes)
5
>>> notes[4]
14.5

## Parcourir des listes

### Itérer sur les éléments d'une liste

Les listes sont des *itérables*. On peut donc les parcourir à l'aide boucle `for`.

À chaque tour de boucle, la variable d'itération sera associée à l'élément courant de la liste.

Il est par exemple possible de calculer la somme des éléments d'une liste comme ceci :

def somme(l):
    s = 0
    for x in l:
        s += x
    return s

Lors d'un appel `somme([6, 14, 22])`,

* lors du premier tour de boucle, `x` prend la valeur `6`, et le calcul de `s` produit `6`

* lors du deuxième tour de boucle, `x` prend la valeur `14`, et le calcul de `s` produit `20`

* lors du troisième et dernier tour de boucle, `x` prend la valeur `22`, et le calcul de `s` produit `42`

>>> des_nombres = [6, 14, 22]
>>> somme(des_nombres)
42

La version suivante travaille sur des chaînes de caractères :

def concatenation(l):
    s ="
    for x in l:
        s += x + ' '
    return s

et par exemple :
>>> des_mots = ["une", "liste", "Python"]
>>> concatenation(des_mots)
'une liste Python '

Itérer sur les indices des éléments d'une liste

Les éléments des listes étant accessibles par leur indice, il est également possible de parcourir les éléments d'une
liste via ces indices.

Pour parcourir l'ensemble des éléments, on fera varier les indices de 0 – inclus –, à la longue de la liste – non
incluse –.

Une autre fonction pour le calcul de la somme des éléments d'une liste peut être :

def somme_via_indice(l):
    s = 0
    for i in range(0, len(l)):
        s += l[i]
    return s

On peut alors ne parcourir que certains éléments, par exemple ceux de rang pair

def somme_rang_pair(l):
    s = 0
    for i in range(0, len(l), 2):
        s += l[i]
    return s

et écrire

>>> des_nombres = [6, 14, 22, 1, 3, 5]
>>> 6 + 22 + 3
31
>>> somme_rang_pair(des_nombres)
31

ou parcourir les éléments dans l'ordre inverse :

def concatenation_inverse(l):
    s ="
    for i in range(len(l)-1, -1, -1):
        s += l[i] + ' '
    return s

et écrire

>>> des_mots = ["une", "liste", "Python"]
>>> concatenation_inverse(des_mots)
'Python liste une '

Il est bien entendu possible de parcourir les éléments via leur indice à l'aide d'une boucle while. Cela fera l'objet
d'exercices.

Memento

* les listes sont des séquences d'éléments de types quelconques

* l'écriture littérale d'une liste est une séquence d'éléments séparés par une virgule , encadrée de crochets [ et ]

• on concatène des listes avec l'opérateur +

• on peut répéter une liste avec l'opérateur *.

• les listes sont des itérables, on les parcourt avec une boucle for

• on accède à l'élément d'indice i d'une liste l avec la syntaxe l[i].
# Modifier une liste Python

## Coup d'œil

On découvre :

* que les listes Python peuvent être modifiées

* comment changer la valeur d'un élément d'une liste, ajouter ou supprimer un élément à une liste

* ce que signifient « mutable » et « mutabilité »

## Mutabilité

Une liste Python peuvent être modifiée. Ce n'était pas le cas des structures rencontrées précédemment. On dit que les listes sont *mutables*.

Cette mutabilité sur une séquence de valeurs se manifeste par trois types de mutations :

* les *substitutions* ;

* les *insertions* ;

* les *suppressions*.

## Substitutions

Il est possible de *substituer* la valeur d'un élément d'une liste Python par une autre. La valeur de l'élément d'indice *i* d'une liste *l* peut être remplacée par une valeur *v*. On écrit :

`l[i] = v`

Cette syntaxe combine :

* l'affectation `=`, et

* l'accès l'élément d'indice *i* de `l`: `l[i]`

```python
>>> liste_cadeaux = ['pull en laine', 'console de jeux-vidéo', 'livre']
```

```python
>>> liste_cadeaux[1] = 'chaussettes'
```

```python
>>> liste_cadeaux
['pull en laine', 'chaussettes', 'livre']
```

Une substitution ne peut qu'utiliser un indice existant.

```python
>>> liste = [49, 3]
```

```python
>>> liste[2] = 404
```

```
IndexError: list assignment index out of range
```

## Insertions

Une *insertion* consiste à ajouter un élément à une séquence.

Pour une liste Python *l*, on insère un élément de valeur *e* en fin de séquence avec la *méthode append()*. On écrit :

`l.append(e)`
Cette méthode ne renvoie rien, elle ne fait que muter la liste à laquelle elle est appliquée.

```python
>>> a_reviser = ['for', 'chaînes', 'while']
>>> len(a_reviser)
3
>>> a_reviser.append('listes')
>>> len(a_reviser)
4
>>> a_reviser
['for', 'chaînes', 'while', 'listes']
```

On utilisera une liste Python vide et la méthode `append` pour construire une liste Python éléments par éléments. Par exemple, dans la fonction `produit()` ci-dessous, on souhaite construire une liste Python contenant le produit élément par élément de deux listes Python passées en paramètre :

```python
def produit(l1, l2):
    """Renvoie la liste contenant les produits des éléments de l1 et l2
    Paramètres :
        l1 (list) : liste de nombres
        l2 (list) : liste de nombres
    Valeur de retour (list) : une liste de nombres
    Contraintes : len(l1) == len(l2)
    Exemple :
        >>> produit([2, 4, 3], [1, 5, 14]) == [2, 20, 42]
        True
        """
    res = []
    for i in range(len(l1)):
        res.append(l1[i] * l2[i])
    return res
```

## Suppression

Une suppression consiste à enlever un élément d'une séquence.

On peut supprimer n'importe quel élément d'indice *k* d'une liste Python 1 en utilisant l'instruction suivante :

```python
del l[k]
```

Par exemple :

```python
>>> a_faire = ['courses', 'cuisine', 'sieste', 'repas de famille', 'révisions']
>>> len(a_faire)
5
>>> del a_faire[3]
>>> len(a_faire)
4
>>> a_faire
['courses', 'cuisine', 'sieste', 'révisions']
```

## Memento

* les listes Python sont mutables, c'est-à-dire modifiables

* on substitue la valeur de l'élément d'indice *i* d'une liste 1. avec la syntaxe `l[i] = nouvelle_valeur`.

* on ajoute un élément en fin de liste avec la méthode `append()`.

* on supprime un élément à une position donnée avec l'instruction `del`.
# Exercices niveau débutant

## Découvertes des listes

### Quelques expressions et instructions

269. Devinez la valeur de chacune des expressions, ou l'effet de chacune des instructions ci-dessous. Vérifiez ensuite la validité de votre réponse en utilisant l'interpréteur Python.

```python
l = ['lundi', 'mardi', 'mercredi', 'jeudi', 'vendredi']
l[1]
l[1][2]
len(l)
l[-1]
l[4] * 2
l[4:] * 2
l.append('samedi')
l
del l[3]
l
l[3] = 'dimanche'
l
```

Vous devriez remarquer que `l.append('samedi')`, `del l[3]` et `l[3] = 'dimanche'` ne renvoient rien.

## Mutations

270. Copiez ces lignes dans un fichier source Python.

```python
if __name__ == '__main__':
    ordre_croissant = [2, 4, 3, 6, 5, 1]
    perfide_ordre = ['dimanche', 'lundi', 'mardi', 'mercredi',
                    'jeudi', 'vendredi', 'samedi']

# Mutez ces deux listes ci-dessous
```

```python
# Vérification
assert ordre_croissant == [1, 2, 3, 4, 5, 6]
assert perfide_ordre == ['lundi', 'mardi', 'mercredi', 'jeudi',
                         'vendredi', 'samedi', 'dimanche']
import doctest
doctest.testmod()
```

Pour que votre code puisse être exécuté, vous devez **muter** les listes associées aux variables `ordre_croissant` et `perfide_ordre` de façon à ce que les expressions booléennes

* `ordre_croissant == [1, 2, 3, 4, 5, 6]`, et

* `perfide_ordre == ['lundi', 'mardi', ..., 'dimanche']`

soient toutes deux vraies.
Tant que ces deux conditions ne seront pas vérifiées, votre programme ne pourra être exécuté sans erreur...

## Recherche de maximum

Copiez le code ci-dessous.

```python
def maximum(l):
    """Renvoie la valeur des plus grands éléments de l.
    Paramètres :
        l (list) : une liste de nombres
        Valeur de retour (int ou float) : la plus grande valeur dans l
        Contraintes : à compléter !
    Exemples :
        >>> maximum([4, 4, 3, 1, 2, 1, 1, 3])
        4
        """
vmax = 0
for e in l:
    if e >(vmax:
       (vmax = e
    return(vmax
```

271. En utilisant l'exécution pas à pas (débogueur Thonny), complétez le tableau ci-dessous exprimant les valeurs de `e` et de `vmax` avant la boucle, puis en fin de chacune des itérations pour l'appel `maximum([1, 3, 4, 2])`.

```python
# +----+-------+
# | e   |(vmax |
# +----+-------+
#    |    |       avant la boucle
# +----+-------+
#    |    |       fin de première itération
# +----+-------+
#    |    |       fin de deuxième itération
# +----+-------+
#    |    |       ...
# +----+-------+
#    |    |       |
# +----+-------+
```

272. Quelle est la valeur de `maximum([-1, -3])` ? Corrigez la fonction pour obtenir une valeur correcte.

273. Quelle est la valeur de `maximum([])` ? Complétez la chaîne de documentation (`docstring`) de la fonction.

274. Définissez une fonction `minimum()` prenant en paramètre une liste et renvoyant la plus petite valeur des éléments de cette liste.

Notez que les fonctions prédéfinies `max()` et `min` que nous avons déjà rencontrées acceptent également un itérable - donc une liste - en paramètre dont elles renvoient le plus grand, respectivement le plus petit, élément.

## Compte, somme, moyenne, voire variance

275. Définissez une fonction `nombrerizulations()` paramétrée par une valeur `v` et une liste `l` qui renvoie le nombre d'occurrences de la valeur `v` parmi les éléments de `l`.

```python
>>> nombrerizulations(2, [4, 2, 6, 2, 2, 5, 4])
3
>>> nombreoccurrences(4, [4, 2, 6, 2, 2, 5, 4])
2
```

Notez que la méthode prédéfinie `list.count()` renvoie ce nombre d'occurrences d'une valeur dans une liste.

276. Définissez une fonction `somme()` renvoyant la somme des valeurs des éléments de la liste passée en paramètre.
```python
>>> somme([1, 2, 3, 4])
10
```

Notez que la fonction Python prédéfinie `sum()` renvoie cette somme des valeurs numériques d'un itérable.

277. Définissez une fonction `moyenne()` renvoyant la moyenne arithmétique des valeurs des éléments de la liste passée en paramètre.

278. La variance $V$ d'une séquence $x_1, x_2, ..., x_n$ est définie par $V = \frac{1}{n} \sum_{i=1}^{n} (x_i - m)^2$ où $m$ est la moyenne de $x_1, x_2, ..., x_n$.

Définissez une fonction `variance()` renvoyant la variance des éléments de la liste passée en paramètre.

## Positivons

Pour chacune des questions suivantes, méditez sur l'usage d'une boucle `for` ou d'une boucle `while` avant d'écrire le code des fonctions.

279. Définissez un prédicat `tous_positifs()` renvoyant `True` si et seulement si la liste passée en paramètre ne contient que des éléments positifs ou nuls.

280. Définissez un prédicat `au.moins_un_positif()` renvoyant `True` si et seulement si la liste passée en paramètre contient au moins un élément positif ou nul.

281. Définissez une fonction `nombre_positifs()` renvoyant le nombre d'éléments positifs de la liste passée en paramètre.

282. Définissez une fonction `filtre_positifs()` renvoyant la liste des éléments positifs ou nuls de la liste passée en paramètre.

```python
>>> filtre_positifs([0, -1, -5, 2, 8, -13])
[0, 2, 8]
```

## Séquences

### Séquence croissante

283. Définissez un prédicat `est_croissante()` paramétré par une liste et renvoyant `True` si et seulement si cette liste est croissante.

```python
>>> est_croissante([1, 2, 4])
True
>>> est_croissante(["un", "deux", "quatre"])
False
>>> est_croissante([])
True
```

### Suite arithmétique-géométrique

Soit $u$ la suite définie par récurrence.

$$ \begin{cases} u_0 = 1 \\ u_{n+1} = 2u_n + 3 \end{cases} $$

284. Définissez une fonction `suite_partielle` paramétrée par un entier $n$ et renvoyant la liste des $n + 1$ premiers termes de la suite $u : u_0, u_1, ..., u_{n-1}$ et $u_n$.
# Exercices niveau intermédiaire

## Recherche d'extrema

285. Définissez une fonction `extrema()` renvoyant une liste contenant la plus petite valeur et la plus grande valeur de la liste passée en paramètre.
Il est possible de proposer une implantation qui ne parcourt qu'une fois la liste paramètre.

```python
>>> animaux = ["cheval", "autruche", "tigre", "zèbre", "fourmi"]
>>> extrema(animaux)
['autruche', 'zèbre']
```

286. Définissez une fonction `moyenne_sans_extrema()` renvoyant la moyenne des valeurs non extrêmes d'une liste de nombres passée en paramètre.

```python
>>> l = [45.0, 95.0, 95.0, 40.0, 39.0, 3.0, 44.0, 95.0, 42.0]
>>> extrema(l)
[3.0, 95.0]
>>> moyenne_sans_extrema(l) == moyenne([45.0, 40.0, 39.0, 44.0, 42.0])
True
```

287. Une version optimisée de la fonction `extrema()` peut utiliser le principe suivant pour minimiser le nombre de comparaisons :

* soient deux éléments de la liste et un minimum et maximum actuels

* pour trouver le minimum et maximum de ces quatre valeurs

- comparer les deux éléments entre-eux

- comparer le plus petit des éléments au minimum

- comparer le plus grand des éléments au maximum

* on a ainsi trois comparaisons plutôt que quatre

Mettez ce principe en œuvre pour proposer une nouvelle version de `extrema()`

## Autres sommes et moyennes

288. Définissez une fonction `sommes_prefixes()` renvoyant une liste contenant les sommes préfixes de la liste passée en paramètre.

```python
>>> sommes_prefixes([2, 4, 3, 1]) == [2, 2+4, 2+4+3, 2+4+3+1]
True
```

289. Définissez une fonction `moyenne_ponderee()` prenant en paramètre une liste de mesures et une liste de coefficients, et renvoyant la moyenne pondérée des mesures par les coefficients.

Par exemple, si un étudiant a obtenu respectivement les notes de 14, 15 et 11 au contrôle continu (coefficient 2), au TP (coefficient 1) et au devoir surveillé (coefficient 2), alors, sa note finale pourra être calculée par `moyenne_ponderee([14.0, 15.0, 11.0], [2, 1, 2])`.

## Préfixes, suffixes et facteurs

290. Définissez deux fonctions `prefixes()` et `suffixes()` renvoyant respectivement la liste des préfixes, et la liste des suffixes, de la chaîne passée en paramètre.
>>> prefixes('motus')
[', 'm', 'mo', 'mot', 'motu', 'motus']
>>> suffixes('fin')
[', 'n', 'in', 'fin']

291. Définissez une fonction `facteurs()` renvoyant la liste des facteurs (sous-chaînes) de la chaîne passée en paramètre.

>>> facteurs('tot')
[', 't', 'to', 'tot', 'o', 'ot', 't']

(Il peut y avoir des répétitions de facteurs.)

## Ranges et mélanges

292. Proposez une fonction `melange(n)` qui produit une permutation des valeurs entières de `range(n)`.

Le principe suivant permet de construire une telle liste :

* à partir de la liste `a_vider` des entiers de l'intervalle `range(n)`

* construire élément par élément une liste en

- choisissant au hasard un des éléments restant de `a_vider`

- ajoutant cet élément à la liste en construction

- supprimant cet élément de la liste `a_vider`

- poursuivre tant que la liste `a_vider` n'est pas vide

293. Proposez une fonction `gather()` qui construit une liste à partir d'une liste de valeurs et une une liste d'indices sur cet exemple :

>>> gather(list(range(5, 12)), [2, 3, 0, 6])
[7, 8, 5, 11]
>>> gather(["William", "Jack", "Rantanplan", "Joe", "Averell"], \
         [3, 0, 1, 4])
['Joe', 'William', 'Jack', 'Averell']

294. Définissez une fonction `liste_melangee()` paramétrée par une liste modèle et renvoyant une nouvelle liste dont les éléments sont ceux de la liste modèle, mais dans un ordre aléatoire.
Vous utilisez par exemple les deux fonctions `melange()` et `gather` définies ci-dessus.

295. Proposez une fonction `range_a_trous(maximum, absents)` qui construit une liste de valeurs entières inférieures à `maximum` qui ne sont pas dans la liste `absents`.
Cette liste `absents` doit être triée dans l'ordre croissant.

>>> range_a_trous(12, [3, 6, 7, 9])
[0, 1, 2, 4, 5, 8, 10, 11]
>>> range_a_trous(18, list(range(12)))
[12, 13, 14, 15, 16, 17]
>>> range_a_trous(18, list(range(12)) + [15])
[12, 13, 14, 16, 17]

## Zorlangue

### Découpage et recollage

296. Définissez une fonction nommée `decoupage()` paramétrée par un caractère `c` et une chaîne `s`, et qui renvoie la liste des sous-chaînes de `s` découpée à chaque occurrence du caractère `c`.

>>> decoupage(' ', 'Il fait beau et chaud !')
['Il', 'fait', 'beau', 'et', 'chaud', '!']
>>> decoupage '@', 'prenom.nom.etu@univ-lille.fr')
['prenom.nom.etu', 'univ-lille.fr']

297. Définissez une fonction `recollage()` paramétrée par une chaîne `s` et une liste de chaînes, et qui renvoie une chaîne constituée des éléments de la liste recollés, avec la chaîne intercalée
>>> recollage(' bise ', ['Salut', 'tu', 'vas', 'bien'])
'Salut bise tu bise vas bise bien'
>>> recollage('', decoupage(' ', 'Ils viennent du bout du monde'))
'Ils viennent dubout du monde'

« Eviv Bulgroz »

298. Définissez une fonction indices_majuscules() paramétrée par une chaîne et renvoyant la liste des indices des majuscules dans cette chaîne.

299. Définissez une fonction miroir_casse() paramétrée par une chaîne mot, et renvoyant la chaîne constituée des caractères de mot, mais dans l'autre sens. De plus, les indices des lettres majuscules ne doivent pas changer. On suppose que mot est constituée uniquement de lettres.

>>> miroir_casse('Zorglub')
'Bulgroz'
>>> miroir_casse('UnivLille')
'ElliLvinu'

300. Définissez une fonction zorglangue() paramétrée par une chaîne s (ne contenant que des lettres et des espaces), et renvoyant cette chaîne traduite en zorlgangue (voir l'article Wikipédia fr.wikipedia.org/wiki/Zorglangue)

>>> zorlangue('Vive Zorglub')
'Eviv Bulgroz'

Remarquez que cette fonction peut aussi traduire la zorglangue :

>>> zorglangue('Esod mumixam')
'Dose maximum'
# Exercices niveau confirmé

## Indices des extrema et médiane

301. Définissez une fonction `i_extrema()` sur le même principe que la fonction `extrema()` précédemment définie, et qui renvoie la liste des indices du minimum et du maximum d'une liste donnée.

```python
>>> animaux = ["cheval", "autruche", "tigre", "zèbre", "fourmi"]
>>> i_extrema(animaux)
[1, 3]
```

302. Définissez une fonction `indices_maxima()` qui renvoie la liste des indices des occurrences de la valeur maximale des éléments de la liste de nombres passée en paramètre.

```python
>>> indice_maxima([2, 4, 3, 4, 1])
[1, 3]
```

303. Définissez de même une fonction `indices_minima()`.

304. Définissez une fonction `mediane()` qui renvoie la valeur médiane des éléments de la liste de nombres passée en paramètre.

Il est possible de procéder ainsi :

* copiez dans une variable locale la liste de nombres passée en paramètre.

* tant qu'il y a trois nombres ou plus dans cette copie, supprimez un minimum et un maximum de cette copie.

## Appliquer, filtrer, et coudre

En Python, il est possible de passer une fonction comme paramètre.

Par exemple :

```python
def carre(x):
    """Le carré d'un nombre x donné"""
    return x * x

def moitie(n):
    """La moitié d'un nombre donné"""
    return n / 2
```

```python
def double_appel(fonc, val):
    """Réalise deux appels imbriqués à la fonction fonc avec le paramètre val.
    Exemple :
    >>> double_appel(carre, 3)
    81
    >>> double_appel(moitie, 16)
    4.0
    """
    tmp = fonc(val)
    res = fonc(tmp)
    return res
```

305. Définissez une fonction `appliquer()` paramétrée par une fonction `fonc` et une liste `l` et qui renvoie la liste des éléments de `l` auxquels a été appliquée la fonction `fonc`.
```python
>>> appliquer(carre, [1, 5, 9, -1])
[1, 25, 81, 1]
```

306. Définissez une fonction `filtrer()` paramétrée par un prédicat `p` et une liste `l` et renvoyant la liste des éléments de `l` satisfaisant `p`.

```python
>>> def est_pair(n):
...     return n % 2 == 0
>>> filtrer est_pair, [4, 4, 3, 4, 6, 1, 7])
[4, 4, 4, 6]
```

307. Définissez une fonction `coudre()` paramétrée par une fonction `f` à deux paramètres, une liste `l1` et une liste `l2` et renvoyant la liste de l'application de `f` à chaque couple d'éléments de `l1` et de `l2` de même indice.

```python
>>> def addition(x, y):
...     return x+y
>>> coudre(addition, [10, 30, 40], [3, 6, 2])
[13, 36, 42]
```

# Formatage et censure (épisode 2)

## Formatage (épisode 2)

Dans un but de remplissages de messages ou formulaires automatiques, on souhaiterait utiliser une fonction permettant de construire une chaîne à partir d'un modèle et d'une liste de chaînes de substitution.

```python
>>> format2('Bonjour {2} {1} !', ['David', 'Vincent', 'Monsieur'])
'Bonjour Monsieur Vincent !'
>>> format2('Cher {0} de {1}', qu'aimez-vous faire à {1} !', ['Marinette', 'Le Havre'])
'Cher Marinette de Le Havre, qu'aimez-vous faire à Le Havre !'
```

308. Définissez une fonction `format2()`, paramétrée par une chaîne de modèle et une liste de chaînes de substitution qui renvoie une chaîne obtenue en remplaçant toutes les occurrences des sous-chaînes de la forme `'{i}'` (avec i un entier) par les chaînes d'indice i de la liste.

Il est possible d'utiliser la fonction `int()` qui, entre autres, convertit une chaîne en entier.

**TODO** Clarifier ! Yes :-)

## Censure (épisode 2)

On souhaite pouvoir censurer une sous-chaîne dans un texte donné.

```python
>>> censure2('La fonction `print()` peut être pratique.', ['input', 'print'])
'La fonction `*****()` peut être pratique.'
>>> censure1('Bal tragique à Colombey : 1 mort', list('aeiou'))
'B*l tr*g*g** à C*l*mb*y : 1 m*rt'
```

309. Définissez une fonction `censure2()`, paramétrée par chaîne et une liste de chaînes, et renvoyant le texte de la première, en remplaçant chacune des occurrences de toutes les chaînes de la seconde par autant d'étoiles * que nécessaire.
# Exercices complémentaires

310. Proposez un traducteur en / de Leet Speak
fr.wikipedia.org/wiki/Leet_speak

311. Proposez un analyseur qui décompose les informations contenues dans une URL
fr.wikipedia.org/wiki/UniformResourceLocator#Fonctionnement

312. Proposez un traducteur du Fourchelangue
https://pydefis.callicode.fr/defis/Fourchelangue/txt

313. Proposez un traducteur d'émoticônes typographiques occidentales en style nippon
https://fr.wikipedia.org/wiki/%C3%89motic%C3%B4ne#Liste_des_%C3%A9motic%C3%B4nes Typographiques

314. Proposez un Jeu du pendu
fr.wikipedia.org/wiki/Le_Pendu_(jeu)

315. Proposez un programme qui filtre une séquence de lettres : les voyelles en début, les consonnes en fin

316. Proposez un programme qui filtre une séquence de caractères : les voyelles en début, les consonnes en fin, et les autres caractères au milieu

Pour chacun de ces programmes, vous veillerez à

• définir le problème

– on pourra commencer par une version simplifiée

• décomposer le problème en sous-problèmes

• spécifier les fonctions nécessaires à la réalisation de ces sous-problèmes :

– nom bien choisi

– nombre et noms des paramètres, leur type

– type de retour de la fonction

– contraintes d'utilisation

– docstring

– exemples d'utilisation

• écrire le corps des fonctions

– pour chaque fonction, on suppose que les autres fonctions existent !

Une approche progressive est préférable. Pour un problème donné

• n'hésitez pas dans un premier temps à simplifier le problème

• une fois une version mise au point pour ce problème, relâchez les contraintes qui avaient été fixées dans un premier temps

• itérer cette méthode pour aboutir à une version finale

N'oubliez pas documenter de votre approche. Expliquez en particulier quelles sont les différentes versions qui ont été développées.
# 10. Listes Python - 2de partie
# Aliasing de listes, valeurs mutables

## Coup d'œil

On découvre :

* la vraie nature des variables

* la notion de référence vers une valeur

* le phénomène d'aliasing

* les conséquences de l'aliasing lors de la manipulation de listes Python qui sont mutables

* l'utilisation de Python Tutor pour visualiser l'état mémoire

## Les variables sont des références

Nous avons vu dès le début de ce cours que :

* une variable associe un nom à une valeur, et que

* l'opération d'affectation `a = b` permet de lier une valeur à la variable

Nous allons approfondir cette première présentation des variables.

Ce que nous avons vu jusque maintenant n'est pas faux. C'est une approximation suffisante pour bien des situations : cela nous a permis de comprendre les programmes écrits jusque maintenant !

Et donc plus précisément nous allons découvrir que :

* une variable associe un nom à une référence à une valeur

## État de la mémoire illustré par Python Tutor

L'état de la mémoire est l'ensemble des associations variable-valeur.

Nous allons utiliser des schémas générés sur le site Python Tutor [pythontutor.com](http://pythontutor.com/) pour illustrer cet état de la mémoire.

L'illustration ci-dessous représente l'état mémoire suite à l'exécution de l'affectation `a = 3` :

<figure><img src="image_22.png" /></figure>

On y distingue :

* une suite d'instructions Python en partie gauche

* l'état de la mémoire en partie droite :

- lui-même divisé en deux zones *Frames* et *Objects*

- la zone *Frames* correspond à différents blocs dans lesquels apparaîtront les variables

- la zone *Objects* est une représentation des valeurs qui sont en mémoire

Cet état de la mémoire est celui après l'exécution de l'affectation `a = 3`.

On remarque particulièrement :

* la variable `a` qui référence la valeur `3`
* la flèche qui lie la variable à la valeur référencée.

# Évolution de l'état de la mémoire

## Quelques affectations

Observons l'état de la mémoire suite à l'exécution des deux affectations

<figure><img src="image_23.png" /></figure>

Chacune des variables associe un nom et une référence à une valeur.

Il est particulièrement notable que les deux références associées à a et à b sont égales : elles désignent la même valeur 3.

Procédons à une nouvelle affectation de a :

<figure><img src="image_24.png" /></figure>

Le nom b reste associé à une référence qui désigne la valeur 3.

Le nom a est associé à un nouvelle référence qui désigne la valeur 5.

On obtient le même résultat avec une affectation $a = a + 2$ qui est exécutée ainsi :

* l'expression $a + 2$ est évaluée :

- elle vaut 5

- c'est une nouvelle valeur, elle apparaît comme telle

* l'affectation modifie l'association entre le nom a et une référence à sa valeur :

- la variable référence maintenant cette nouvelle valeur 5'

<figure><img src="image_25.png" /></figure>

## Avec des chaînes de caractères

Nous pouvons réaliser la même suite d'instructions avec des chaînes de caractères.

Nous allons voir apparaître des valeurs de type `str` dans la mémoire.

<figure><img src="image_26.png" /></figure>

Les deux variables sont des références vers la même valeur "abc".

Procédons à l'affectation $s = s + 'd'$. Elle est exécutée en deux étapes :

* l'expression $s + 'd'$ est évaluée :

- elle vaut "abcd"

- c'est une nouvelle valeur, elle apparaît comme telle

* l'affectation modifie l'association entre le nom s et une référence à sa valeur :

- la variable référence maintenant cette nouvelle valeur "abcd'
<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

## Avec des listes

Nous pouvons réaliser la même suite d'instructions avec des listes.

Nous allons voir apparaître des valeurs de type `list` dans la mémoire. Par exemple :

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

La valeur de chacun des quatre éléments de la liste `['a', 'b', 'c', 'd']` apparaît avec son indice.

Les deux variables `l` et `m` référencent cette même liste.

Comme pour les nombres ou les chaînes de caractères, une nouvelle affectation `l = l + ['d']` de la variable `l` est exécutée en deux étapes :

* l'expression `l + ['d']` est évaluée

- elle vaut `['a', 'b', 'c', 'd']`

- c'est une nouvelle valeur, elle apparaît comme telle

* l'affectation modifie l'association entre le nom `l` et une référence à sa valeur

- la variable référence maintenant cette nouvelle valeur `['a', 'b', 'c', 'd']`

<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

## Une référence est un partage

Résumons.

Nous savons maintenant qu'une variable associe un nom à une référence vers une valeur.

Deux variables différentes peuvent donc associer deux noms à une référence vers une même valeur.

Ces deux variables partagent cette valeur.

## Modifier des valeurs

Nous connaissons plusieurs types de valeurs : les nombres `int` et `float`, les chaînes de caractères `str`, les intervalles `range`, et les listes `list`.

Les nombres, les chaînes et les intervalles sont des valeurs qui ne peuvent être modifiées :

* on ne peut que les utiliser dans des expressions

* ces expressions produisent de nouvelles valeurs.

On dit que les valeurs de ces types ne sont pas mutables.

À l'inverse, les listes sont des valeurs qui peuvent être modifiées. Il est possible :
* de modifier un élément d'une liste

* d'ajouter un élément à une liste

* de supprimer un élément d'une liste.

On dit que les listes sont *mutables*.

Le partage de références vers des valeurs mutables est à étudier particulièrement : la modification de la valeur impactera l'ensemble des références vers cette valeur !

Ce phénomène est aussi appelé aliasing : plusieurs références permettent d'accéder à une même valeur.

# Partage de listes, valeurs mutables

## Deux affectations

Reprenons notre exemple de manipulation de listes. Suite aux deux affectations, l'état de la mémoire est le suivant :

<figure><img src="image_33.png" /></figure>

Les deux variables `l` et `m` référencent la même valeur `list`.

## Substitution

Modifions cette valeur en substituant la valeur `'e'` à l'élément d'indice `2` de la liste. Cela est par exemple possible en écrivant `l[2] = 'e'` :

<figure><img src="image_34.png" /></figure>

Les deux variables `l` et `m` référencent toujours cette même liste qui a été modifiée.

La valeur référencée par la variable `m` a donc été modifiée.

L'élément d'indice `2` de cette variable `m`, `m[2]`, vaut `'e'`.

Les autres moyens de modifier une valeur de type liste produiront le même effet.

## Insertion

Ajoutons un élément à cette liste.

Cela peut être réalisé au choix par une opération sur `l` ou une opération sur `m`.

Choisissons d'utiliser `m('z')`.

<figure><img src="image_35.png" /></figure>

Suite à l'exécution de l'instruction `m.append('z')`, les deux variables `l` et `m` référencent toujours cette même liste qui a été modifiée.

La liste référencée par `l` est constituée de 5 éléments dont le `'z'` final.
## Suppression

Supprimons maintenant un élément à cette liste.

À nouveau, cela peut être réalisé au choix par une opération sur l ou une opération sur m.

Choisissons d'utiliser l.

<figure><img src="image_36.png" /></figure>

Suite à l'exécution de l'instruction `del l[2]`, les deux variables l et m référencent toujours cette même liste qui a de nouveau été modifiée.

La liste référencée par m est constitué de 4 éléments, le 'c' a disparu.

## Aliasing de valeurs mutables

Le phénomène d'aliasing – plusieurs références permettent d'accéder à une même valeur – doit être maîtrisé quand les valeurs référencées sont mutables.

La modification de la valeur via l'une des références est partagée par l'ensemble des références à cette valeur.

## Python Tutor live

Retrouvez le code présenté ici sur le site Python Tutor

* page Python Tutor [pythontutor.com/live.html#code=...]

Exécutez le code pas à pas, modifiez-le, et observez l'évolution de l'état de la mémoire.

## Memento

* une variable associe un nom et une référence à une valeur

* des variables différentes peuvent référencer une même valeur. C'est un phénomène d'aliasing

* l'aliasing de valeurs mutables – les listes – doit être maîtrisé lors de la modification de telles valeurs
# Copier une liste

## Coup d'œil

On découvre :

* pourquoi la copie de valeurs listes Python est indispensable

* comment réaliser une copie d'une liste Python

## Nécessité de copier une liste

Les valeurs de type `list` sont mutables : les opérations de substitution d'un élément, insertion ou suppression d'un élément modifie la valeur.

On peut vouloir garder l'ancienne valeur de la liste et produire une *nouvelle* valeur par une telle modification. Par exemple ne garder dans une liste que les seuls nombres positifs, sans détruire la liste originale.

On sait qu'une simple affectation dans une variable ne produit pas une copie mais un partage de référence :

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

## Différentes manières de copier une liste

Les manières de créer une nouvelle liste, copie d'une liste donnée, sont nombreuses. Nous en découvrons quelques-unes ici.

### Avec la fonction prédéfinie `list()`

La fonction prédéfinie `list()` construit une liste à partir d'un itérable. Nous l'avons utilisé pour construire une liste à partir d'un intervalle `range` ou d'une chaîne de caractères.

Cette fonction permet aussi de construire une liste à partir d'une liste. Le résultat est une nouvelle liste formée des mêmes éléments.

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>
## Par insertions successives d'éléments

Nous savons créer une liste élément par élément à partir d'une liste vide.

Nous pouvons créer une copie d'une liste en insérant un à un les éléments à l'aide de la méthode `append()` :

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

## En tant que tranche complète

Nous pouvons obtenir une structure formée d'une tranche des éléments d'une structure indiquable avec la syntaxe `[ imin : imax ]`.

Les bornes inférieure `imin` et supérieure `imax` peuvent être omises. Leur valeur par défaut est le plus petit, respectivement le plus grand indice de la structure.

Une copie d'une liste peut donc être créée comme une tranche du premier au dernier élément d'une liste :

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

## Par copie élément par élément

Nous savons créer une liste d'une taille donnée, par exemple par répétition d'une liste d'un élément.

La liste `[0] * n` est une liste de n zéros.

Nous pouvons ensuite copier un à un chacun des éléments de la liste originelle dans cette nouvelle liste à l'aide d'une boucle `for` qui parcourt les indices des listes :

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

La valeur initiale de chacun des éléments de la liste créée importe peu. Nous pouvons par exemple utiliser la valeur `None` de Python, valeur qui représente habituellement l'absence de valeur (oui..) :

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

## Avec la méthode `list.copy()`

Python fournit une méthode `s.copy()` sur les valeurs de type `list` qui crée une copie de s :
<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

## Avec la fonction copy() de la bibliothèque copy

La bibliothèque Python `copy` fournit plusieurs fonctions pour réaliser des copies de valeurs mutables.

Nous pouvons utiliser la fonction `copy()` de cette bibliothèque :

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

## Python Tutor live

Retrouvez le code présenté ici sur le site Python Tutor

* page Python Tutor [pythontutor.com/live.html#code=...]

Exécutez le code pas à pas, modifiez-le, et observez l'évolution de l'état de la mémoire.

## Choisir comment créer une copie d'une liste

L'ensemble des manières de copier une liste Python sont équivalentes : elles produisent toutes le même résultat ; leurs performances ne sont pas si différentes.

Il existe même d'autres manières de faire que nous n'avons pas vues.

L'utilisation des fonctions `list()` ou `copy()` est courante.

Sa syntaxe bizarre est parfois reprochée à la « copie par tranche » `lst[:]`.

Néanmoins cette manière de faire est la plus rapide.

La méthode `list.copy()` a été introduite relativement récemment dans Python pour conjuguer une meilleure lisibilité et cette efficacité : elle est implémentée de la même manière.

Copier une liste par `append()` successifs d'éléments permet aussi de ne copier que certains éléments de la liste originelle : on ajoute une instruction conditionnelle au sein de la boucle `for`.

Enfin, la fonction `copy()` de la bibliothèque `copy` a été présentée parce que cette bibliothèque fournit également d'autres fonctions que nous découvrirons plus tard.

Cela dit, faites comme il vous plaira !

## Memento

* les listes sont des valeurs mutables : réaliser une copie d'une telle valeur permet de travailler sur cette copie sans modifier la liste

* des multiples manières de créer une copie sont possibles, elles sont équivalentes
# Copier ou muter une liste ?

## Coup d'œil

On découvre :

* que deux approches sont possibles pour définir des fonctions modifiant des listes

* comment mettre en œuvre chacune des approches

## Comment trier une liste Python

Soit une liste donc nous désirons trier les éléments par ordre croissant

<figure><img src="image_53.png" /></figure>

Deux approches différentes sont possibles :

* modifier la valeur associée à l'élément

* produire une nouvelle valeur, une nouvelle liste

Python fournit une fonction et une méthode correspondant à chacune des manière de faire.

## Muter pour trier

Python propose une méthode applicable aux listes qui permet de trier leurs éléments.

Cette méthode modifie la liste à laquelle elle est appliquée :

<figure><img src="image_54.png" /></figure>

Cette méthode ne renvoie pas de valeur.

On n'écrira donc pas `s = l.sort()` pour espérer récupérer la liste triée. L'exécution de cette instruction provoque le résultat suivant :

<figure><img src="image_55.png" /></figure>

La variable `s` est associée à la valeur `None`, cette valeur qui indique l'absence de valeur.

## Copier pour trier

Python propose aussi une fonction qui renvoie une nouvelle valeur triée :
<figure><img src="image_56.png" /></figure>

La liste originelle n'est pas modifiée.

<figure><img src="image_57.png" /></figure>

## Muter ou copier

L'utilisation de la méthode `sort()` mute la liste. L'utilisation de la fonction `sorted()` copie la liste.

Si on n'a plus besoin de la liste originelle, la première méthode peut être employée. La seconde méthode est d'un usage plus universel.

## Comment “positiver” une liste

L'exemple précédent met en évidence deux approches basées sur l'utilisation de fonctions ou méthodes prédéfinies de Python.

Voyons comment proposer nos propres fonctions pour une situation analogue.

Soit une liste de nombres, nous désirons remplacer les valeurs négatives par leur opposé.

Il est possible de proposer :

* une fonction qui modifie la liste

* une fonction qui renvoie une nouvelle liste

## Muter pour positiver

Proposons une fonction `positiver()` qui accepte une liste de nombres en paramètre, et remplace chacune des valeurs négatives par leur opposée.

Cette fonction ne renverra aucune valeur. C'est une procédure. Son exécution va modifier la valeur passée en paramètre :

*(on se passe de docstring pour simplifier la présentation)*

```python
def positiver(l):
    for i in range(len(l)):
        if l[i] < 0:
            l[i] = -l[i]
```

Soit la liste `[1, -2, 4, -3, 0]`

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /></figure>

Cette valeur est modifiée suite à un appel à `positiver()` :
Write code in Python 3.6

<figure><img src="image_60.png" /></figure>

(drag lower right corner to resize code editor)

<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

## Copier pour positiver

Proposons une fonction positivee() qui accepte une liste de nombres en paramètre, et renvoie sa « positivee », liste dans laquelle chacune des valeurs négatives est remplacée par son opposée.

Son exécution ne va pas modifier la liste passée en paramètre.

Il s'agit : 1- de copier la valeur de la liste paramètre, puis 2- de réaliser les modifications nécessaires des éléments de cette copie :

(on se passe de docstring pour simplifier la présentation)

```python
def positivee(l):
    res = l.copy()
    for i in range(len(res)):
        if res[i] < 0:
            res[i] = -res[i]
    return res
```

Soit à nouveau la liste `[1, -2, 4, -3, 0]`

Write code in Python 3.6

<figure><img src="image_63.png" /></figure>

(drag lower right corner to resize code editor)

<figure><img src="image_64.png" /></figure>

<figure><img src="image_65.png" /></figure>

Suite à un appel à positivee(), une liste résultat est créée et la valeur originelle non modifiée :

Write code in Python 3.6

<figure><img src="image_66.png" /></figure>

(drag lower right corner to resize code editor)

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

## Muter ou copier : deux approches

Deux approches sont donc utilisées pour obtenir une liste modifiée à partir d'une valeur originelle :

1. proposer une procédure

* qui modifie la valeur passée en paramètre

* et ne renvoie rien
On parle de « *modification en place* », ou d'« *effet de bords* ».

On parle aussi d'approche *procédurale* : l'exécution d'une procédure modifie l'état de la mémoire, sans renvoyer de valeur.

2. proposer une fonction

* qui renvoie une nouvelle liste, modification du paramètre.

On parle d'approche *fonctionnelle* : les valeurs ne sont pas modifiées, mais de nouvelles valeurs sont produites.

Il est important de bien préciser – par exemple dans la docstring – quelle approche est choisie quand on développe une fonction travaillant sur des listes.

Il en sera de même pour les autres valeurs mutables que nous rencontrerons plus tard.

Ces deux approches fondent également des paradigmes de programmation : on parle de programmation procédurale ou impérative d'un côté, de programmation fonctionnelle de l'autre.

## Memento

* l'approche dite procédurale modifie les valeurs de ses paramètres en faisant usage de mutations de listes

* l'approche dite fonctionnelle renvoie de nouvelles valeurs en faisant usage de copies de listes

* il est essentiel de bien documenter l'approche utilisée
# Exercices niveau débutant

## Suivre les alias

Soit la suite d'instructions suivantes :

```
a = 1
b = [a, 2*a]
c = b
d = b + [a]
b.append(4)
a = 42
b[1] = 42
e = c[1] == d[1]
```

```
c = d
d[1] = 41
f = c[1] == d[1]
```

```
b = c + d
b[2] = 14
g = b[2] == c[2]
```

```
del c[1]
h = d[0] == d[1]
```

317. Dessiner les valeurs associées à chacune des variables à la manière des schémas Python Tutor. Vérifiez ensuite votre proposition via une exécution pas à pas sur la page Python Tutor pythontutor.com/live.html#co

## Retour sur quelques fonctions

Dans cet exercice, faites bien attention à écrire des procédures qui **mutent** les listes passées en paramètres et ne renvoient rien.

318. Définissez une procédure `reflechit()` qui mute la liste passée en paramètre de façon à ce que les éléments de cette liste soient dans l'ordre inverse.

```
>>> l = [2, 5, 4, 3]
>>> reflechit(l)
>>> l
[3, 4, 5, 2]
```

319. Définissez une procédure `filtre_positifs()` qui supprime de la liste passée en paramètre tous les entiers strictement négatifs.

```
>>> l = [2, -4, 3, 0, 5, -1]
>>> filtre_positifs(l)
>>> l
[2, 3, 0, 5]
```

320. Définissez une procédure `cumule()` qui mute les éléments d'une liste de nombre pour que celle-ci devienne la somme cumulée de l'originale.
```python
>>> l = [2, 4, 5, 1]
>>> cumule(l)
>>> l == [2, 2+4, 2+4+5, 2+4+5+1]
True
```

321. Définissez une procédure `melange()` qui permute aléatoirement les éléments d'une liste de longueur *n*. Cette fois-ci, on propose, de tirer *n* fois un indice au hasard dans l'intervalle $\{0, 1, 2, ..., n-1\}$, de supprimer de la liste l'élément associé à cet indice, et de l'ajouter en fin de liste.

```python
>>> l = [1, 2, 3, 4]
>>> melange(l)
>>> l
[1, 3, 4, 2]
```

## Insérer une valeur

### Insérer à une position donnée

Il s'agit d'insérer une valeur dans une liste à une position donnée, et pas nécessairement en bout de liste.

Ainsi, insérer la valeur `'loup'` en position 2 de la liste `['chou', 'chèvre', 'bâton', 'feu']` produira `['chou', 'chèvre', 'loup', 'bâton', 'feu']`.

La position d'insertion est une valeur comprise entre

* 0 : la valeur doit être insérée en début de liste

* la longueur de la liste : la valeur doit être insérée en fin de liste

322. Proposez deux variantes pour insérer une valeur dans une liste :

* une procédure dans une approche procédurale,

* une fonction dans une approche fonctionnelle.

Portez une attention particulière aux noms que vous donnerez à cette procédure et cette fonction.

### Insérer dans une liste croissante

Il s'agit maintenant d'insérer une valeur dans une liste ordonnée croissante.

La valeur sera insérée à une position telle que cette propriété de la liste soit conservée.

323. Proposez éventuellement deux variantes pour insérer une valeur dans une liste ordonnée croissante :

* une procédure dans une approche procédurale,

* une fonction dans une approche fonctionnelle.

Précisez la ou les approches choisies.

## Tri par insertion

Soit une liste de valeurs à trier.

Il est possible de procéder par insertions successives des valeurs de la liste dans la liste triée.

Ces insertions se font à l'aide des fonctions/procédures définies à l'exercice précédent.

324. Proposez, au choix, une procédure ou une fonction pour réaliser un tri par insertion d'une liste de valeurs.

## Manipuler des piles

En informatique, une pile est une structure de données qui propose trois opérations primitives :

* `empiler` qui ajoute un élément au sommet de la pile

* `dépiler` qui supprime l'élément en sommet de pile et renvoie cette valeur

* `vide` qui vérifie si la pile est vide.

Aucune autre opération n'est permise.
<figure><img src="image_69.png" /></figure>

Image Wikimedia Commons

The original上传er was 16@r at French Wikipedia., CC BY-SA 3.0
commons.wikimedia.org/wiki/File:PrimitivesPile.png

Ainsi une pile fonctionne selon le principe du dernier entré, premier sorti, comme une pile d'assiettes.

## Interface procédurale de manipulation de piles

Nous définissons une interface procédurale pour manipuler des piles à base de quatre primitives :

```python
def empiler(v, p):
    """
    Ajoute la valeur v en sommet de la pile p.
    Effet de bords : la valeur p est modifiée
    """
```

```python
def depiler(p):
    """
    Supprime la valeur en sommet de la pile p.
    Renvoie cette valeur
    Contraintes : la pile doit être non vide.
    Effet de bords : la valeur p est modifiée
    """
```

```python
def est_vide(p):
    """
    Vrai ssi la pile est vide.
    """
```

```python
def pile_vide():
    """
    La pile vide.
    """
```

## Implantation de piles

Il est possible d'utiliser une liste Python pour mettre en œuvre une pile.

On choisit par exemple de mémoriser

* la valeur en fond de pile dans le 1er élément de la liste

* la valeur en sommet de pile dans le dernier élément de la liste.
Ainsi,

* empiler une valeur revient à insérer un cette valeur en fin de liste,

* dépiler revient à supprimer le dernier élément de la liste.

Ce choix n'est connu que de la personne qui propose une implémentation des piles.
Il n'est pas connu de la personne qui va utiliser les fonctions.

325. Proposez une implémentation des primitives `empiler()`, `depiler()`.

La pile vide est une liste vide. Et donc :

* la fonction `pile_vide()` renvoit simplement cette valeur,

* le prédicat `est_vide()` compare la valeur de son paramètre avec cette valeur.

326. Proposez une implémentation des primitives `pile_vide()` et `est_vide()`.

## Des listes aux piles, et retour

Définissons deux fonctions utilitaires pour passer d'une liste à une pile, et inversement :

def pile_de_liste(l):

```python
        """
```

Une pile formée des éléments de la liste l.

La valeur l[0] en sommet de pile, la valeur l[-1] en fond de pile.

```python
        """
```

def liste_de_pile(p):

```python
        """
```

Vide la pile dans une liste l

Le fond de pile est en l[0], le sommet en fin de liste.

Retourne l.

Effet de bord : p est vide à l'issue de la fonction.

```python
        """
```

Ces deux fonctions utilitaires peuvent être écrites sans connaître la manière dont les piles sont implémentées.
Elle ne doivent utiliser que les seules primitives de l'interface définie sur les piles : `empiler()`, `depiler()`, `est_vide()`, et `pile_vide()`.

327. Proposez une définition des deux fonctions `pile_de_liste()` et `liste_de_pile(p)`:

## Piles de triage

À l'image des gares de triage nous allons utiliser des piles pour réarranger les éléments d'une liste.

Soit une liste d'entiers à réarranger de telle sorte que les entiers pairs soient au début de la liste, et les entiers impairs en fin de liste.

Il est possible de procéder ainsi :

* mettre les éléments dans une pile

* vider la pile dans deux piles, une pile des entiers pairs, et une pile des entiers impairs

* vider la pile des entiers pairs dans une nouvelle pile

* vider la pile des entiers impairs dans cette même pile

328. Proposez une fonction `triage()` qui accepte une liste d'entiers en paramètre et renvoie une nouvelle liste contenant les valeurs paires puis les valeurs impaires.

On suivra le principe présenté.

On utilisera aucune autre fonction que les primitives définies sur les piles et les deux fonctions auxiliaires de transformation depuis et vers des listes.

## Bon parenthésage

Nous avons déjà traité du bon parenthésage d'expressions. Nous n'avons considéré qu'un unique type de parenthèse.

Il s'agit ici de vérifier le bon parenthésage d'expressions pouvant comporter plusieurs types de parenthèses : ( et ), [ et ], { et }.