Feuille d’exercices 2

Contenu

Feuille d’exercices 2#

Objectifs

Listes
Boucles
Compléments sur les fonctions

Exercice 1 : manipulation élémentaire de liste#

Question 1 : Effectuer successivement les étapes suivantes :

Affecter à une variable nommée L une liste vide.
Ajouter l’entier \(3\) à la fin de la liste L.
Insérer l’entier \(-2\) au début de la liste L.
Afficher la liste L.
Si le second élément de la liste L est strictement positif, alors afficher « Positif ».

L = []
L.append(3)
L.insert(0, -2)
print(L)
if L[1] > 0:
    print("Positif")

[-2, 3]
Positif

Question 2 : Créer une liste jours contenant les noms des \(7\) jours de la semaine (chacun exprimé sous la forme d’une chaîne de caractères).

jours = ["lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi", "dimanche"]

Question 3 : En utilisant la liste jours, afficher le troisième jour de la semaine.

jours[2]

'mercredi'

Rappelons que pour connaître la longueur d’une chaîne de caractère, on utilise la fonction len. Par exemple, len("bonjour") vaut \(7\).

Question 4 : En parcourant la liste jours avec une boucle for, et en effectuant un test à chaque tour de boucle, afficher les jours de la semaine qui sont formés de \(5\) lettres exactement.

for j in jours:
    if (len(j) == 5):
        print(j)

lundi
mardi
jeudi

Exercice 2 : boucle `for` et itérateur `range`#

Question 1 : À l’aide d’une boucle for et du mot-clef range, afficher successivement les nombres entiers allant de \(-3\) à \(8\) (inclus).

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

Question 2 : À l’aide d’une boucle for et du mot-clef range, afficher, dans l’ordre décroissant, l’ensemble des nombres divisibles par \(5\) qui sont compris entre \(400\) et \(500\) (bornes incluses).

for i in range(500, 399, -5):
    print(i)

Question 3 : À l’aide d’une boucle for et du mot-clef range, calculer la somme des entiers naturels naturels impairs inférieurs à \(200\).

somme = 0
for n in range(1, 200, 2):
    somme += n
somme

Question 4 (plus difficile) : À l’aide d’une boucle for, du mot-clef range et l’opérateur * qui permet de copier plusieurs fois le même caractère, reproduire la figure suivante, mais avec un triangle de taille 20x20 :

**********
*********
********
*******
******
*****
****
***
**
*

for j in range(20, 0, -1):
    s = "*" * j
    print(s)

********************
*******************
******************
*****************
****************
***************
**************
*************
************
***********
**********
*********
********
*******
******
*****
****
***
**
*

Exercice 3 : boucle `while`#

Question 1 : À l’aide d’une boucle while (donc, sans boucle for ni mot-clef range), afficher les entiers pairs compris entre \(16\) (inclus) et \(26\) (exclus).

i = 16
while (i < 26):
    print(i)
    i += 2

Question 2 : À l’aide d’une boucle while, afficher les puissances de \(2\) inférieures à \(1.000.000\) (en partant de \(2^0 = 1\)).

i = 1
while i <= 1000000:
    print(i)
    i *= 2

Question 3 : Dans la cellule suivante, une fonction ma_fonction est écrite pour calculer le maximum d’une liste L. Décommentez la dernière ligne, exécutez la cellule, puis observez ce qui est affiché. Essayez ensuite de corriger l’erreur pour obtenir le bon résultat.

def ma_fonction(L):
    m = 0
    i = 0
    n = len(L)
    while i <= n:
        if L[i] > m:
            m = L[i]
        i += 1
    return m

# ma_fonction([13, 12, 42, -37])

def ma_fonction(L):
    m = 0
    i = 0
    n = len(L)
    while i <= n:
        if L[i] > m:
            m = L[i]
        i += 1
    return m

ma_fonction([13, 12, 42, -37])

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[12], line 11
      8         i += 1
      9     return m
---> 11 ma_fonction([13, 12, 42, -37])

Cell In[12], line 6, in ma_fonction(L)
      4 n = len(L)
      5 while i <= n:
----> 6     if L[i] > m:
      7         m = L[i]
      8     i += 1

IndexError: list index out of range

On obtient une erreur de dépassement d’indice de liste. Le problème vient du fait que lorsque la variable i atteint n = len(L), on souhaite accéder à l’élément L[i] de la liste, qui n’existe pas. En effet, la liste L contient les n éléments suivants : L[0], L[1], L[2], …, L[n-1].

Pour corriger la fonction, il suffit de parcourir la liste une fois de moins :

def ma_fonction_corrigee(L):
    m = 0
    i = 0
    n = len(L)
    while i < n:
        if L[i] > m:
            m = L[i]
        i += 1
    return m

ma_fonction_corrigee([13, 12, 42, -37])

Exercice 4 : fonction factorielle#

Rappelons qu’une fonction est dite récursive si elle s’appelle elle-même, et itérative sinon.

Question 1 : Écrire une fonction itérative factorielle(n) qui calcule la factorielle d’un entier n passé en paramètre. Tester ensuite la fonction avec les valeurs de \(n \in \{ 0, 1, 5, 10 \}\) pour lesquelles on a \(0! = 1\), \(1! = 1\), \(5! = 120\) et \(10! = 3628800\).

Ensuite, que vaut \(100!\) ?

def factorielle(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

print("0! =", factorielle(0))
print("1! =", factorielle(1))
print("5! =", factorielle(5))
print("10! =", factorielle(10))
print("100! =", factorielle(100))

0! = 1
1! = 1
5! = 120
10! = 3628800
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Question 2 : Écrire une version récursive de la fonction factorielle, qui sera nommée factorielle_rec(n). Tester ensuite la fonction avec les mêmes valeurs que précédemment.

def factorielle_rec(n):
    if (n == 0):
        return 1
    return n * factorielle_rec(n-1)

print("0! =", factorielle_rec(0))
print("1! =", factorielle_rec(1))
print("5! =", factorielle_rec(5))
print("10! =", factorielle_rec(10))
print("100! =", factorielle_rec(100))

0! = 1
1! = 1
5! = 120
10! = 3628800
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Exercice 5 : suite récurrente d’ordre 1#

On considère la suite récurrente d’ordre \(1\) définie par

\[ u_0 = 1 \quad \text{ et } \quad u_{n+1} = \left\lfloor \frac{u_n^2}{3} \right\rfloor + n, \; \forall n \ge 0\,. \]

Question 1. Écrire une fonction itérative calcule_u_iter(n) qui calcule la valeur de \(u_n\) par une fonction itérative (c’est-à-dire, sans que la fonction s’appelle elle-même).

On vérifiera notamment que \(u_2 = 1\), \(u_4 = 4\) et \(u_{10} = 96177957631162369\).

def calcule_u_iter(n):
    u = 1
    for i in range(n):
        u = u**2 // 3 + i
    return u

print("u(0) =", calcule_u_iter(0))
print("u(2) =", calcule_u_iter(2))
print("u(4) =", calcule_u_iter(4))
print("u(10) =", calcule_u_iter(10))

u(0) = 1
u(2) = 1
u(4) = 4
u(10) = 96177957631162369

Question 2. Écrire une fonction récursive calcule_u_rec(n) qui calcule la valeur de \(u_n\) par une fonction récursive.

def calcule_u_rec(n):
    if n == 0:
        return 1
    else:
        u = calcule_u_rec(n-1)
        return u**2 // 3 + (n-1)

print("u(0) =", calcule_u_rec(0))
print("u(10) =", calcule_u_rec(10))

u(0) = 1
u(10) = 96177957631162369

Exercice 6 : test de croissance de liste#

Question 1 : Écrire une fonction itérative est_croissante_iter(L), qui prend en entrée une liste L, et qui teste si cette liste est triée dans l’ordre croissant.

def est_croissante_iter(L):
    n = len(L)
    i = 0 
    while (i < n-1):
        if L[i] > L[i+1]:
            return False
        i += 1
    return True

print(est_croissante_iter([]))
print(not(est_croissante_iter([1, 2, 5, 2, 3])))
print(est_croissante_iter([1, 2, 2, 3, 7]))

True
True
True

Observons maintenant qu’une liste L de longueur \(n\) est triée dans l’ordre croissant si les deux propriétés suivantes sont vérifiées :

ses deux derniers éléments sont triés dans l’ordre croissant
la sous-liste de ses \(n-1\) premiers éléments est également triée dans l’ordre croissant.

Par ailleurs, une liste de longueur \(1\) est toujours triée dans l’ordre croissant. On obtient donc une manière récursive de vérifier si une liste est triée dans l’ordre croissant.

Question 2 : En utilisant la caractérisation donnée plus haut, écrire une fonction récursive est_croissante_rec(L), qui prend en entrée une liste L, et qui teste si cette liste est triée dans l’ordre croissant. Votre fonction devra être récursive.

def est_croissante_rec(L):
    n = len(L)
    if (n <= 1):
        return True
    elif L[n-2] > L[n-1]:
        return False
    else:
        L.pop()
        return est_croissante_rec(L)
        
print(not(est_croissante_rec([1, 2, 5, 2, 3])))
print(est_croissante_rec([1, 2, 2, 3, 7]))

True
True