TD8. Pierre Larousse
Ce TD a pour objectif d'introduire le type abstrait dictionnaire, et de voir comment utiliser ce type en Python.
Préambule : éléments de langage
Question 1
Donner une définition du terme dictionnaire.
Question 2
Donner une définition du terme dict ainsi qu'une ligne de code python permettant de créer un dict
.
Exercice 1 : conjecture de Syracuse
La conjecture de Syracuse est une conjecture mathématique célèbre qui considère la suite d'entiers définie par :
- u0 quelconque
- si ui est pair alors ui+1 = ui/2
- sinon ui+1 = 3*ui + 1
La conjecture postule que pour toute valeur entière strictement positive de u0, la suite finit toujours par atteindre la valeur 1.
Question 1
Écrire une fonction calcule_prochain_syracuse
prenant en entrée ui et renvoyant ui+1
Question 2
Écrire une fonction calcule_nb_etapes_avant_1
prenant en entrée u0 et renvoyant le nombre d'étapes nécessaires avant d'atteindre 1.
La fonction ne doit pas être récursive.
Question 3
À l'aide d'un dictionnaire, modifier la fonction calcule_nb_etapes_avant_1
pour tirer parti des résultats des appels précédents à la fonction.
L'appel à la fonction calcule_nb_etapes_avant_1
prenant en entrée u0 devra ajouter uniquement la clef u0 dans le dictionnaire.
Exercice 2 : fonctions injectives
On considère une fonction mathématique dont les résultats sont stockés dans un dictionnaire. Chaque élément du dictionnaire contient une valeur d'entrée de la fonction et la valeur de sortie associée. On suppose que le dictionnaire associe une valeur de sortie à chaque entrée possible.
Question 1
Écrire une fonction est_injective(fonction_dict)
qui vérifie si la fonction représentée par fonction_dict
est injective ou non.
Exercice 3 : comment faire mieux ? (pour aller plus loin)
Question 1
Modifier la version avec mémoisation de Syracuse pour stocker également tous les résultats intermédiaires.
Question 2
Modifier la fonction est_injective
pour utiliser un set
python.
Exercice 4 : soyons fous (pour aller encore plus loin)
Question 1
Démontrer ou invalider la conjecture de Syracuse.