Aller au contenu

Lab 02

Bienvenue au deuxième laboratoire ! Précédemment, nous avons vérifié votre configuration, et vous devriez maintenant savoir comment compiler de simples programmes Java depuis le code source jusqu’au bytecode Java en ligne de commande et comment exécuter votre code.

À partir de maintenant, nous utiliserons l’IDE IntelliJ pour écrire du code. Cependant, gardez à l’esprit que l’IDE n’ajoute aucune magie : en son cœur, c’est juste un éditeur de texte avancé avec des éléments d’interface pour invoquer les outils standards de Java, comme le compilateur et la machine virtuelle Java.

Dans ce laboratoire, nous allons rafraîchir quelques notions de base de Java et ajouter un peu de pratique sur les paradigmes de programmation vus en classe.

Orientation objet

  • Tout au long du reste du cours, nous travaillerons exclusivement avec les concepts orientés objet (OO).
  • Avant de plonger dans les pratiques OO essentielles, nous récapitulerons un concept fondamental : les classes, les objets et les secrets de classe.

Classes et objets

Les classes Java ne sont pas les mêmes que les objets Java.

  • Une classe est un modèle.
    • Une classe définit des propriétés et comportements communs.
  • Un objet est une instance d’une classe.
    • Il attribue des valeurs concrètes aux propriétés définies.
    • Il peut exécuter des comportements en utilisant ces valeurs.

Illustration

  • Lorsque vous vous promenez dans les rues de Montréal, vous voyez de nombreuses voitures.
    • Elles occupent de l’espace
    • Elles ont des valeurs de propriétés concrètes, par exemple : pèse 1,4 tonne, contient 40 L de carburant, a 83 CV.
    • Elles peuvent exécuter des comportements, comme accélérer, freiner, faire le plein, ...
Quel concept correspond à chacune de ces voitures ?

Un objet : elles ont des valeurs concrètes et peuvent exécuter des comportements.

Quel concept serait le mieux adapté pour décrire les points communs de toutes ces voitures ?

Une classe : la classe définit les propriétés (sans valeurs concrètes), comme "poids", "consommation de carburant", "puissance", et la classe définit les comportements comme "accélérer", "freiner", "faire le plein", ...

Une autre façon de récapituler :

  • Les classes sont des plans.
  • Les objets sont des instances, créées à partir de ces plans.

Garder les secrets de classe

Généralement, vous voulez concevoir vos classes de sorte que les objets reflètent une notion de sécurité, c’est-à-dire qu’aucune situation étrange ne se produise lorsque nous créons des objets à partir du plan de la classe.

Exemple :

  • Les plans de voitures sont conçus pour que le carburant ne puisse être ajouté que, jamais retiré (sauf en conduisant).
  • En fait, ce serait problématique si les voitures pouvaient vider du carburant sur l’asphalte à volonté.
  • Si le plan de la voiture est conçu pour interdire de vider le carburant, aucun des objets voiture ne pourra le faire.

Accès ouvert

Avec l’exemple du carburant ci-dessus en tête, quel est le problème avec l’implémentation suivante de la classe Car ?

public class Car {

    public int remainingFuel = 50;
    public int mileage = 200;
    public int horsepower = 80;
    public int speed = 0;

    public void accelerate() {
        speed = speed + 10;
        System.out.println("Vroooooom");
    }

    public void slowDown() {
        speed = speed - 10;
        System.out.println("Screeeeech");
    }

    public void fuelUp() {
        remainingFuel = 100;
        System.out.println("Glug, glug, glug");
    }
}
Quel est le problème ?

Tous les champs sont publics. Les voitures auraient un réservoir accessible ouvertement. N’importe qui pourrait ajouter ou retirer du carburant à tout moment. Même chose pour tous les autres champs.

Accès restreint

  • En Java, vous ne voulez presque jamais que les champs d’une classe soient public.
  • Un champ public équivaut à dire "Je me fiche de la sécurité, je suppose que personne ne fait jamais d’erreurs de programmation ou n’utilise mon code autrement que prévu."

Créez une version sécurisée du code ci-dessus :

  • Assurez-vous que le carburant ne peut être qu’ajouté, jamais retiré.

Autres langages

  • De nombreux langages de script, par exemple Python, n’ont pas de concept réel pour protéger les champs.
  • Au début, cela peut sembler plus facile (je n’ai pas besoin de m’inquiéter de la sécurité, donc je programme plus vite ma petite application)
  • En réalité, l’absence de concepts de sécurité est rarement un avantage. Le fait qu’une solution "fonctionne" ne signifie pas que c’est une bonne solution :

On se fiche que ça fonctionne

Dans ce cours, on se fiche que le code "fonctionne". Un code fonctionnel est le minimum que nous attendons. Dans ce cours, ce qui compte, c’est la qualité de la solution, c’est-à-dire si elle est fiable, adaptée, solide et élégante.

Boucle et récursion

Dans ce deuxième segment, nous allons examiner un autre thème de paradigme abordé lors de la dernière séance : les différentes façons d’implémenter des itérations.

Mais avant d’entraîner les allers-retours entre boucles et équivalents récursifs, voici un bref rappel de la syntaxe Java.

  • Nous regardons l’exemple de la somme d’entiers, c’est-à-dire que pour un nombre donné n, nous voulons calculer la somme de tous les nombres inférieurs ou égaux à n.
  • Exemple : pour n = 5, nous voulons calculer 1 + 2 + 3 + 4 + 5

Techniquement, on peut faire mieux

L’exemple est un peu artificiel, car comme vous le savez certainement, nous pourrions aussi utiliser la formule de Gauss et éviter toute boucle ou récursion :
sum(n) = n*(n+1) / 2.
Mais pour le fun, nous allons faire comme si nous n’avions jamais entendu parler de Gauss et devons donc calculer le résultat étape par étape.

Exemple de syntaxe de boucle

En Java, une boucle est assez simple à écrire :

public static void main(String[] args) {
    System.out.println(addAll(100));
}

// Loop implementation (we're using a for loop to iterate)
public static int addAll(int limit) {
    int sum = 0;
    for (int i = 0; i <= limit; i++) {
        sum = sum + i;
    }
    return sum;
}

L’instruction for nous permet d’effectuer des calculs de manière répétée (ajouter +i), jusqu’à ce qu’un critère de fin soit atteint (nous avons atteint 100).

Exemple de syntaxe récursive

Mais que faire si aucune instruction for n’est autorisée (ou si nous travaillons avec un langage non impératif) ?
Dans cet exemple, nous resterons sur la syntaxe Java, mais nous verrons comment obtenir le même résultat avec un appel récursif :

public static void main(String[] args) {
    System.out.println(sum(100));
}

// Loop implementation (we're using recursion to iterate)
public static int sum(int i) {

    // End recursion criteria
    if (i == 1) {
        return 1;
    }

    // Otherwise continue recursion
    return sum(i - 1) + i;
}

Regardez la dernière ligne : sum(i-1) + i. Nous n’avons pas de boucle, mais en déléguant simplement à l’itération suivante via la récursion, nous pouvons tout de même additionner tous les nombres.

Conversion

  • Un principe de base de la programmation est que tout algorithme exprimé sous forme de boucle peut être converti en équivalent récursif et vice-versa. Cependant, l’équivalent n’est pas toujours évident.
  • Dans les exercices suivants, vous devez trouver l’équivalent :
    • Je vous fournirai une implémentation récursive et vous devrez écrire le code Java correspondant utilisant une boucle.
    • Je vous fournirai une implémentation avec une boucle et vous devrez écrire le code Java récursif correspondant.

Récursion vers boucle

Ci-dessous, vous trouverez une très courte fonction Java. Il s’agit d’une implémentation de la conjecture de Collatz.

Version récursive

  • Essayez de comprendre ce que fait ce code et exprimez l’algorithme avec vos propres mots.
  • Lorsque vous pensez avoir compris, vérifiez votre réponse avec la boîte verte ci-dessous.

Essayez simplement

Vous pouvez le simuler sur une feuille de papier, par exemple pour une valeur initiale de 4.

public static void collatz(int n) throws InterruptedException {

    System.out.println(n);

    // Just a little sleep, so you can observe what is going on.
    Thread.sleep(300);

    if (n % 2 == 0)
        collatz(n / 2);
    else
        collatz(n * 3 + 1);
}
Quel est l’algorithme ?

Il s’agit d’une récursion infinie. À chaque étape, le nombre courant est soit :
- Divisé par 2 (s’il est pair)
- Multiplié par 3, puis additionné de 1 (s’il est impair)
La même logique peut être implémentée avec une boucle infinie.

À votre tour

Remplissez les blancs :

  • Convertissez le code fourni en une version utilisant une boucle.
  • Vérifiez votre solution en exécutant le code : comparez les sorties de votre programme itératif avec celles du programme récursif fourni.
public static void main(String[] args) throws InterruptedException {
    collatz(100);
}

public static void collatz(int n) throws InterruptedException {
    // ... your code here.
}
Des observations après avoir essayé plusieurs entrées ?

Il semble que quel que soit le nombre de départ, la série se termine toujours par une boucle : 4 -> 2 -> 1.
Curieusement, bien que tous les nombres testés finissent par la même boucle, personne n’a jamais trouvé de preuve.
(Si vous trouvez une preuve, faites-le-moi savoir !)

Boucle vers récursion

Cet exercice final est l’équivalent du précédent. Vous devez convertir une implémentation avec boucle en une implémentation récursive, c’est-à-dire sans while ni for.

Version avec boucle

  • Cette fois, je ne vous dis pas ce que fait la fonction.
  • Regardez bien le code et essayez de le comprendre. Lorsque vous pensez avoir compris, vérifiez votre compréhension avec la boîte verte ci-dessous.
  public static void main(String[] args) throws InterruptedException
  {
    // Initialize numbers
    int i1 = 1;
    int i2 = 1;
    int iterationCounter = 0;

    // An end-condition could be, we want to stop after 10 iterations.
    while (iterationCounter < 10)
    {

      System.out.println(i1);
      Thread.sleep(300);
      int nextNumber = i1 + i2;
      i1 = i2;
      i2 = nextNumber;

      // Don't forget to increment the counter, so our loop actually stops eventually:
      iterationCounter++;
    }
  }
À quoi sert cette fonction ?

Il s’agit d’une implémentation de la suite Fibonacci.
Elle affiche les nombres de Fibonacci (le nombre suivant est toujours la somme des deux précédents), donc : 1, 1, 2, 3, 5, ...

À votre tour

Remplissez les blancs :

  • Convertissez le code fourni en une version récursive.
  • Vérifiez votre solution en exécutant le code : comparez les sorties de votre programme itératif avec celles du programme récursif fourni.
public static void main(String[] args) throws InterruptedException {
    // Initialize numbers
    int i1 = 1;
    int i2 = 1;
    int iterationCounter = 10;
    // Start recursion
    fib(i1, i2, iterationCounter);
}

public static void fib(...your parameters here) throws InterruptedException {
    // Your code here...
}