informatique (MP2I/MPI) · Chapitre 8 · Exercice de TD
Problème — Les dernières lignes d'un flux qu'on ne peut lire qu'une fois
Mémoire, fichiers et entrées-sorties · niveau 3 (difficile)
Énoncé
On veut afficher les dernières lignes de l'entrée standard.
- Pourquoi ne peut-on pas simplement « aller à la fin et remonter » ?
- Écrire une solution en un seul passage et en mémoire , avec son invariant.
- Prouver la correction et traiter les cas limites.
Corrigé de la question 1
1. Pourquoi le problème est un vrai problème. Un fichier ordinaire a une taille et un accès direct : on peut s'y déplacer. Un flux n'a ni l'une ni l'autre. Quand l'entrée vient d'un tube — ./generer | ./fin — il n'y a pas de fin connue d'avance, pas de position où revenir, et les octets déjà lus sont perdus. Toute solution doit donc décider quoi retenir avant de savoir où le flux s'arrête.
Deux fausses solutions à écarter d'abord. Tout stocker dans un tableau : c'est en mémoire pour un flux de lignes, donc impossible sur un flux infini, et gaspilleur sur un gros fichier. Lire deux fois : c'est impossible sur un tube, et deux fois plus lent sur un fichier.
Question 2 : comment l'IA t'aide
2. Écrire une solution en un seul passage et en mémoire , avec son invariant.
Élève
Je pense garder les dernières lignes dans une file : j'ajoute chaque ligne lue en queue et, si la file dépasse , je retire en tête. Mais en C, avec un tableau, je ne vois pas comment éviter de décaler toutes les lignes à chaque lecture.
IA
La file est la bonne idée. Avec un tableau de cases, plutôt que de décaler, où pourrais-tu écrire la ligne numéro pour qu'elle écrase exactement la ligne dont tu n'as plus besoin ?
Élève
La ligne devenue inutile est celle de numéro . Il faudrait donc que les lignes et tombent dans la même case.
IA
Quelle fonction du numéro de ligne a cette propriété ? Écris ensuite l'invariant de la boucle de lecture : après lignes lues, quelles lignes le tableau contient-il, et dans quelles cases ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.