Algo avancée 2e journée

Vincent Tam

18 avril 2023

Template ExoN.java

import java.util.Locale;
import java.util.Scanner;
import java.util.InputMismatchException;
import java.util.Objects;

/*
 * Class description
 *
 * @author vtam
 */
public class ExoN {
    public static void main(String[] args) {
        // get console input for array, adjust array's type if needed
        int arrayLength = getIntInput("Entrez la taille du tableau : ");
        double[] array = new double[arrayLength];
        for (int i = 0; i < array.length; i++) {
            array[i] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
        }

        // write your logic here

        // display each array element in an entier line
        for (int i = 0; i < array.length; i++) {
            System.out.println("tableau[" + i + "] = " + array[i]);
        }
    }

    // auxiliary functions to obtain user input and to handle
    // InputMismatchException
    public static void displayError(String message) {
        System.err.println(message);
        System.exit(-1);
    }

    public static int getIntInput(String message) {
        return getIntInput(message, "Erreur de saisie.");
    }

    public static int getIntInput(String message, String errorMessage) {
        System.out.print(message);
        Scanner input = new Scanner(System.in).useLocale(Locale.US);
        try {
            return input.nextInt();
        } catch (InputMismatchException e) {
            displayError(errorMessage);
        }
        return -1; // useless return to pass the compiler
    }

    public static double getDoubleInput(String message) {
        return getDoubleInput(message, "Erreur de saisie.");
    }

    public static double getDoubleInput(String message, String errorMessage) {
        System.out.print(message);
        Scanner input = new Scanner(System.in).useLocale(Locale.US);
        try {
            return input.nextDouble();
        } catch (InputMismatchException e) {
            displayError(errorMessage);
        }
        return -1; // useless return to pass the compiler
    }
}

Remarques pour le template

Exo 4 : somme des éléments dans le tableau

<TypeNumérique> FONCTION somme(T : tableau[max] de type numérique)
DEBUT
  VAR i, somme : ENTIER
  somme ← T[0]
  POUR i ALLANT DE 1 à max-1 PAR PAS DE 1 FAIRE
    somme ← somme + T[i]
  FINPOUR
  RETOURNER somme
FIN

Bon usage :

Exo 5 : tri par sélection

Difficultés :

Exo 5 : code Java

int arrayLength = getIntInput("Entrez la taille du tableau : ");
double[] array = new double[arrayLength];
double target = 0;
for (int i = 0; i < array.length; i++) {
    array[i] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
}

double curMin = 0;
double temp = 0;
int curMinIdx = 0;

// loop on diminishing tails' head
for (int i = 0; i < array.length - 1; i++) {
    curMin = array[i]; // min in beheaded tail
    temp = 0; // temp var for swapping
    curMinIdx = 1; // index for curMin
    for (int j = i + 1; j < array.length; j++) {
        if (array[j] < curMin) {
            curMin = array[j];
            curMinIdx = j;
        }
    }
    // swap if head > curMin in tail
    if (curMinIdx > 1) {
        temp = array[i];
        array[i] = array[curMinIdx];
        array[curMinIdx] = temp;
    }
}

// display each array element in an entier line
for (int i = 0; i < array.length; i++) {
    System.out.println("tableau[" + i + "] = " + array[i]);
}

Exo 6 : tri par insertion

On est invité à regarder la page pertinente sur Wiki.

int arrayLength = getIntInput("Entrez la taille du tableau : ");
double[] array = new double[arrayLength];
double target = 0;
for (int i = 0; i < array.length; i++) {
    array[i] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
}

// loop on diagonal element array[i]
double diagonal = 0;
int insIdx = 0;
for (int i = 1; i < array.length; i++) {
    diagonal = array[i];
    insIdx = i;
    // find insertion element in growing heads
    while (insIdx > 0 && diagonal < array[insIdx - 1]) {
        array[insIdx] = array[insIdx - 1];
        insIdx--;
    }
    // insert diagonal element in the "hole" array
    array[insIdx] = diagonal;
}

// display each array element in an entier line
for (int i = 0; i < array.length; i++) {
    System.out.println("tableau[" + i + "] = " + array[i]);
}

Exo 7 : tri à bulles

Exo 7 : tri à bulles (cont.)

On est invité à regarder la vidéo précédante sur YouTube. Occupé par la prise de la note, je n’ai pas regardé en détail l’image descriptive. J’ai utilisé une boucle WHILE englobant une boucle FOR, ce qui est moins efficient qu’une boucle FOR imbriquée.

Exo 7 : implémentation

int arrayLength = getIntInput("Entrez la taille du tableau : ");
double[] array = new double[arrayLength];
double target = 0;
for (int i = 0; i < array.length; i++) {
    array[i] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
}

// write your logic here
double temp = 0;
for (int i = 0; i < array.length - 1; i++) {
    for (int j = 1; j < array.length - i; j++) {
        if (array[j - 1] > array[j]) {
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
        }
    }
}

// display each array element in an entier line
for (int i = 0; i < array.length; i++) {
    System.out.println("tableau[" + i + "] = " + array[i]);
}

Matrices = tableau des tableaux

FUNCTION init(matrix: array[numRow] of type "array[numCol] of numerical type", e: var)
  FOR i FROM 0 TO numRow-1 INCREMENT BY 1
    FOR j FROM 0 TO numCol-1 INCREMENT BY 1
      matrix[i][j] ← e
    ENDFOR
  ENDFOR
END

Exo 10 : somme matricielle

public static double[][] matrixSum(double[][] m1, double[][] m2) {
    // check if dimensions are correct
    if (m1 == null || m2 == null || m1.length != m2.length) {
        displayError("Matrix dimensions mismatch");
    }
    for (int i = 0; i < m1.length; i++) {
        if (m1[i].length != m2[i].length) {
            displayError("Matrix dimensions mismatch");
        }
    }

    // elementwise sum
    double[][] sum = new double[m1.length][m1[0].length];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m1[0].length; j++) {
            sum[i][j] = m1[i][j] + m2[i][j];
        }
    }
    return sum;
}
public static void main(String[] args) {
    // get console input for matrices, adjust their type if needed
    int numRow = getIntInput("Entrez le nombre de lignes : ");
    int numCol = getIntInput("Entrez le nombre de colonnes : ");
    double[][] m1 = new double[numRow][numCol];
    double[][] m2 = new double[numRow][numCol];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m1[0].length; j++) {
            m1[i][j] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
        }
    }
    for (int i = 0; i < m2.length; i++) {
        for (int j = 0; j < m2[0].length; j++) {
            m2[i][j] = getDoubleInput("Entrez l'élément du tableau à l'indice " + i + ": ");
        }
    }

    // write your logic here
    double[][] sum = matrixSum(m1, m2);

    // display each array element in an entier line
    for (int i = 0; i < sum.length; i++) {
        for (int j = 0; j < sum[0].length; j++) {
            System.out.println("tableau[" + i + "][" + j "] = " + sum[i]);
        }
    }
}

Exo Quicksort

Je n’arrive pas à une logique aussi simple que celle du prof. J’ai choisi le 1er élément comme le pivot avec deux pointeurs. Il s’avère que c’est un choix plus compliqué.

  1. petit pivot (peu importe l’ordre de 10 et 100): rIdx ← rIdx − 2

    1 10 … ? ? 100 après 1 ? … ? 10 100
    ↖ ↗ ↖ ↗

  2. moyen pivot (peu importe l’ordre de 1 et 100): lIdx ← lIdx + 1, rIdx ← rIdx − 1

    10 1 ? … ? 100 après 10 1 ? … ? 100
    ↖ ↗ ↖ ↗

  3. grand pivot (peu importe l’ordre de 1 et 10): lIdx ← lIdx + 2

    100 1 ? ? … 10 après 100 1 10 ? … ?
    ↖ ↗ ↖ ↗

Exo Quicksort (cont.)

Dans le cas 1 avec trois éléments, il est possible que apès l’opération, rIdx < lIdx, ce que l’on souhaite pas. En gros, c’est plus simple avec un seul pIdx qui indique l’indice du « trou » entre les deux sous-tableaux.

Liste chaînée

Structure

monNoeud1 : Liste de type T
attribut : T
prochainNoeud : Liste de type T → monNoeud2 : Liste de type T
attribut : T
prochainNoeud : Liste de type T

A la fin de la liste, l’attribut « prochainNoeud » prend la valeur NULL.