Livre_silo 30 août 2013 16:32 Page 160
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
160
Informatique pour tous
SAVOIR-FAIRE Concevoir un algorithme répondant à un problème
précisément posé
1 Identifier la structure adaptée pour représenter les données du problème (par
exemple un tableau).
2 Déterminer si le problème peut se ramener à un des algorithmes usuels sur cette
structure (par exemple le parcours du tableau).
3 Apporter les modifications nécessaires à cet algorithme pour répondre au problème.
Exercice 6.11 Concevoir un algorithme vérifiant qu’une suite est croissante jusqu’à un certain rang.
1 On peut représenter les termes de la suite comme un tableau de flottants u.
2 Si la suite est effectivement croissante, il faudra le vérifier à chaque rang, mais si elle ne l’est pas, on
pourra interrompre le parcours du tableau dès qu’on aura trouvé deux valeurs en ordre décroissant.
L’algorithme que l’on va écrire est donc à rapprocher d’une recherche séquentielle.
3 Il y a principalement deux différences avec la recherche séquentielle. D’une part, on ne va pas comparer
un élément avec une valeur fixée, mais avec l’élément suivant. D’autre part, on veut savoir si la suite
est croissante et donc on renverra True dans le cas où on a parcouru tout le tableau sans trouver de
valeurs en ordre décroissant.
On pourra écrire une fonction comme celle-ci :
def croissante(u):
for i in range(len(u)-1):
if u[i] > u[i+1]:
return False
return True
Exercice 6.12 Modifier le programme 2 pour qu’il affiche toutes les occurrences de m dans t. La complexité
est-elle différente après cette modification ?
Exercice 6.13 Écrire une fonction qui vérifie qu’une chaîne de caractères est composée uniquement de
lettres de l’alphabet, d’espaces et des symboles de ponctuation usuels.
Évaluer sa complexité.
Exercice 6.14 Écrire une fonction qui vérifie qu’une chaîne de caractères est une adresse e-mail valide.
On pensera par exemple à vérifier la présence du symbole @, l’absence de certains caractères, etc.
Exercice 6.15 * Écrire une fonction qui vérifie qu’une chaîne de caractères est un palindrome, c’est-à-dire
qu’elle est identique qu’on la lise de gauche à droite ou de droite à gauche.
Adapter cette fonction pour qu’elle ne tienne pas compte des espaces ni des signes de ponctuation.
6.5 Matrices
On peut choisir de représenter une matrice de dimensions (n, p) par un tableau de longueur n, dont les éléments sont des tableaux de longueur p.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
160
Informatique pour tous
SAVOIR-FAIRE Concevoir un algorithme répondant à un problème
précisément posé
1 Identifier la structure adaptée pour représenter les données du problème (par
exemple un tableau).
2 Déterminer si le problème peut se ramener à un des algorithmes usuels sur cette
structure (par exemple le parcours du tableau).
3 Apporter les modifications nécessaires à cet algorithme pour répondre au problème.
Exercice 6.11 Concevoir un algorithme vérifiant qu’une suite est croissante jusqu’à un certain rang.
1 On peut représenter les termes de la suite comme un tableau de flottants u.
2 Si la suite est effectivement croissante, il faudra le vérifier à chaque rang, mais si elle ne l’est pas, on
pourra interrompre le parcours du tableau dès qu’on aura trouvé deux valeurs en ordre décroissant.
L’algorithme que l’on va écrire est donc à rapprocher d’une recherche séquentielle.
3 Il y a principalement deux différences avec la recherche séquentielle. D’une part, on ne va pas comparer
un élément avec une valeur fixée, mais avec l’élément suivant. D’autre part, on veut savoir si la suite
est croissante et donc on renverra True dans le cas où on a parcouru tout le tableau sans trouver de
valeurs en ordre décroissant.
On pourra écrire une fonction comme celle-ci :
def croissante(u):
for i in range(len(u)-1):
if u[i] > u[i+1]:
return False
return True
Exercice 6.12 Modifier le programme 2 pour qu’il affiche toutes les occurrences de m dans t. La complexité
est-elle différente après cette modification ?
Exercice 6.13 Écrire une fonction qui vérifie qu’une chaîne de caractères est composée uniquement de
lettres de l’alphabet, d’espaces et des symboles de ponctuation usuels.
Évaluer sa complexité.
Exercice 6.14 Écrire une fonction qui vérifie qu’une chaîne de caractères est une adresse e-mail valide.
On pensera par exemple à vérifier la présence du symbole @, l’absence de certains caractères, etc.
Exercice 6.15 * Écrire une fonction qui vérifie qu’une chaîne de caractères est un palindrome, c’est-à-dire
qu’elle est identique qu’on la lise de gauche à droite ou de droite à gauche.
Adapter cette fonction pour qu’elle ne tienne pas compte des espaces ni des signes de ponctuation.
6.5 Matrices
On peut choisir de représenter une matrice de dimensions (n, p) par un tableau de longueur n, dont les éléments sont des tableaux de longueur p.