Livre_silo 30 août 2013 16:32 Page 168
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
168
Informatique pour tous
6.7 Exercices
Exercice 6.16 * Le but de cet exercice est d’écrire une fonction qui détermine la médiane d’un tableau
d’entiers.
1 Programmer l’algorithme suivant : on recherche le minimum et le maximum du tableau, on les supprime
et on recommence jusqu’à obtenir un tableau de longueur inférieure ou égale à 2. On déduit alors
facilement la valeur de la médiane du ou des entiers restants.
2 Quelle est la complexité de cet algorithme ? On verra au chapitre 13 qu’il existe des méthodes plus
efficaces.
Exercice 6.17 Écrire une fonction qui détermine si tous les éléments d’un tableau (d’entiers ou de flottants) sont positifs ou nuls. On veillera à sortir de la fonction dès qu’une valeur négative est rencontrée.
Exercice 6.18 Écrire une fonction qui prend en arguments trois entiers m, n et p et renvoie un tableau
identique à celui désigné par l’expression list(range(m, n, p)), bien entendu sans utiliser cette dernière
expression.
Exercice 6.19 Écrire une fonction qui prend un entier n en argument et renvoie un tableau de n entiers
tirés aléatoirement dans l’intervalle 0, n. On utilisera la fonction random.randint pour cela.
Exercice 6.20 Écrire une fonction qui renvoie un tableau aléatoire de caractères entre 'a' et 'z'. On
utilisera pour cela les fonctions ord (qui renvoie le code d’un caractère) et chr (qui renvoie le caractère
associé à un code donné).
Exercice 6.21 * Dans cet exercice, on écrira différentes versions d’une fonction qui prend en argument
un tableau et inverse l’ordre de ses éléments, sans utiliser la fonction reversed.
1 Dans un premier temps, écrire une fonction qui renvoie un autre tableau contenant les éléments dans
l’ordre inverse. Le tableau donné en argument devra rester inchangé.
2 Écrire ensuite une autre fonction qui renverse l’ordre des éléments en place, c’est-à-dire directement
dans le tableau fourni en argument et sans utiliser de tableau auxiliaire.
Exercice 6.22 Écrire une fonction appliquer qui prend pour arguments une fonction f et un tableau t
et renvoie le tableau formé des images de chaque élément de t par la fonction f.
La fonction map de Python réalise une opération similaire.
Exercice 6.23 * Écrire une fonction qui vérifie si un tableau donné en argument est dépourvu de doublons
(aucune valeur n’y apparaît deux fois). Évaluer sa complexité.
Exercice 6.24 Écrire une fonction qui mélange aléatoirement les éléments d’un tableau a en utilisant
le « mélange de Knuth » (Knuth shuffle). L’algorithme est le suivant : pour i allant de 1 à len(a)-1, on
échange a[i] avec a[j], où j est un entier choisi aléatoirement entre 0 et i, inclus.
Exercice 6.25 Pour tester la fonction recherche_dichotomique (programme 1 page 157), écrire une fonction qui renvoie un tableau trié de n entiers. On pourra procéder en utilisant une variable entière, que l’on
incrémentera de manière aléatoire.
Exercice 6.26 * Réécrire la fonction recherche_mot (programme 2 page 159), en utilisant la construction
t[i:j]. Quel est le défaut de cette solution ?
Exercice 6.27 Écrire une fonction qui calcule le produit scalaire de deux vecteurs représentés par deux
tableaux de même taille.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
168
Informatique pour tous
6.7 Exercices
Exercice 6.16 * Le but de cet exercice est d’écrire une fonction qui détermine la médiane d’un tableau
d’entiers.
1 Programmer l’algorithme suivant : on recherche le minimum et le maximum du tableau, on les supprime
et on recommence jusqu’à obtenir un tableau de longueur inférieure ou égale à 2. On déduit alors
facilement la valeur de la médiane du ou des entiers restants.
2 Quelle est la complexité de cet algorithme ? On verra au chapitre 13 qu’il existe des méthodes plus
efficaces.
Exercice 6.17 Écrire une fonction qui détermine si tous les éléments d’un tableau (d’entiers ou de flottants) sont positifs ou nuls. On veillera à sortir de la fonction dès qu’une valeur négative est rencontrée.
Exercice 6.18 Écrire une fonction qui prend en arguments trois entiers m, n et p et renvoie un tableau
identique à celui désigné par l’expression list(range(m, n, p)), bien entendu sans utiliser cette dernière
expression.
Exercice 6.19 Écrire une fonction qui prend un entier n en argument et renvoie un tableau de n entiers
tirés aléatoirement dans l’intervalle 0, n. On utilisera la fonction random.randint pour cela.
Exercice 6.20 Écrire une fonction qui renvoie un tableau aléatoire de caractères entre 'a' et 'z'. On
utilisera pour cela les fonctions ord (qui renvoie le code d’un caractère) et chr (qui renvoie le caractère
associé à un code donné).
Exercice 6.21 * Dans cet exercice, on écrira différentes versions d’une fonction qui prend en argument
un tableau et inverse l’ordre de ses éléments, sans utiliser la fonction reversed.
1 Dans un premier temps, écrire une fonction qui renvoie un autre tableau contenant les éléments dans
l’ordre inverse. Le tableau donné en argument devra rester inchangé.
2 Écrire ensuite une autre fonction qui renverse l’ordre des éléments en place, c’est-à-dire directement
dans le tableau fourni en argument et sans utiliser de tableau auxiliaire.
Exercice 6.22 Écrire une fonction appliquer qui prend pour arguments une fonction f et un tableau t
et renvoie le tableau formé des images de chaque élément de t par la fonction f.
La fonction map de Python réalise une opération similaire.
Exercice 6.23 * Écrire une fonction qui vérifie si un tableau donné en argument est dépourvu de doublons
(aucune valeur n’y apparaît deux fois). Évaluer sa complexité.
Exercice 6.24 Écrire une fonction qui mélange aléatoirement les éléments d’un tableau a en utilisant
le « mélange de Knuth » (Knuth shuffle). L’algorithme est le suivant : pour i allant de 1 à len(a)-1, on
échange a[i] avec a[j], où j est un entier choisi aléatoirement entre 0 et i, inclus.
Exercice 6.25 Pour tester la fonction recherche_dichotomique (programme 1 page 157), écrire une fonction qui renvoie un tableau trié de n entiers. On pourra procéder en utilisant une variable entière, que l’on
incrémentera de manière aléatoire.
Exercice 6.26 * Réécrire la fonction recherche_mot (programme 2 page 159), en utilisant la construction
t[i:j]. Quel est le défaut de cette solution ?
Exercice 6.27 Écrire une fonction qui calcule le produit scalaire de deux vecteurs représentés par deux
tableaux de même taille.