TP 1 : Dictionnaire et recherche séquentielle

Recherche séquentielle dans une liste¶

Exercice

1. Ecrire une fonction appartient telle que appartient(e, L) renvoie True si e appartient à L, False sinon.
2. Ecrire une maximum renvoyant le maximum d'une liste.
3. Ecrire une fonction maximum2 renvoyant le deuxième plus grand élément d'une liste. Par exemple maximum2([2, 1, 3, 0, 5]) doit renvoyer 3. On supposera tous les éléments différents pour simplifier.

Solution

In [1]:

def appartient(e, L):
    for i in range(len(L)):
        if e == L[i]:
            return True
    return False

def maximum(L):
    m = L[0]
    for i in range(1, len(L)):
        if L[i] > m:
            m = L[i]
    return m

def maximum2(L):
    if L[0] > L[1]:
        m, m2 = L[0], L[1]
    else:
        m, m2 = L[1], L[0]
    # m est le maximum et m2 le 2ème maximum
    for i in range(2, len(L)):
        if L[i] > m2:
            if L[i] > m:
                m, m2 = L[i], m
            else:
                m2 = L[i]
    return m2

maximum2([2, 1, 3, 0, 5])

def appartient(e, L): for i in range(len(L)): if e == L[i]: return True return False def maximum(L): m = L[0] for i in range(1, len(L)): if L[i] > m: m = L[i] return m def maximum2(L): if L[0] > L[1]: m, m2 = L[0], L[1] else: m, m2 = L[1], L[0] # m est le maximum et m2 le 2ème maximum for i in range(2, len(L)): if L[i] > m2: if L[i] > m: m, m2 = L[i], m else: m2 = L[i] return m2 maximum2([2, 1, 3, 0, 5])

Out[1]:

3

Dictionnaire¶

Un dictionnaire permet de stocker des associations clés-valeurs : à chaque clé, le dictionnaire donne une valeur. C'est similaire à une liste qui possède une valeur à chaque indice (= clé) sauf que les clés d'un dictionnaire ne sont pas forcément des entiers consécutifs.

Exemple de définition d'un dictionnaire qui à 2 associe 4 et à 3 associe 6 :

In [1]:

dictionnaire = {2: 4, 3: 6}

dictionnaire = {2: 4, 3: 6}

Pour récupérer la valeur associée à 3 :

In [3]:

dictionnaire[3]  # comme pour une liste

dictionnaire[3] # comme pour une liste

Out[3]:

6

Pour ajouter une association de 4 vers 8 :

In [6]:

dictionnaire[4] = 8

dictionnaire[4] = 8

Pour obtenir le nombre de clés d'un dictionnaire :

In [7]:

len(dictionnaire)

len(dictionnaire)

Out[7]:

3

Pour obtenir la liste des clés d'un dictionnaire :

In [9]:

dictionnaire.keys()

dictionnaire.keys()

Out[9]:

dict_keys([2, 3, 4])

On peut parcourir les clés avec une boucles for :

In [10]:

for cle in dictionnaire.keys():  # .keys() est optionnel
    print(f"la valeur associée à la clé {cle} est la valeur {dictionnaire[cle]}")

for cle in dictionnaire.keys(): # .keys() est optionnel print(f"la valeur associée à la clé {cle} est la valeur {dictionnaire[cle]}")

la valeur associée à la clé 2 est la valeur 4
la valeur associée à la clé 3 est la valeur 6
la valeur associée à la clé 4 est la valeur 8

On peut aussi créer un dictionnaire vide :

In [ ]:

d = {}  # dictionnaire vide
d = dict()  # autre façon de définir un dictionnaire vide
# on peut ensuite ajouter des éléments avec d

d = {} # dictionnaire vide d = dict() # autre façon de définir un dictionnaire vide # on peut ensuite ajouter des éléments avec d

Exercice

1. Définir un dictionnaire qui à 42 associe 5 et à 23 associe 13. Vérifier.
2. Définir un dictionnaire d associant aux chaînes de caractères "hello" et "python" leurs nombres de caractères (par exemple, il faut que d["hello"]soit égal à 5 car "hello" contient 5 caractères).

Solution

In [3]:

# 1
d = {42 : 5, 23 : 13}
print(d[23]) # donne 13

# 2
d = {"hello" : 5, "python" : 6}
d["hello"]

# 1 d = {42 : 5, 23 : 13} print(d[23]) # donne 13 # 2 d = {"hello" : 5, "python" : 6} d["hello"]

13

Out[3]:

5

Comptage avec un dictionnaire¶

Exercice

1. Ecrire une fonction compter telle que compter(L) renvoie un dictionnaire d dont les clés sont les éléments de L et les valeurs sont les nombres d'apparitions de chaque éléments. Ainsi, d[e] est le nombre de fois que L[e] apparaît dans L. Par exemple, compter([1, 7, 1, 1, 5, 7]) doit renvoyer d tel que d[1] = 3 (1 apparaît 3 fois), d[5] = 1 (5 apparaît 1 fois), d[7] = 2 (7 apparaît 2 fois).
2. En déduire une fonction majoritaire telle que majoritaire(L) renvoie l'élément qui apparaît le plus souvent dans L. Par exemple, majoritaire([1, 7, 1, 1, 5, 7]) doit renvoyer 1 (il apparaît plus de fois que n'importe quel autre élément).

Solution

In [6]:

# 1
def compter(L):
    d = {} # dictionnaire vide
    for e in L:
        if e not in d:
            d[e] = 0
        d[e] += 1 # augmente de 1 le nombre d'appartions de e
    return d

print(compter([1, 7, 1, 1, 5, 7]))

# 2
def majoritaire(L):
    d = compter(L)
    m = None # l'élément ayant apparu le plus de fois (None est juste là pour l'initialisation)
    for k in d:
        if m is None or d[k] > d[m]:
            m = k # mise à jour de m
    return m

majoritaire([1, 7, 1, 1, 5, 7])

# 1 def compter(L): d = {} # dictionnaire vide for e in L: if e not in d: d[e] = 0 d[e] += 1 # augmente de 1 le nombre d'appartions de e return d print(compter([1, 7, 1, 1, 5, 7])) # 2 def majoritaire(L): d = compter(L) m = None # l'élément ayant apparu le plus de fois (None est juste là pour l'initialisation) for k in d: if m is None or d[k] > d[m]: m = k # mise à jour de m return m majoritaire([1, 7, 1, 1, 5, 7])

{1: 3, 7: 2, 5: 1}

Out[6]:

1

Suite de Syracuse¶

Exercice

La suite de Syracuse d'un entier $a$ est définie par :
$$u_0 = a$$ $$u_{n+1} = \begin{cases} \frac{u_n}{2}, \text{si } n \text{ est pair}\\ 3u_n + 1, \text{sinon}\\ \end{cases}$$

1. Écrire une fonction syracuse telle que syracuse(a, n) renvoie $u_n$.
2. Le temps de vol de $(u_n)$ est le plus petit entier $t$ tel que $u_t = 1$. Écrire une fonction temps_vol telle que temps_vol(a) renvoie $t$.