Course list Register Sign in

Information

Author(s) Pierre Schaus
Deadline 08/10/2019 17:00:00
Submission limit No limitation

Sign in

Sign in

PART 2 - Median (implem)

Nous vous donnons l'API d'une classe Vector permettant d'accéder, modifier et interchanger deux élements en temps constant. Votre tâche est d'implémenter une méthode permettant de calculer la médiane d'un Vecteur.

public interface Vector {
    // taille du vecteur
    public int size();
    // mets la valeur v à l'indice i du vecteur
    public void set(int i, int v);
    // renvoie la valeur à l'indice i du vecteur
    public int get(int i);
    // échange les valeurs aux positions i et j
    public void swap(int i, int j);

}

Le projet IntelliJ est disponible ici.

Implementation de la median

Vous devez implémenter une méthode qui a la signature suivante:

public static int median(Vector a, int lo, int hi)

Cette méthode calcule la médiane du vector "a" entre les positions "lo" et "hi" (incluses).

Vous pouvez considérer que le vector "a" a toujours une taille impaire.

Pour vous aider, un projet IntelliJ avec un test minimaliste pour vérifier si votre code calcule la bonne valeur médiane est donné. En effet, il n'est pas conseillé de débugger son code via Inginious.

Attention Il n'est pas interdit de modifier ou d'interchanger des elements du vecteur "a" durant le calcul (avec les methodes get/set/swap). Il est interdit de faire appel à d'autres méthodes de la librairie standard Java. Il est également interdit de faire un "new".

L'évaluation porte sur sur 10 points:

  • bonne valeur de retour: 3 points,
  • bonne valeur de retour et complexité O(n log n): 5 points,
  • bonne valeur de retour et complexité O(n) expected (cas moyen sur une distribution uniforme aléatoire): 10 points.

Tout le code que vous écrirez dans le champ texte sera substitué à l'endroit indiqué ci-dessous. Vous êtes libre d'implémenter éventuellement d'autres méthodes pour vous aider dans cette classe mais la méthode "median" donnée ci-dessus doit au moins y figurer.

public class Median {
    // votre code sera substitué ici
}