Discussion :

[Dunk]

Bonjour

Voila : j'ai un exo à faire, je dois trouver le 2e plus grand élément d'un tableau d'entiers en utilisant ce qu'on appelle la méthode du tournoi. En gros, je prends les éléments, je leur fais jouer un "tournoi", je trouve le vainqueur (le plus gd de tous) et je regarde le plus grand élément des adversaires du vainqueur, qui se trouve être le 2e plus grand élément du tableau.
Voila pour le principe...
Maintenant le code...
J'ai codé un "petit" programme... et il me parait juste... mais j'ai une erreur à la compilation : "Stack Overflow error".
Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
Program Tournoi;
Uses CRT;
Const
     nmax=100;
Type
    tableau=array[1..nmax] of integer;
    tableau2=array[1..nmax,1..nmax] of integer;
Var
   A:tableau;
   joueurs:tableau2;
   i,j,k,dpge:integer;
 
 
 
{***   Procédure qui affiche le contenu d'un tableau   ***}
Procedure ecriture(t:tableau;taille:integer);
var
   i:integer;
begin
     for i:=1 to taille do
         write(t[i],' ');
     writeln;
end;
 
 
 
{***   Procédure qui génère un tableau aléatoirement   ***}
Procedure initialisation(var t:tableau;taille:integer);
var
   i:integer;
begin
     randomize;
     for i:=1 to taille do
         t[i]:=random(100);
     ecriture(t,taille);
end;
 
 
Procedure Deux_PGE(t:tableau;taille:integer;var dpge:integer;var joueurs:tableau2);
Var
   n,i,j,k,num_match,num_adv,ind_dpge,winner:integer;
   adv:tableau;
   matchs:tableau2;
Begin
     n:=taille;
     for i:=1 to n do
         joueurs[1,i]:=i;
     j:=2;
     num_match:=1;
     while (n <> 1) do
           begin
               	k:=n div 2;
                for i:=1 to k do
                    begin
                         if (t[joueurs[j-1,2*i-1]] > t[joueurs[j-1,2*i]]) then
                            joueurs[j,i]:=joueurs[j-1,2*i-1]
                         else
                            joueurs[j,i]:=joueurs[j-1,2*i];
                            matchs[num_match,1]:=joueurs[j-1,2*i-1];
                            matchs[num_match,2]:=joueurs[j-1,2*i];
                            num_match:=num_match+1;
                     end;
                if (n mod 2 = 0) then
                   n:=k
                else
                    begin
                         joueurs[j,k+1]:=joueurs[j-1,n];
                         n:=k;
                    end;
                j:=j+1;
           end;
     num_match:=num_match-1;
     winner:=joueurs[j,1];
{*** MARQUE 1 ***}
     num_adv:=1;
     for i:=1 to num_match do
         begin
              if (matchs[i,1] = winner) then
                 begin
                      adv[num_adv]:=matchs[i,2];
                      num_adv:=num_adv+1;
                 end
              else
                  begin
                       if (matchs[i,2] = winner) then
                          begin
                               adv[num_adv]:=matchs[i,1];
                               num_adv:=num_adv+1;
                          end;
                  end;
         end;
     num_adv:=num_adv-1;
{*** MARQUE 2 ***}
     ind_dpge:=adv[1];
     for i:=2 to num_adv do
         if (t[adv[i]] > t[ind_dpge]) then
            ind_dpge:=adv[i];
     dpge:=ind_dpge;
End;
 
 
Begin
     clrscr;
     initialisation(A,8);
     j:=2;
     Deux_PGE(A,8,dpge,joueurs);
     for i:=1 to j-1 do
         begin
              for k:=1 to 8 do
                  write(joueurs[i,k],' ');
              writeln;
         end;
     Writeln;
     Writeln('DPGE : ',dpge);
     readkey;
End.

Voila...
A savoir qu'avant ce programme, j'avais fait un programme en découpant ma procédure Deux_PGE en 3 procédures... et lors de l'erreur de compilation, le prompt se mettait sur le begin de la procedure que j'ai entouré de {*** MARQUE 1 ***} et {*** MARQUE 2 ***}.

Merci d'avance !

[M.Dlb]

Il y a peut-être une explosion de pile lors de l'appel à Deux_PGE car tu y passes des paramètres, dont le tableau2 joueurs, qui ont une taille conséquente. Essaye d'utiliser des pointeurs sur les tableaux, pour éviter le Stack Overflow. Sinon l'initialisation se passe bien ?

[Dunk]

L'initialisation se passe sans problème oui.
Et quand j'ai le programme découpé en 3 procédures, la procédure qui est avant les marques que j'ai mis en commentaire se déroule très bien.
Le problème surgit quand je veux lister les adversaires du vainqueur dans le tableau adv...
Par contre, un problème : je ne peux pas utiliser les pointeurs étant donné qu'on ne les a pas vu en cours...
Il faudrait donc alléger qqchose qqpart... mais quoi ?

[M.Dlb]

Apparemment tes variables sont trop larges. Deux solutions :
- soit réduire le nombre nmax pour diminuer la taille des tableaux,
- soit déplacer tes variables locales adv et joueurs dans les variables globales du programme.

[Dunk]

Ok ok merci !
Je suis obligé de réduire nmax à 87 pour que ça marche...
Dans l'énoncé, le nmax est donné à 1000...
Au pire, je me contenterai de ce nmax à 87, mais je pense qu'il doit y avoir un moyen de coder un algorithme analogue qui marche pour 1000.
Je pense aussi qu'il faut utiliser une procédure récursive juste avant de lister les adversaires.

Qu'en pensez-vous ?

[Dunk]

Aaaah ! En créant un nouveau type pour mon tableau de matchs, je m'en sors !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Type
      tableau_matchs=array[1..nmax,1..2] of integer;

Et pouf
Par contre, je peux pas monter jusqu'à nmax=200, parce que mon tableau2 est "too large"... faut que je trouve aussi une optimisation pour ça...

[Alcatîz]

Bonjour !

je peux pas monter jusqu'à nmax=200, parce que mon tableau2 est "too large"... faut que je trouve aussi une optimisation pour ça...

Dans l'énoncé, le nmax est donné à 1000...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tableau2=array[1..nmax,1..nmax] of integer;

Avec nmax = 1000, le type tableau2 fait 2.000.000 bytes. Or, la taille d'une variable ne peut dépasser 65520 bytes pour Turbo Pascal. Soit tu es obligé d'utiliser Turbo Pascal, auquel cas nmax = 1000 est absolument impossible, soit tu peux utiliser un autre compilateur comme Free Pascal ou Virtual Pascal, dont la taille des variables peut faire plusieurs Gb.

[Dunk]

Merci bien !
J'ai tout ce que je voulais, merci de votre aide !

[Eric Sigoillot]

Bonjour,

C'est bien compliquée cette recherche de 2ème maximum...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const
  CMax = 100;
 
type
  TArray = array[1..CMax] of Integer;
 
function FindMax(A: TArray; First: Integer; var PosMax: Integer): Integer;
var
  i: Integer;
  Max: Integer;
begin
  PosMax := First;
  Max := A[First];
  for i := First + 1 to CMax do
  begin
    if A[i] > Max then
    begin
      Max := A[i];
      PosMax := i;
    end;
  end;
  FindMax := Max;
end;
 
function Find2ndMax(A: TArray; var PosMax2: Integer): Integer;
var
  Dummy: Integer;
begin
  { On cherche le premier maximum : sa position est
    stockée dans PosMax2 }
  FindMax(A, 1, PosMax2);
  { Une fois récupérée, on intervertit le maximum avec
    le premier élément. Or, le maximum ne nous intéresse pas,
    donc on se contente de remplacer le maximum avec le 
    premier élément du tableau. Ainsi, le 2ème maximum se
    trouve dans le tableau à partir de la 2ème position }
  A[PosMax2] := A[1];
  Find2ndMax := FindMax(A, 2, PosMax2);
end;

Tout simplement

@++


PS: Code non testé tappé sur le tas, mais ça devrait être à peu près ça

[Dunk]

Bonsoir mon brave :p
Je suis bien conscient que mon algo est bien compliqué...
Mais mon sujet est composé de 2 questions pour trouver le 2e maximum :
1) méthode naïve : la vôtre :p (que j'ai déjà codé pour l'exo)
2) méthode du tournoi : celle que j'essaye de mettre en place...

La méthode naïve effectue au pire 2n-3 comparaisons... tandis que celle du tournoi en effectue au pire n-1+E(ln(n)/ln(2))...

Merci qd même