Exercices

Chapitre 0: Rappels

1 Prévoir les sorties de boucles

Écrire les sorties des algorithmes suivants.

for i in range(4, 7):
    print(i)

for i in range(3, 9, 2):
    print(i)

for i in range(4):
    for j in range(i):
        print(i, j)

i = 0
while i < 5:
    i = i+1
    print(i)

i = 3
while i >= 0:
    i = i - 1
    j = i
    while j >= 0:
        j = j - 1
        print(i, j)

for i in range(3):
    for j in range(i, -1, -1):
        print(i, j)

i = 3
while i > 0:
    j = i - 1
    while j < 3:
        j = j + 1
        print(i, j)
    i = i - 1

i = 3
while i > 0:
    for j in range(i):
        print(i, j)
    i = i - 1

for i in range(3, 1, -1):
   j = i 
   while j > 0:
         print(i, j)
         j = j - 1

liste = [13, 5, 7, 9, 11]
for i in range(1, len(liste)):
    print(liste[i], liste[i-1])

liste = [13, 5, 7, 9, 11]
for i in range(len(liste)- 2, -1, -1):
    print(liste[i], liste[i+1])

dict = {"a": 0, "b": 1, "c": 2}
for item in dict.items():
    print(item)

2 Dessiner des motifs avec des boucles

Écrivez un programme Python pour construire le motif suivant, en utilisant une boucle.
```
*
* *
* * *
* * * *
* * * * *
* * * *
* * *
* *
*
```
Écrivez un programme Python qui accepte un mot de l’utilisateur et l’inverse.
Écrivez un programme Python qui prend deux chiffres m (nb de lignes) et n (nb de colonnes) en entrée et génère un tableau à deux dimensions.

La valeur de l’élément dans la i-ème ligne et la j-ème colonne du tableau doit être i*j.

Exemple : Lignes = 3, Colonnes = 4 Résultat attendu : [[0, 0, 0, 0], [0, 1, 2, 3], [0, 2, 4, 6]]
Écrivez un programme Python pour afficher le motif alphabétique « E ».

Sortie attendue:
```
*****
*
*
****
*
*
*****
```
Écrivez un programme Python pour afficher le motif alphabétique « Z ».

Sortie attendue:
```
*******
     *
    *
   *
  *
 *
*******
```
Écrivez un programme Python pour construire le modèle suivant, en utilisant une boucle.

Sortie attendue:
```
1
22
333
4444
55555
666666
7777777
88888888
999999999
```
Écrivez un programme Python pour construire le modèle suivant, en utilisant une boucle.

Sortie attendue:
```
999999999
88888888
7777777
666666
55555
4444
333
22
1
```
Écrivez un programme Python pour construire le modèle suivant, en utilisant une boucle.

Sortie attendue:
```
111111111
 22222222
  3333333
   444444
    55555
     6666
      777
       88
        9
```

Écrivez un programme Python pour construire le modèle suivant, en utilisant une boucle.

Sortie attendue:

1                1
22              22
333            333
4444          4444
55555        55555
666666      666666
7777777    7777777
88888888  88888888
999999999999999999

3 Vérifier qu’une liste est triée

Écrire le code d’une fonction appelée is_sorted qui prend en paramètres une liste et qui renvoie True si la liste est triée et False sinon.

Écrire en python le code de la fonction en la prototypant.
Proposer quelques tests d’assertion en pensant aux cas limites : liste vide, liste triée, éléments égaux…
Évaluer la complexité de l’algorithme dans le pire des cas.

4 Étude du tri par insertion

On donne ci-dessous le code Python du tri par insertion :

def tri_insertion(t):
    n = len(t)
    for i in range(1, n):
        # ICI
        x = t[i]
        j = i
        while j > 0 and t[j-1] > x:
            t[j] = t[j-1]
            j = j - 1
        t[j] = x
        # LA
    return t

4.1 Compréhension de l’algorithme

Écrire le prototype de cette fonction.

On va étudier l’appel de la fonction avec comme argument [11, 25, 12, 22, 64].

Écrire l’instruction permettant d’exécuter l’appel de la fonction avec la liste précédente.
Que représente n? Quelle est sa valeur?
Quelles seront les valeurs prises par i données par l’instruction for i in range(1, n)?
Dans un tableau, donner les états successifs du tableau aux points ICI et LA pour tous les tours de la boucle externe(for).
Expliquer le rôle de la boucle interne(while).

4.2 Étude de la complexité

Rappeler la définition de la complexité.
Montrer que pour tout entier $n$ , la somme des entiers de 1 à $n$ vaut : $S=1+2+3+\cdots +(n-1)+n=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}.$ (voir cette animation si nécessaire.)
Calculer la complexité du tri par insertion proposé.
En déduire qu’il s’agit d’un algorithme de complexité quadratique: $O(n^2)$ .

4.3 Correction de l’algorithme

Etablir la correction de l’algorithme. On rappelle que pour prouver la correction nous devons montrer les trois points suivants:

Initialisation: L’invariant est vrai avant la première itération.
Conservation: si l’invariant est vrai avant une itération, il restera vrai après l’itération.
Terminaison: la boucle se termine et nous donne le résultat attendu.