البـــــوابـــة
2.4 Fractales
Considérons d'autres exemples de programmes récursifs. Des exemples spectaculaires sont le cas de fonctions graphiques fractales. Nous utilisons les fonctions graphiques du Macintosh (cf. page X). Un premier exemple simple est le flocon de von Koch [11] qui est défini comme suit
<BLOCKQUOTE>
Figure 2.3 : Flocons de von Koch</BLOCKQUOTE>
<BLOCKQUOTE>Le flocon d'ordre 0 est un triangle équilatéral.
Le flocon d'ordre 1 est ce même triangle dont les côtés sont découpés en trois et sur lequel s'appuie un autre triangle équilatéral au milieu.
Le flocon d'ordre n+1 consiste à prendre le flocon d'ordre n en appliquant la même opération sur chacun de ses côtés. </BLOCKQUOTE>Le résultat ressemble effectivement à un flocon de neige idéalisé. L'écriture du programme est laissé en exercice. On y arrive très simplement en utilisant les fonctions trigonométriques sin et cos. Un autre exemple classique est la courbe du Dragon. La définition de cette courbe est la suivante: la courbe du Dragon d'ordre 1 est un vecteur entre deux points quelconques P et Q, la courbe du Dragon d'ordre n est la courbe du Dragon d'ordre n-1 entre P et R suivie de la même courbe d'ordre n-1 entre R et Q (à l'envers), où PRQ est le triangle isocèle rectangle en R, et R est à droite du vecteur PQ. Donc, si P et Q sont les points de coordonnées (x, y) et (z,t), les coordonnées (u, v) de R sont
<BLOCKQUOTE>
static void dragon(int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z + t - y) / 2;
v = (y + t - z + x) / 2;
dragon (n-1, x, y, u, v);
dragon (n-1, z, t, u, v);
}
}
Si on calcule dragon (20, 20, 20, 220, 220), on voit apparaître un petit dragon. Cette courbe est ce que l'on obtient en pliant 10 fois une feuille de papier, puis en la dépliant. Une autre remarque est que ce tracé lève le crayon, et que l'on préfère souvent ne pas lever le crayon pour la tracer. Pour ce faire, nous définissons une autre procédure dragonBis qui dessine la courbe à l'envers. La procédure dragon sera définie récursivement en fonction de dragon et dragonBis. De même, dragonBis est définie récursivement en termes de dragonBis et dragon. On dit alors qu'il y a une récursivité croisée.
static void dragon (int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z + t - y) / 2;
v = (y + t - z + x) / 2;
dragon (n-1, x, y, u, v);
dragonBis (n-1, u, v, z, t);
}
}
static void dragonBis(int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z - t + y) / 2;
v = (y + t + z - x) / 2;
dragon (n-1, x, y, u, v);
dragonBis (n-1, u, v, z, t);
}
}
Il y a bien d'autres courbes fractales comme la courbe de Hilbert, courbe de Peano qui recouvre un carré, les fonctions de Mandelbrot. Ces courbes servent en imagerie pour faire des parcours ``aléatoires'' de surfaces, et donnent des fonds esthétiques à certaines images.
2.5 Quicksort
Cette méthode de tri est due à C.A.R Hoare en 1960. Son principe est le suivant. On prend un élément au hasard dans le tableau à trier. Soit v sa valeur. On partitionne le reste du tableau en 2 zones: les éléments plus petits ou égaux à v, et les éléments plus grands ou égaux à v. Si on arrive à mettre en tête du tableau les plus petits que v et en fin du tableau les plus grands, on peut mettre v entre les deux zones à sa place définitive. On peut recommencer récursivement la procédure Quicksort sur chacune des partitions tant qu'elles ne sont pas réduites à un élément. Graphiquement, on choisit v comme l'un des ai à trier. On partitionne le tableau pour obtenir la position de la figure 2.5 (c). Si g et d sont les bornes à gauche et à droite des indices du tableau à trier, le schéma du programme récursif est
static void qSort(int g, int d) {
if (g < d) {
v = a[g];
Partitionner le tableau autour de la valeur v
et mettre v à sa bonne position m
qSort (g, m-1);
qSort (m+1, d);
}
}
Nous avons pris a[g] au hasard, toute autre valeur du tableau a aurait convenu. En fait, la prendre vraiment au hasard ne fait pas de mal, car ça évite les problèmes pour les distributions particulières des valeurs du tableau (par exemple si le tableau est déjà trié). Plus important, il reste à écrire le fragment de programme pour faire la partition. Une méthode ingénieuse [6] consiste à parcourir le tableau de g à d en gérant deux indices i et m tels qu'à tout moment on a aj < v pour g < j £ m, et aj ³ v pour m < j < i. Ainsi
<BLOCKQUOTE>
Figure 2.5 : Partition de Quicksort</BLOCKQUOTE>m = g;
for (i = g+1; i <= d; ++i)
if (a < v) {
++m;
x = a[m]; a[m] = a[i]; a[i] = x; // Echanger [i]am et ai
}
ce qui donne la procédure suivante de Quicksort
static void qSort(int g, int d) {
int i, m, x, v;
if (g < d) {
v = a[g];
m = g;
for (i = g+1; i <= d; ++i)
if (a < v) {
++m;
x = a[m]; a[m] = a[i]; a[i] = x; // Echanger [i]am et ai
}
x = a[m]; a[m] = a[g]; a[g] = x; // Echanger am et ag
qSort (g, m-1);
qSort (m+1, d);
}
}
Cette solution n'est pas symétrique. La présentation usuelle de Quicksort consiste à encadrer la position finale de v par deux indices partant de 1 et N et qui convergent vers la position finale de v. En fait, il est très facile de se tromper en écrivant ce programme. C'est pourquoi nous avons suivi la méthode décrite dans le livre de Bentley [6]. Une méthode très efficace et symétrique est celle qui suit, de Sedgewick [47].
static void quickSort(int g, int d) {
int v,t,i,j;
if (g < d) {
v = a[d]; i= g-1; j = d;
do {
do
++i;
while (a < v);
do
--j;
while (a[j] > v);
t = a[i]; a[i] = a[j]; a[j] = t;
} while (j > i);
a[j] = a[i]; a[i] = a[d]; a[d] = t;
quickSort (g, i-1);
quickSort (i+1, d);
}
}
On peut vérifier que cette méthode ne marche que si des sentinelles à gauche et à droite du tableau existent, en mettant un plus petit élément que [i]v à gauche et un plus grand à droite. En fait, une manière de garantir cela est de prendre toujours l'élément de gauche, de droite et du milieu, de mettre ces trois éléments dans l'ordre, en mettant le plus petit des trois en a1, le plus grand en aN et prendre le médian comme valeur v à placer dans le tableau a. On peut remarquer aussi comment le programme précédent rend bien symétrique le cas des valeurs égales à v dans le tableau. Le but recherché est d'avoir la partition la plus équilibrée possible. En effet, le calcul du nombre moyen CN de comparaisons emprunté à [47] donne C0 = C1 = 0, et pour N ³ 2,
Considérons d'autres exemples de programmes récursifs. Des exemples spectaculaires sont le cas de fonctions graphiques fractales. Nous utilisons les fonctions graphiques du Macintosh (cf. page X). Un premier exemple simple est le flocon de von Koch [11] qui est défini comme suit
<BLOCKQUOTE>
Figure 2.3 : Flocons de von Koch
<BLOCKQUOTE>Le flocon d'ordre 0 est un triangle équilatéral.
Le flocon d'ordre 1 est ce même triangle dont les côtés sont découpés en trois et sur lequel s'appuie un autre triangle équilatéral au milieu.
Le flocon d'ordre n+1 consiste à prendre le flocon d'ordre n en appliquant la même opération sur chacun de ses côtés. </BLOCKQUOTE>Le résultat ressemble effectivement à un flocon de neige idéalisé. L'écriture du programme est laissé en exercice. On y arrive très simplement en utilisant les fonctions trigonométriques sin et cos. Un autre exemple classique est la courbe du Dragon. La définition de cette courbe est la suivante: la courbe du Dragon d'ordre 1 est un vecteur entre deux points quelconques P et Q, la courbe du Dragon d'ordre n est la courbe du Dragon d'ordre n-1 entre P et R suivie de la même courbe d'ordre n-1 entre R et Q (à l'envers), où PRQ est le triangle isocèle rectangle en R, et R est à droite du vecteur PQ. Donc, si P et Q sont les points de coordonnées (x, y) et (z,t), les coordonnées (u, v) de R sont
| u = (x + z)/2 + (t - y)/2 |
| v = (y + t)/2 - (z - x)/2 |
<BLOCKQUOTE>
Figure 2.4 : La courbe du Dragon
</BLOCKQUOTE>La courbe se programme simplement parstatic void dragon(int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z + t - y) / 2;
v = (y + t - z + x) / 2;
dragon (n-1, x, y, u, v);
dragon (n-1, z, t, u, v);
}
}
Si on calcule dragon (20, 20, 20, 220, 220), on voit apparaître un petit dragon. Cette courbe est ce que l'on obtient en pliant 10 fois une feuille de papier, puis en la dépliant. Une autre remarque est que ce tracé lève le crayon, et que l'on préfère souvent ne pas lever le crayon pour la tracer. Pour ce faire, nous définissons une autre procédure dragonBis qui dessine la courbe à l'envers. La procédure dragon sera définie récursivement en fonction de dragon et dragonBis. De même, dragonBis est définie récursivement en termes de dragonBis et dragon. On dit alors qu'il y a une récursivité croisée.
static void dragon (int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z + t - y) / 2;
v = (y + t - z + x) / 2;
dragon (n-1, x, y, u, v);
dragonBis (n-1, u, v, z, t);
}
}
static void dragonBis(int n, int x, int y, int z, int t) {
int u, v;
if (n == 1) {
moveTo (x, y);
lineTo (z, t);
} else {
u = (x + z - t + y) / 2;
v = (y + t + z - x) / 2;
dragon (n-1, x, y, u, v);
dragonBis (n-1, u, v, z, t);
}
}
Il y a bien d'autres courbes fractales comme la courbe de Hilbert, courbe de Peano qui recouvre un carré, les fonctions de Mandelbrot. Ces courbes servent en imagerie pour faire des parcours ``aléatoires'' de surfaces, et donnent des fonds esthétiques à certaines images.
2.5 Quicksort
Cette méthode de tri est due à C.A.R Hoare en 1960. Son principe est le suivant. On prend un élément au hasard dans le tableau à trier. Soit v sa valeur. On partitionne le reste du tableau en 2 zones: les éléments plus petits ou égaux à v, et les éléments plus grands ou égaux à v. Si on arrive à mettre en tête du tableau les plus petits que v et en fin du tableau les plus grands, on peut mettre v entre les deux zones à sa place définitive. On peut recommencer récursivement la procédure Quicksort sur chacune des partitions tant qu'elles ne sont pas réduites à un élément. Graphiquement, on choisit v comme l'un des ai à trier. On partitionne le tableau pour obtenir la position de la figure 2.5 (c). Si g et d sont les bornes à gauche et à droite des indices du tableau à trier, le schéma du programme récursif est
static void qSort(int g, int d) {
if (g < d) {
v = a[g];
Partitionner le tableau autour de la valeur v
et mettre v à sa bonne position m
qSort (g, m-1);
qSort (m+1, d);
}
}
Nous avons pris a[g] au hasard, toute autre valeur du tableau a aurait convenu. En fait, la prendre vraiment au hasard ne fait pas de mal, car ça évite les problèmes pour les distributions particulières des valeurs du tableau (par exemple si le tableau est déjà trié). Plus important, il reste à écrire le fragment de programme pour faire la partition. Une méthode ingénieuse [6] consiste à parcourir le tableau de g à d en gérant deux indices i et m tels qu'à tout moment on a aj < v pour g < j £ m, et aj ³ v pour m < j < i. Ainsi
<BLOCKQUOTE>
Figure 2.5 : Partition de Quicksort
for (i = g+1; i <= d; ++i)
if (a < v) {
++m;
x = a[m]; a[m] = a[i]; a[i] = x; // Echanger [i]am et ai
}
ce qui donne la procédure suivante de Quicksort
static void qSort(int g, int d) {
int i, m, x, v;
if (g < d) {
v = a[g];
m = g;
for (i = g+1; i <= d; ++i)
if (a < v) {
++m;
x = a[m]; a[m] = a[i]; a[i] = x; // Echanger [i]am et ai
}
x = a[m]; a[m] = a[g]; a[g] = x; // Echanger am et ag
qSort (g, m-1);
qSort (m+1, d);
}
}
Cette solution n'est pas symétrique. La présentation usuelle de Quicksort consiste à encadrer la position finale de v par deux indices partant de 1 et N et qui convergent vers la position finale de v. En fait, il est très facile de se tromper en écrivant ce programme. C'est pourquoi nous avons suivi la méthode décrite dans le livre de Bentley [6]. Une méthode très efficace et symétrique est celle qui suit, de Sedgewick [47].
static void quickSort(int g, int d) {
int v,t,i,j;
if (g < d) {
v = a[d]; i= g-1; j = d;
do {
do
++i;
while (a < v);
do
--j;
while (a[j] > v);
t = a[i]; a[i] = a[j]; a[j] = t;
} while (j > i);
a[j] = a[i]; a[i] = a[d]; a[d] = t;
quickSort (g, i-1);
quickSort (i+1, d);
}
}
On peut vérifier que cette méthode ne marche que si des sentinelles à gauche et à droite du tableau existent, en mettant un plus petit élément que [i]v à gauche et un plus grand à droite. En fait, une manière de garantir cela est de prendre toujours l'élément de gauche, de droite et du milieu, de mettre ces trois éléments dans l'ordre, en mettant le plus petit des trois en a1, le plus grand en aN et prendre le médian comme valeur v à placer dans le tableau a. On peut remarquer aussi comment le programme précédent rend bien symétrique le cas des valeurs égales à v dans le tableau. Le but recherché est d'avoir la partition la plus équilibrée possible. En effet, le calcul du nombre moyen CN de comparaisons emprunté à [47] donne C0 = C1 = 0, et pour N ³ 2,
