Problèmes d'optimisation

Avant de commencer

Vous avez les températures relevées chaque jour d'une semaine. Vous voulez savoir : quel jour il a fait le plus chaud, et quelle température. C'est un problème d'optimisation : trouver l'extremum et son indice.

1. Le schéma général

optimum ← T[1]
indice_optimum ← 1
Pour i de 2 à n Faire
  Si T[i] est meilleur que optimum Alors
    optimum ← T[i]
    indice_optimum ← i
  FinSi
FinPour

« Meilleur » dépend du problème : > pour un maximum, < pour un minimum.

2. Maximum d'un tableau

FUNCTION IndiceMax(T : Tab; n : integer) : integer;
VAR i, imax : integer;
BEGIN
  imax := 1;
  FOR i := 2 TO n DO
    IF T[i] > T[imax] THEN
      imax := i;
  IndiceMax := imax;
END;

On retourne l'indice plutôt que la valeur : à l'appelant de faire T[imax] s'il veut la valeur. Plus utile en pratique.

3. Optimisation avec contrainte

Exemple : trouver le plus grand pair d'un tableau.

FUNCTION PlusGrandPair(T : Tab; n : integer) : integer;
VAR i, max : integer;
  trouve : boolean;
BEGIN
  trouve := false;
  max := 0;
  FOR i := 1 TO n DO
    IF T[i] MOD 2 = 0 THEN
    BEGIN
      IF (NOT trouve) OR (T[i] > max) THEN
      BEGIN
        max := T[i];
        trouve := true;
      END;
    END;
  IF NOT trouve THEN
    PlusGrandPair := -1   { aucun pair trouvé }
  ELSE
    PlusGrandPair := max;
END;

Le drapeau trouve permet de gérer le cas où il n'y a aucun pair.

4. Minimum local et maximum local

Un min local est un élément plus petit que ses deux voisins.

FUNCTION EstMinLocal(T : Tab; n, i : integer) : boolean;
BEGIN
  IF (i <= 1) OR (i >= n) THEN
    EstMinLocal := false
  ELSE
    EstMinLocal := (T[i] < T[i-1]) AND (T[i] < T[i+1]);
END;

5. Exercices

PROCEDURE Minimum(T : Tab; n : integer; VAR val, idx : integer);
VAR i : integer;
BEGIN
  val := T[1];
  idx := 1;
  FOR i := 2 TO n DO
    IF T[i] < val THEN
    BEGIN
      val := T[i];
      idx := i;
    END;
END;

PROCEDURE MinMax(T : Tab; n : integer; VAR mn, mx : integer);
VAR i : integer;
BEGIN
  mn := T[1]; mx := T[1];
  FOR i := 2 TO n DO
  BEGIN
    IF T[i] < mn THEN mn := T[i];
    IF T[i] > mx THEN mx := T[i];
  END;
END;

BEGIN
  MinMax(T, n, mn, mx);
  Writeln('Étendue = ', mx - mn);
END.

PROCEDURE DeuxPlusGrands(T : Tab; n : integer; VAR p1, p2 : integer);
VAR i : integer;
BEGIN
  IF T[1] >= T[2] THEN
  BEGIN p1 := T[1]; p2 := T[2]; END
  ELSE
  BEGIN p1 := T[2]; p2 := T[1]; END;

  FOR i := 3 TO n DO
    IF T[i] > p1 THEN
    BEGIN
      p2 := p1;
      p1 := T[i];
    END
    ELSE IF (T[i] > p2) AND (T[i] <> p1) THEN
      p2 := T[i];
END;

6. Erreurs fréquentes au bac

• Initialiser max := 0 au lieu de T[1] (échoue sur des valeurs négatives).
• Oublier idx := 1 au début (résultat indéfini).
• Mauvais sens de comparaison (< au lieu de > ou inverse).

7. Quiz