A table

Pilao de poulet

Ingredients	Quantité
riz	1
cuisses de poulet	1
tomates	2
concentré de tomate	1
oignons	5

Pilao de poulet


ingredients = ["riz", "cuisses", "tomates", "concentré", "oignons"]
quantites = [1,1,2,1,5]

Sauce Mole de Oaxaca

Ingredients	Quantité
noix	30 g
cacahuète	30 g
amande	40 g
graines de sésame	25 g
tomates concassées en boîte	2
oignons hachés	2
gousse d'ail hachées	4
cacao en poudre	80 g
purée de piment	80 g
bouillon de volaille	50 cl
sel	1 c. à café
cannelle moulue	1 pincée
huile d’olive	3 cl
tortilla	1

Sauce Mole de Oaxaca


ingredients = ["noix", "cacahuète", "amande", "sésame", "tomates concassées","oignons","ail","cacao","piment","bouillon","sel","cannelle","huile","tortilla"]
quantites = [30,30,40,25,2,2,4,80,80,50,1,1,3,1]

Construction d'une nouvelle structure de données

Objectifs:
Lier les ingredients et leurs quantités.

Etape 1 : Une liste


mole = [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]

Etape 2 : Une fonction de hachage


def hachage(mot):
    hash = 0
    for lettre in mot:
        hash += ord(lettre)
    return hash % 1024

hachage("noix")

\longrightarrow

446
hachage("cacahuète")

\longrightarrow

38
hachage("amande")

\longrightarrow

614
hachage("sésame")

\longrightarrow

770
hachage("tomates concassées")

\longrightarrow

968
hachage("oignons")

\longrightarrow

765
hachage("ail")

\longrightarrow

310
hachage("cacao")

\longrightarrow

503
hachage("piment")

\longrightarrow

653
hachage("bouillon")

\longrightarrow

868
hachage("sel")

\longrightarrow

324
hachage("cannelle")

\longrightarrow

834
hachage("huile")

\longrightarrow

535
hachage("tortilla")

\longrightarrow

875


mole[hachage("noix")] = ("noix",30)
mole[hachage("cacahuète")] = ("cacahuète",30)
mole[hachage("amande")] = ("amande",40)
...
...
...


mole[446] = ("noix",30)
mole[hachage("cacahuète")] = ("cacahuète",30)
mole[hachage("amande")] = ("amande",40)
...
...
...


mole[446] = ("noix",30)
mole[38] = ("cacahuète",30)
mole[hachage("amande")] = ("amande",40)
...
...
...


mole[446] = ("noix",30)
mole[38] = ("cacahuète",30)
mole[614] = ("amande",40)
...
...
...

\textrm{mole = [None, ... ,}\underbrace{("cacahuète",30)}_\textrm{index:38}, ... , \underbrace{("noix",30)}_\textrm{index : 446}, ..., \underbrace{("amande",40)}_\textrm{index:614}, ...]

Dictionnaire

type `dict`

Dictionnaire

En informatique, un dictionnaire est une structure de données représentant une séquence finie qui associe une clé et une valeur.

Objectifs

Créer un dictionnaire,
Accéder à une valeur,
Ajouter / modifier des couple clé / valeur,
Parcourir les éléments d'un dictionnaire,
Savoir si une clé appartient au dictionnaire
Comparer deux dictionnaires
Supprimer une clé

Implémentation des dictionnaires python

Représentation

En python, les dictionnaires sont contenus dans des accolades { ... } . Les clés sont séparées des valeurs par deux points : et les couples clés / valeurs sont séparés par des virgules ,

Représentation

{ clé1 : valeur1 , clé2 : valeur2 }

Instanciation


vide_1 = {}
vide_2 = dict()
informaticiens = {"Alan Turing":1912, "Ada Lovelace":1815, "Grace Hopper":1906}

Instanciation

Les clés et les valeurs du dictionnaire informaticiens sont donc :

Clé	Valeur
Alan Turing	1912
Ada Lovelace	1815
Grace Hopper	1906

Accéder à un élément

L'instruction pour accéder à une valeur est construite à partir du nom du dictionnaire et de la clé de la valeur souhaitée entre crochets.

nom_dictionnaire[clé]

Accéder à un élément

Le dictionnaire s'appelle informaticiens et la valeur 1815 est associée à la clé "Ada Lovelace".
On accède donc à cet élément avec l'instruction :

informaticiens["Ada Lovelace"]

Savoir si une clé est dans un dictionnaire

Pour savoir si une clé est dans un dictionnaire, on utilise le mot clé span class="orange"> in

clé in dictionnaire

Modifier un couple clé / valeur

Pour ajouter un élément, l'instruction est composée du nom du dictionnaire, de la clé entre crochets et de la valeur. L'affectation se fait par le signe =.
On a donc :

nom_dictionnaire[clé] = valeur

Modifier un couple clé / valeur

Il y a 2 cas possibles :

Si la clé est déjà présente dans le dictionnaire, la valeur associée est remplacée par la nouvelle,
Si la clé n'est pas déjà présente dans le dictionnaire, le couple clé / valeur est ajouté au dictionnaire.

Parcourir les dictionnaires

Il existe plusieurs méthodes pour parcourir les clés d'un dictionnaire :

En itérant sur le dictionnaire,
En itérant sur l'objet dict_keys obtenu avec la méthode keys()
En itérant sur l'objet dict_values obtenu avec la méthode values()
En itérant sur l'objet dict_items obtenu avec la méthode items()

Parcourir les clés


informaticiens = {"Alan Turing":1912, "Ada Lovelace":1815, "Grace Hopper":1906}
for cle in informaticiens:
    print(cle)

Parcourir les clés


informaticiens = {"Alan Turing":1912, "Ada Lovelace":1815, "Grace Hopper":1906}
for cle in informaticiens.keys():
    print(cle)

Parcourir les clés


informaticiens = {"Alan Turing":1912, "Ada Lovelace":1815, "Grace Hopper":1906}
for valeur in informaticiens.values():
    print(valeur)

Parcourir les clés


informaticiens = {"Alan Turing":1912, "Ada Lovelace":1815, "Grace Hopper":1906}
for cle, valeur in informaticiens.items():
    print(f"La valeur {valeur} est asssociée à la clé {cle}")

Quizz

Implémentation à l'aide d'une table de hash

def hash(key):
    h = 0 
    for lettre in key:
        h += ord(lettre)
    return h 
    
def ajout(dic, cle, valeur):
    dic[hash(cle)] = valeur
    return dic

def chercher(dic, cle):
    return dic[hash(cle)]

mon_dic = [None]*53687091 

ajout(mon_dic, "bonjour", "nsi")
print(chercher(mon_dic,"bonjour"))

A table

Pilao de poulet

Pilao de poulet

Sauce Mole de Oaxaca

Sauce Mole de Oaxaca

Construction d'une nouvelle structure de données

Dictionnaire

type dict

Dictionnaire

Objectifs

Implémentation des dictionnaires python

Représentation

Représentation

Instanciation

Instanciation

Accéder à un élément

Accéder à un élément

Savoir si une clé est dans un dictionnaire

Modifier un couple clé / valeur

Modifier un couple clé / valeur

Parcourir les dictionnaires

Parcourir les clés

Parcourir les clés

Parcourir les clés

Parcourir les clés

Quizz

Implémentation à l'aide d'une table de hash

type `dict`