Informatique -- Tronc Commun
TD 2 -- Récursivité, Médiane

Benjamin Werner, Eric Schost

25 Octobre 1999






Objet

L'objet de la session d'ajourd'hui est essentiellement de découvrir la programmation récursive, c'est-à-dire des fonctions qui sont définies en fonction d'elles-même.

L'exemple choisi est le calcul de la médiane dans un tableau. On commencera par deux mini-exercices rapides.

1   Mini-exo: les tableaux paramètres d'une méthode

On rappelle qu'en java, méthode désigne les fonctions ou procédures. Lorsqu'un tableau est passé en paramètre d'une méthode, c'est en fait son adresse mémoire qui est pasée en paramètre.

Donc les modifications faites sur le tableau dans la méthode sont permanentes.

Voici quelques petits programmes. Regardez-les et devinez le résultat. Vérifiez en les executant. Demandez-nous des explications le cas échéant.

public class Exemple {
    static int[] tab = {0,1,2,3};

    public static void ajoute (int[] t, int i) {
        t[i]=t[i]+2;
        return ;
    }

    public static void main (String[] args) {
        ajoute(tab,3);
        ajoute(tab,3);
        System.out.print(tab[3]);
        System.out.print(" ");
        System.out.print(tab[2]);
        System.out.print("\n");     //pour aller à la ligne
    }
}
Un autre un tout petit plus rusé: 
public class Exemple2 {
    static int[] tab = {0,1,2,3};

    public static void ajoute (int[] t1, int[] t2, int i) {
        t1[i]=t1[i]+2;
        t2[i]=t2[i]+3;
        return ;
    }

    public static void main (String[] args) {
        ajoute(tab, tab, 3);
        System.out.print(tab[3]);
        System.out.print(" ");
        System.out.print(tab[2]);
        System.out.print("\n");     //pour aller à la ligne
    }
}

2   Mini-exo de récursivité: la factorielle

Complétez le programme ci-dessous pour qu'il affiche la factorielle de 6. Faites au moins la version récursive du programme; deux lignes suffisent.

Vous pouvez, en sus, faire la version itérative (c'est-à-dire avec une boucle for).

public class Fact {

    public static int fact (int n) {
        ........
        ........
    }

    public static void main (String[] args) {
        System.out.print(fact(6));
        System.out.print("\n");
    }
}
Voici les solutions.

3   Calcul de la médiane dans un tableau

La médiane d'un ensemble de n nombres est le nombre qui est plus grand que la moitié de ces nombres, et plus petit que l'autre moitié de ces nombres. Autrement dit, c'est le nombre qui se trouve au milieu du tableau si on trie celui-ci.

La médiane est donc différente de la moyenne, mais c'est une indication statistique aussi intéressante.

Du coup, une méthode naïve pour trouver la médiane consiste à trier les n objets et à renvoyer l'élément d'indice n/2. La complexité de cette algorithme est en O(n log(n)) à cause du tri. Aujourd'hui nous allons programmer l'algorithme quickselect due à Hoare dont la complexité moyenne est O(n).

3.1   Partitionnement

C'est la partie la plus délicate de l'algorithme. On considère une partie de tableau t[i] pour i compris entre g et d et on se donne un pivot t[k]. Il s'agit alors de partitionner le tableau de manière à ce que les éléments du tableau plus petits que le pivot soient à gauche de celui-ci; ceux qui sont plus grands à droite. Le pivot lui-même est donc à sa place définitive.

La méthode prend donc trois arguments: le tableau et les bornes d et g. Elle ré-arrange le tableau et rend la position du pivot en résultat. Ici on choisira t[g] comme pivot, pour simplifier.

Une manière simple de faire la partition consiste à utiliser un tableau annexe u, de taille d-g. On parcourt alors t[g... d] et on range recopie les t[i] à gauche ou à droite dans le tableau u. A la fin, on met le pivot à sa place, et on recopie u dans la portion correspondante de t.

  1. Créez le fichier qui contiendra le programme.
  2. Ecrivez la fonction de partitionnement décrite ci-dessus.
  3. Testez cette fonction en affichant l'exécutant sur un petit tableau, par exemple 
            int[] tab_test = {3,5,9,1,0,2,1};

3.2   La médiane

C'est la partie récursive du programme. En fait, cet algorithme est assez général pour trouver l'élément en position k dans le tableau trié (pour la médiane, on prend k=n/2). Le principe est le suivant:

Questions

  1. Ecrire la fonction Select qui prend en argument le tableau, les bornes g et d et le rang k de l'élément cherché. Cette fonction doit rendre la valeur de l'élément de rang k.
  2. Testez cette fonction sur quelques petits tableaux définis à la main, ou bien en utilisant la fonction suivante, qui fabrique un tableau, permutation aléatoire de [0,..., n-1]. L'intérêt pour le test est que la valeur de l'élément de rang k à pour valeur k.
  3. Modifiez main pour qu'il récupère sur la ligne de commande la longueur du tableau ainsi que le rang de l'élément cherché.

3.3   Animation graphique

Vous pouvez maintenant animer votre programme; pour cela:

3.4   Solution

Vous en trouvez une possible ici.

3.5   Amélioration possible

Il est possible d'éviter l'utilisation d'un tableau auxiliaire pour le partitionnement; il faut juste eviter alors de se mélanger les pinceaux dans les indices.

Il existe enfin de nombreuses astuces pour faire le minimum de comparaisons lors du partitionnement; vous pouvez jeter un oeil au poly.

4   Tri rapide

L'algorithme de tri rapide, ou quicksort, également du à Hoare, est quasiment identique à quickselect. La seule différence est qu'après avoir partitionné le tableau, la procédure de tri s'appelle récursivement sur les deux moitiés du tableau (et non pas juste sur celle qui contient la médiane).

Les plus rapides peuvent s'amuser à transformer leur programme de médiane en programme de tri; personnellement je n'ai pas eu le temps de faire une animation.

This document was translated from LATEX by HEVEA.