École polytechnique
Épreuve facultative d'algorithmique

\(Pour\ suivre\ la\ convention\ imposée\ par\ l' énoncé\), on définit une fonction aqui adresse les éléments d'un tableau:

n = 10;
tableau = Table[Random[Integer, 20], {n}]
a[k_] := tableau[[k + 1]]

Q1: on utilise un parcours linéaire du tableau apour déterminer le max et l'inf, la fonction est donc en temps linéaire (≃2  n)

amplitude[a_] := Module[{max = -Infinity, min = Infinity},
    Do[If[a[i] > max, max = a[i]]; If[a[i] < min, min = a[i]], {i, 0, n - 1}]; 
     max - min]
{tableau, amplitude[a]}

Q2: si le max précède le min, on aura du mal à faire un gain égal à amplitude ! Ex a = {100  $, 10  $}.L'amplitude est la valeur absolue du gain ou de la perte maximale.

Q3: on utilise un parcours sur j, puis sur i ≤ j, la fonction est donc en temps quadratique (≃(n^2)/2).

gain[a_] := Module[{bid = 0},
Do[If[a[j] - a[i] > bid, bid = a[j] - a[i]],
      {j, 1, n - 1}, {i, 0, j}]; bid]
gain[a]

Remarque: on peut se contenter de 0≤i≤j-1.

Q4: la condition j-i minimal entraîne une difficulté. On peut noter qu'il n'y a défaut d'unicité que si le max ou l'inf est atteint plusieurs fois. Une solution est d'inverser les boucles imbriquées, de faire décrémenter j et de remplacer < par ≤ !

gain[a_] := Module[{bid = 0, iMax, jMax},
    Do[If[a[j] - a[i] >= bid, bid = a[j] - a[i];
	iMax = i; jMax = j],
      {i, 0, n - 1}, {j, n - 1, i + 1, -1}];
	{bid, {iMax, jMax}}]
gain[a]

Q5: pour améliorer la complexité de l'algorithme, on va garder trace des indices des valeurs optimales.

gain1[a_] := Module[
		{gc = 0, indMax = 0, indMin = 0, nveauMin = 0},
    Do[If[a[i] > a[indMax], gc = a[indMax = i] - a[indMin]];
       If[a[i] - a[nveauMin] > gc,
			gc = a[indMax = i] - a[indMin = nveauMin]];
       If[a[i] < a[indMin], nveauMin = i]; ,
			{i, 1, n - 1}]; gc]
			
gain1[a]

Q7 (heureusement qu'on ne demande plus un temps linéaire !)
La solution la plus lisible utilise une coupure des fonctions précédentes, en les appliquant aux deux sous-tableaux obtenus en coupant a au point j et en optimisant la somme des deux par itération sur j.
Pour cela, on réécrit la procédure gain pour y faire figurer les dates extrêmes des transactions possibles.

gainCourtTerme[a_, début_, fin_] :=
   Module[{gc = début, indMax = début, indMin = début, nveauMin = début},
    Do[If[a[i] > a[indMax], gc = a[indMax = i] - a[indMin]];
       If[a[i] - a[nveauMin] > gc,
			gc = a[indMax = i] - a[indMin = nveauMin]];
       If[a[i] < a[indMin], nveauMin = i]; ,
	{i, début + 1, fin - 1}];
	gc]

gain2[a_] := Module[{essai, top = 0},
    Do[essai = gainCourtTerme[a, 0, k]
			+ gainCourtTerme[a, k, n - 1];
       If[essai > top, top = essai], {k, 1, n - 1}];
			top]
			
gain2[a]

Q8: Idem en moins lisible

gct[a_, début_, fin_] := Module[{gc = début, indMax = début, indMin = début,
     nveauMin = début},
    Do[If[a[i] > a[indMax], gc = a[indMax = i] - a[indMin]];
       If[a[i] - a[nveauMin] > gc,
		gc = a[indMax = i] - a[indMin = nveauMin]];
       If[a[i] < a[indMin], nveauMin = i]; ,
		{i, début + 1, fin - 1}];
     {gc, indMin, indMax}]
		
gain2[a_] := Module[{essai, coord, bid1, bid2, top = 0},
    Do[essai = 	First[bid1 = gct[a, 0, k]] +
				First[bid2 = gct[a, k, n - 1]];
       If[essai > top, top = essai;
		coord = {bid1[[2]], bid1[[3]], bid2[[2]], bid2[[3]]}],
				{k, 1, n - 1}];
				{top, coord}]
				
gain2[a]

Voici une version plus idiosyncrasique où l'on adresse une liste par le numéro de ses éléments… ce qui permet de passer la liste en argument.

gct[a_List, début_, fin_] :=
Module[
	{gc = début, indMax = début, indMin = début, nveauMin = début},
    Do[If[a[[i]] > a[[indMax]],
		gc = a[[indMax = i]] - a[[indMin]]];
       If[a[[i]] - a[[nveauMin]] > gc,
		gc = a[[indMax = i]] - a[[indMin = nveauMin]]];
	  If[a[[i]] < a[[indMin]], nveauMin = i],
    {i, début + 1, fin}];
	{gc, indMin, indMax}]
	
gain2[a_] := Module[
	{essai, coord, bid1, bid2, top = 0, n = Length[a]},
    Do[essai = First[bid1 = gct[a, 1, k]] +
			  First[bid2 = gct[a, k, n]];
       If[essai > top, top = essai;
			 coord = {bid1[[2]], bid1[[3]],bid2[[2]],bid2[[3]]}
		],
	{k, 1, n - 1}];
	{top, coord}]
	
gct[{5, 12, 3, 6, 9, 14, 8, 20, 6, 17, 10, 11}, 1, 12]

gain2({5, 12, 3, 6, 9, 14,
         8, 20, 6, 17, 10, 11})