Les méthodes de tous les exercices doivent être écrites
dans les classes fournies en annexe
(télécharger ces classes)
.
EXERCICE 1
On considère les entiers écrits en binaires et on cherche à générer
tous les entiers binaires d'une longueur donnée. Par exemple, tous les
entiers binaires de trois chiffres sont :
| |
| 000 |
|
001 |
|
010 |
|
100 |
|
011 |
|
110 |
|
101 |
|
111 |
|
Ecrivez la méthode imprimer(int k) de la classe Binaire telle
que imprimer(k) imprime sur le flux de sortie tous les entiers binaires
de longueur k. Calculez la complexité de cette méthode.
Ecrivez une méthode annexe (et privée) récursive qui imprime tous les
entiers binaires de longueur k précédés d'un préfixe (une
chaîne de caractères) donné.
EXERCICE 2
On considère les mots écrits à l'aide des deux lettres x et y et on cherche à générer tous les mots contenants un nombre
particulier de x et un nombre particulier de y. Par exemple,
tous les mots contenants exactement trois x et deux y sont :
| yyxxx |
|
yxyxx |
|
yxxyx |
|
yxxxy |
|
xyyxx |
|
xyxyx |
|
xyxxy |
|
xxyyx |
|
xxyxy |
|
xxxyy |
Ecrivez la méthode imprimer(int p, int q) de la classe Mots
telle que imprimer(p,q) imprime sur le flux de sortie tous les mots
contenants exactement p fois la lettre x et q fois la
lettre y. Calculez la complexité de cette méthode.
Même chose que précédemment !
EXERCICE 3
Soit T un tableau contenant n entiers positifs ou nuls e0, e1,
... ,en-1. Les valeurs de T sont positives ou nulles et apparaissent
dans un ordre quelconque.
Ecrivez la méthode possible(int i) de la classe Somme telle que
possible(i) teste s'il existe un sous ensemble S de T tel que la
somme des éléments de S est egale à i. Calculez la complexité de
cette méthode.
Ecrivez et urilisez une méthode annexe (privée) récursive qui teste
s'il existe un sous ensemble S de Tk tel que la somme des éléments
de S est egale à i, où Tk est l'ensemble de k premières
valeurs du tableau.
EXERCICE 4
Un voleur dévalise un magasin et dispose d'un sac pour emporter des
objets. Il y a dans le magasin n objets, et chaque objet xi (0 £ i
£ n-1) possède un poids pi et une valeur vi. De plus, le
voleur ne peut pas emporter plus de P kilos dans son sac.
Ecrivez la méthode valeur(int P) de la classe Voleur qui
retourne la valeur maximale du butin que le voleur peut emporter sans
dépsaaser le poids maximal P. Calculez la complexité de cette
méthode.
Ecrivez et utilisez une méthode annexe (privée) récursive qui
détermine la valeur maximale du butin que le voleur peut emporter sans
dépasser un certain poids et en choisissant parmi les k premiers objets.
EXERCICE 5
On suppose qu'on a un réseau informatique constitué de n sites
numérotés de 0 à n-1. Une matrice connexion permet de savoir
s'il existe une ligne directe entre les sites i et j. Ainsi
connexion[i][j] = true si et seulement s'il existe une ligne directe
entre les sites i et j. S'il n'existe pas de ligne directe entre
les sites i et j, on peut néanmoins se connecter de i à
j en passant par d'autres sites.
Ecrivez la méthode connecte(int i, int j) de la classe Connexion qui détermine pour tout couple (i,j) si l'on peut se
connecter de i à j sur ce réseau en passant éventuellement
par d'autres sites. Calculez la complexité de cette méthode.
Ecrivez et utilisez une méthode annexe (privée) récursive qui
détermine si on peut se connecter de i à j en passant
éventuellement par un, zéro, ou plusieurs des k premiers sites.
On suppose maintenant que les connexions ont un coût. Comment peut-on
stocker cette information ?
Complétez la classe Distance et écrivez la méthode cout(int
i, int j) de cette classe qui calcule pour tout couple de sites (i,j) le
coût minimum pour se connecter de i à j, en passant éventuellement
par d'autres sites. Calculez la complexité de cette méthode.
Même chose que précédemment !
EXERCICE 6
On s'intéresse aux permutations d'ordre n pour un n > 1 donné. Par
exemple, toutes les permutations d'ordre 3 sont :
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
Ecrivez la méthode imprimer(int k) de la classe Permutation
telle que imprimer(k) imprime sur le flux de sortie toutes les
permutations d'ordre k. Calculez la complexité de cette
méthode.
Ecrivez et utilisez une méthode annexe (et privée) récursive qui
permute et imprime un tableau contenant les entiers 1,2,...,n.
This document was translated from LATEX by
HEVEA.