C2 : Exercices

Exercices d'entrainement

C4.E1 : Nombre de caractères dans une chaine

Écrire une fonction récursive qui prend une chaine de caractères en paramètre et renvoie la longueur de cette chaine sans utiliser la fonction native len.

Afficher la correction

def lg(chaine):
    if chaine == "":
        return 0
    else:
        return 1 + lg(chaine[1:])

print(lg(""))
print(lg("b"))
print(lg("bo"))
print(lg("bonjour"))

C4.E2 : Fonctions mystérieuses

On considère le code ci-dessous.

def f1(n):
    if n == 1:
        return False
    return f2(n-1)

def f2(n):
    if n == 1:
        return True
    return f1(n-1)

1) Indiquer les valeurs renvoyées par f1(1), f1(2), f1(3), f1(4) et f1(5).

2) Expliquer le rôle des fonctions f1 et f2 et écrire leurs docstrings.

Afficher la correction

C4.E3 : Valeur maximale d'une liste

Écrire une fonction récursive qui prend une liste de nombres en paramètre et renvoie la valeur maximale de cette liste.

Afficher la correction

import doctest

def maxi_rec(li) :
    """
    Renvoie la valeur maximale d'une liste
    Paramètres
        li (list) : liste d'entiers ou de flotants
    Return (int) ou (float)

    >>> maxi_rec([])

    >>> maxi_rec([15])
    15
    >>> maxi_rec([15,2,-9,5,3,-7])
    15
    >>> maxi_rec([2,-9,5,3,-7])
    5
    >>> maxi_rec([2,-9,5,3,-7,20])
    20
    """
    if len(li) == 0:
        return None
    elif len(li) == 1:
        return li[0]
    else:
        val1 = li[0]
        val2 = maxi_rec(li[1:])
        if val1 > val2:
            return val1
        else:
            return val2

doctest.testmod(verbose=True)

Remarque : les opérations qui consistent à récupérer des tranches de listes (c'est-à-dire [__ : __]) sont coûteuses. Donc quand on peut on les évite.

Voici une autre version de l'exercice :

def maxi_rec(l:list)->int:
    if len(l) == 0:
        return None
    else:
        return rec(l, 0)

def rec(l,i):
    if i == len(l)-1:
        return l[i]
    else:
        return max(l[i], rec(l, i+1))


assert maxi_rec([]) == None
assert maxi_rec([1]) == 1
assert maxi_rec([1, 8]) == 8
assert maxi_rec([8, 1]) == 8
assert maxi_rec([1, 8, 5]) == 8
assert maxi_rec([12, 8, 5]) == 12
assert maxi_rec([1, 8, 15]) == 15
assert maxi_rec([1, 8, 5, -5, 13, 28]) == 28

Petits problèmes

C4.Pb1 : Suite de fibonacci

La suite de Fibonacci est une suite de nombres entiers dans laquelle chaque nombre est la somme des deux nombres qui le précèdent. Elle commence par les nombres 0 et 1.

Voici les premières valeurs de cette suite :

\(F_0\)	\(F_1\)	\(F_2\)	\(F_3\)	\(F_4\)	\(F_5\)	\(F_6\)	\(F_7\)	\(F_8\)	\(F_9\)	\(F_10\)
\(0\)	\(1\)	\(1\)	\(2\)	\(3\)	\(5\)	\(8\)	\(13\)	\(21\)	\(34\)	\(55\)

1) Écrire une fonction récursive fibo_rec(i:int)->int qui prend un entier i en paramètre et renvoie la valeur du i^ème terme de la suite de Fibonacci. Ainsi, fibo_rec(6) doit renvoyer 8.

2) Écrire une fonction non récursive fibo_seq(i:int)->int qui prend un entier i en paramètre et renvoie la valeur du i^ème terme de la suite de Fibonacci. Ainsi, fibo_seq(6) doit renvoyer 8.

3) Indiquer en justifiant laquelle des deux fonctions utilise le moins de ressource processeur.

Afficher la correction

def fibo_req(nb) :
    if nb == 0 or nb == 1:
        return nb
    else:
        return fibo_req(nb-1) + fibo_req(nb-2)

def fibo_seq(nb):
    if nb == 0:
        return 0
    else:
        liste_fibo = [0,1]
        for i in range(2,nb+1):
            liste_fibo.append(liste_fibo[i-1] + liste_fibo[i-2])
        return liste_fibo[-1]

print(fibo_req(0))
print(fibo_req(1))
print(fibo_req(7))
print(fibo_req(8))

print(fibo_seq(0))
print(fibo_seq(1))
print(fibo_seq(7))
print(fibo_seq(8))