Skip to content

TD5. Séquences de caractères

Ce TD a pour objectif de prendre conscience que la notion de complexité a aussi du sens pour l'utilisation mémoire.

Exercice 1 : séquence infinie de caractères

On considère l'analyse d'une séquence de caractères, potentiellement très, très, très longue. On dispose d'une fonction recupere_prochain_caractere() qui renvoie le prochain caractère non traité de la séquence. On considère que le caractère @ indique la fin de la séquence.

On cherche à réaliser un ensemble d'opérations d'analyse sur une séquence donnée. Toutes les opérations doivent être réalisées en une seule passe. Vous devez donc compléter le code suivant afin de réaliser les analyses des questions 1 à 6 :

... # initialisation
car = recupere_prochain_caractere()
while car != '@':
    ... # analyse
    car = recupere_prochain_caractere()
... # affichage des résultats

Par exemple, pour la séquence 'a le a pelle nouveaux 23 15 5 faux@' on obtient :

a : 4
le : 2
mots : 9
mots finissant par x : 2
moyenne des longueurs des mots : 2.88888888888889

Question 1

Ajouter le code nécessaire pour compter les a

Question 2

Ajouter le code nécessaire pour compter les le

Question 3

Ajouter le code nécessaire pour compter les mots

Question 4

Ajouter le code nécessaire pour compter les mots terminés par x

Question 5

Ajouter le code nécessaire pour calculer la moyenne de la longueur des mots

Question 6

Calculer la somme de tous les nombres de la séquence. Un nombre est l'interprétation en base 10 d'une séquence de chiffres (caractères entre '0' et '9'). Sur l'exemple précédent on obtient ainsi 23 + 15 + 5 = 43

Exercice 2 : mémoire constante, vraiment ? (pour aller plus loin)

Question 1

Sommes-nous vraiment certain de ne pas avoir de problème de mémoire ? Pourquoi ?

Question 2

En supposant que nous puissions traiter un caractère par nanoseconde, combien de temps nous faudrait il pour utiliser 1ko de mémoire avec une séquence ne contenant que des a ?

Question 3

Écrire un programme qui sature la mémoire petit à petit de façon visible simplement avec un seul entier.