Algorithmes et Programmation 2, année 2022
Exercice 1: Explorer un système de fichier
Vous pouvez télécharger ici un script qui génère une arborescence compliquée de fichiers qui contiennent des informations pas très intéressantes.
Vous pouvez regarder comment ça marche!
Pour lancer le script:
python3 TD_ref/genere_arbre.py arbre
il va alors créer dans le repertoire courant un dossier
arbre et pleins de sous-dossier.
- Pour ouvrir un fichier en Python vous pouvez utiliser:
with open(“nom/du/fichier”) as f: x = f.read() # le contenu du fichier sous forme de chaîne de caractères
- Pour lister le contenu d’un répertoire, vous pouvez utiliser:
import os os.listdir(“chemin/vers/un/dossier”) # retourne la liste des noms de fichiers (chaine de caractères)
- Pour vérifier qu’un chemin pointe vers un dossier:
os.path.isdir(“chemin/vers/quelque/chose”) # retourne True si c’est un repertoire os.path.isfile(“chemin/vers/quelque/chose”) # retourne True si c’est un fichier
- Dans la suite n’utilisez pas os.walk
- Proposer un algorithme qui compte le nombre de fichiers dans l’arborescence
Attention à ne pas compter les dossiers. Vous pouvez utiliser la
commande find chemin/vers/repertoire -type f | wc -l pour
compter les fichier en ligne de commande (mais pas en Python!).
Proposez un algorithme qui retourne la profondeur (le nombre maximal de dossier imbriqué) dans l’arborescence.
Proposez un algorithme qui retourne une liste de liste où chaque liste contient les chemins vers fichiers ayant avec le même contenu.
Faites des analyses de complexités de vos implémentations
Exercice 2: Jouer avec les références
On va regarder les objets Pythons \(\mathcal{T}\) définit récursivement ainsi:
- Les entiers sont dans \(\mathcal{T}\)
- Si un \(t_1,\ldots,t_n\in \mathcal{T}\) alors \([t_1, \ldots, t_n]\in \mathcal{T}\).
D’une certaine manière, les éléments de \(\mathcal{T}\) représentent des arbres. Par exemple:
[[4, 5, 6], 10, [[11, 20, 30], 200, 440]] représente
l’arbre suivant:
La liste des feuilles de l’arbre précédent est
[4, 5, 6, 10, 11, 20, 30, 200, 440]
- Proposer un algorithme qui prends en entrée un élément de \(\mathcal{T}\) et retourne la liste de ses feuilles en respectant l’ordre.
Que ce passe t’il quand on execute votre code sur l’exemple suivant:
L = [[4, 5, 6], 10, [[11, 20, 30], 200, 440]]
L[2][0].append(L)- Proposer un algorithme qui vérifie qu’un objet python construit uniquement avec des listes et des entiers est bien un objet de \(\mathcal{T}\). C’est-à dire qu’il ne contient de liste incluse dans elle même.
Vous pouvez utiliser la fonction id vu dans le cours
Compiled the: dim. 07 janv. 2024 23:19:01 CET