Livre_silo 30 août 2013 16:32 Page 314
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
314
Informatique pour tous
12.4 Exercices
Dans tous les exercices proposés ici, on veillera à n’utiliser que l’interface fournie par les
piles, et pas les opérateurs spécifiques aux tableaux.
Exercice 12.12 Écrire une fonction qui intervertit les deux éléments situés au sommet d’une pile de taille
au moins égale à 2.
Exercice 12.13 Écrire une fonction qui dépile et renvoie le troisième élément d’une pile de taille au moins
égale à 3. Les premier et deuxième éléments devront rester au sommet de la pile.
Exercice 12.14 Écrire une fonction qui lit le n-ième élément d’une pile. On s’assurera que la pile, en sortie,
contient toujours les mêmes éléments. (Indication : on pourra utiliser une deuxième pile.) On prévoira le
cas où la pile n’est pas de taille suffisante pour qu’un tel élément existe.
Exercice 12.15 Programmer les fonctions sommet et taille uniquement à l’aide de empiler, depiler et
est_vide, indépendamment de la réalisation de pile choisie.
Que peut-on dire de la complexité en temps et en espace de cette fonction taille ?
Exercice 12.16 Écrire une fonction qui prend une pile non vide en argument et place l’élément situé à
son sommet tout au fond de la pile, en conservant l’ordre des autres éléments.
Quelle est sa complexité en temps et en espace ?
Exercice 12.17 Écrire une fonction similaire à reversed, qui prend une pile en argument et renvoie une
autre pile constituée des mêmes éléments placés dans l’ordre inverse. On s’autorise à vider la pile fournie
en argument. Quelle est la complexité en temps et en espace de cette fonction ?
Exercice 12.18 * Tester dans différentes situations le comportement des boutons proposés par un navigateur Internet : visiter une nouvelle page, revenir d’une page en arrière, aller une page en avant.
Écrire un ensemble de fonctions simulant ces boutons. On pourra pour cet exercice utiliser deux piles.
Exercice 12.19 Écrire une fonction couper qui prend une pile et la coupe en enlevant de son sommet un
certain nombre d’éléments (tiré au hasard) qui sont renvoyés dans une seconde pile. Exemple : si la pile
initiale est [1, 2, 3, 4, 5] et si le nombre d’éléments retirés vaut 2, alors la pile ne contient plus que
[1, 2, 3] et la pile renvoyée contient [5, 4].
Exercice 12.20 * Mélange de cartes. Écrire une fonction melange qui prend en arguments deux piles
et qui mélange leurs éléments dans une troisième pile de la façon suivante : tant qu’une pile au moins
n’est pas vide, on retire aléatoirement un élément au sommet d’une des deux piles et on l’empile sur la
pile résultat. Exemple : un mélange possible des piles [1, 2, 3] et [5, 4] est [3, 2, 4, 1, 5]. Note : à
l’issue du mélange, les deux piles de départ sont donc vides.
Exercice 12.21 * Tour de magie de Gilbreath. Construire un paquet de cartes en empilant n fois
les mêmes k cartes (par exemple, pour un paquet de 32 cartes, on empile n = 16 paquets de paires
rouge/noir). Couper alors le paquet avec la fonction couper ci-dessus, puis mélanger les deux paquets
obtenus à l’aide de la fonction melange. On observe alors que le paquet final contient toujours n blocs
des mêmes k cartes (même si ces dernières peuvent apparaître dans un ordre différent au sein de chaque
bloc). Sur l’exemple des 16 paquets rouge/noir, on obtient toujours 16 paquets rouge/noir ou noir/rouge.
Exercice 12.22 ** Écrire une réalisation des tableaux redimensionnables en suivant l’idée décrite dans
l’encadré Pour aller plus loin page 305.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
314
Informatique pour tous
12.4 Exercices
Dans tous les exercices proposés ici, on veillera à n’utiliser que l’interface fournie par les
piles, et pas les opérateurs spécifiques aux tableaux.
Exercice 12.12 Écrire une fonction qui intervertit les deux éléments situés au sommet d’une pile de taille
au moins égale à 2.
Exercice 12.13 Écrire une fonction qui dépile et renvoie le troisième élément d’une pile de taille au moins
égale à 3. Les premier et deuxième éléments devront rester au sommet de la pile.
Exercice 12.14 Écrire une fonction qui lit le n-ième élément d’une pile. On s’assurera que la pile, en sortie,
contient toujours les mêmes éléments. (Indication : on pourra utiliser une deuxième pile.) On prévoira le
cas où la pile n’est pas de taille suffisante pour qu’un tel élément existe.
Exercice 12.15 Programmer les fonctions sommet et taille uniquement à l’aide de empiler, depiler et
est_vide, indépendamment de la réalisation de pile choisie.
Que peut-on dire de la complexité en temps et en espace de cette fonction taille ?
Exercice 12.16 Écrire une fonction qui prend une pile non vide en argument et place l’élément situé à
son sommet tout au fond de la pile, en conservant l’ordre des autres éléments.
Quelle est sa complexité en temps et en espace ?
Exercice 12.17 Écrire une fonction similaire à reversed, qui prend une pile en argument et renvoie une
autre pile constituée des mêmes éléments placés dans l’ordre inverse. On s’autorise à vider la pile fournie
en argument. Quelle est la complexité en temps et en espace de cette fonction ?
Exercice 12.18 * Tester dans différentes situations le comportement des boutons proposés par un navigateur Internet : visiter une nouvelle page, revenir d’une page en arrière, aller une page en avant.
Écrire un ensemble de fonctions simulant ces boutons. On pourra pour cet exercice utiliser deux piles.
Exercice 12.19 Écrire une fonction couper qui prend une pile et la coupe en enlevant de son sommet un
certain nombre d’éléments (tiré au hasard) qui sont renvoyés dans une seconde pile. Exemple : si la pile
initiale est [1, 2, 3, 4, 5] et si le nombre d’éléments retirés vaut 2, alors la pile ne contient plus que
[1, 2, 3] et la pile renvoyée contient [5, 4].
Exercice 12.20 * Mélange de cartes. Écrire une fonction melange qui prend en arguments deux piles
et qui mélange leurs éléments dans une troisième pile de la façon suivante : tant qu’une pile au moins
n’est pas vide, on retire aléatoirement un élément au sommet d’une des deux piles et on l’empile sur la
pile résultat. Exemple : un mélange possible des piles [1, 2, 3] et [5, 4] est [3, 2, 4, 1, 5]. Note : à
l’issue du mélange, les deux piles de départ sont donc vides.
Exercice 12.21 * Tour de magie de Gilbreath. Construire un paquet de cartes en empilant n fois
les mêmes k cartes (par exemple, pour un paquet de 32 cartes, on empile n = 16 paquets de paires
rouge/noir). Couper alors le paquet avec la fonction couper ci-dessus, puis mélanger les deux paquets
obtenus à l’aide de la fonction melange. On observe alors que le paquet final contient toujours n blocs
des mêmes k cartes (même si ces dernières peuvent apparaître dans un ordre différent au sein de chaque
bloc). Sur l’exemple des 16 paquets rouge/noir, on obtient toujours 16 paquets rouge/noir ou noir/rouge.
Exercice 12.22 ** Écrire une réalisation des tableaux redimensionnables en suivant l’idée décrite dans
l’encadré Pour aller plus loin page 305.