Forum Clubic

[Pascal] Problème de stack overflow

Bonsoir braves gens…

J’ai un problème avec un programme…
Je vais pas détailler tout le fonctionnement du programme et son but, j’ai l’impression que ça a peu d’importance.
En fait, à la compilation, j’ai un message d’erreur “Stack overflow error” et le prompt se met sur le begin de la procédure suivante :

Procedure Lister_adversaires(matchs:tableau2;num_match,winner:integer;var adv:tableau;var num_adv:integer);
Var
   i:integer;
Begin
     num_adv:=1;
     for i:=1 to num_match do
         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
                     adv[num_adv]:=matchs[i,1];
                  num_adv:=num_adv+1;
             end;
     num_adv:=num_adv-1;
End;

Petite précision :


Const
     nmax=100;
Type
    tableau=array[1..nmax] of integer;
    tableau2=array[1..nmax,1..nmax] of integer;

Je pense que l’erreur doit être dans la procédure… mais où ?
Merci :stuck_out_tongue:

Ca peut être de la récursivité infinie (stack overflow = dépassement de la pile)

Qu’est ce que tu as été faire à ce pauvre compilateur?

Ben c’est bien ce que je pensais… mais je vois pas où !

Regarde à l’appel de la procédure. Aussi, je sais pas comment sont passés les tableaux lors de l’appel de procédure? (pointeur? copie?)

Non, pas de pointeurs…

Essaye de passer ton tableau par pointeur alors?

(en C, les tableaux sont des pointeurs, donc les passés en paramètres ça passe)

(mais pas int x[10], juste int x[])

Etant donné qu’on a pas vu les pointeurs encore, je peux pas m’en servir…
Par contre, je vais filer mon programme en entier…
Le but du programme étant de sortir l’indice du 2e plus grand élément d’un tableau, en utilisant la méthode dite du tournoi (en gros : il compare les éléments 2 par 2, et détermine ainsi le plus grand de tous, puis il regarde le plus grand des “adversaires” du plus grand de tous, qui se trouve être le 2e plus grand élément)


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];
     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;
     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.

De même je crois que les pointeurs en Pascal se font par @ et &. Je n’ai jamais fait de Pascal, donc je ne t’aiderai pas plus.

J’ai fini…
En fait, il faut modifier la valeur de la constante nmax…
Et il fallait aussi optimiser la taille du tableau de matchs…

Voila le code, commenté en prime, pour ceux que ça intéresse :

Program DH1Exercice2Q2;
Uses CRT;
Const
     nmax=177;
Type
    tableau=array[1..nmax] of integer;
    tableau2=array[1..nmax,1..nmax] of integer;
    tableau_matchs=array[1..nmax,1..2] of integer;
Var
   A,adv:tableau;
   joueurs:tableau2;
   matchs:tableau_matchs;
   winner,ind_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;


{***   Procédure DPGE, qui calcule le plus grand et le 2e plus grand élément d'un tableau t   ***}
Procedure DPGE(t:tableau;taille:integer;var winner,ind_dpge:integer);
Var
   n,i,tour,k,num_match,num_adv:integer;
Begin
     n:=taille;
     {***   On remplit le tableau des joueurs au premier tour avec leur indice dans le tableau t   ***}
     for i:=1 to n do
         joueurs[1,i]:=i;
     {***   On passe au tour 2   ***}
     tour:=2;
     {***   On initialise le numéro du match à 1   ***}
     num_match:=1;
     while (n <> 1) do
     {***   Tant qu'il ne reste pas qu'un seul joueur   ***}
           begin
                k:=n div 2;
                for i:=1 to k do
                {***   On joue les matchs du tour suivant   ***}
                    begin
                         if (t[joueurs[tour-1,2*i-1]] > t[joueurs[tour-1,2*i]]) then
                            joueurs[tour,i]:=joueurs[tour-1,2*i-1]
                         else
                             joueurs[tour,i]:=joueurs[tour-1,2*i];
                         {***   Dans joueurs[tour,i], on stocke l'indice du vainqueur du match   ***}
                         matchs[num_match,1]:=joueurs[tour-1,2*i-1];
                         matchs[num_match,2]:=joueurs[tour-1,2*i];
                         num_match:=num_match+1;
                         {***   On stocke les 2 joueurs du matchs dans le tableau matchs   ***}
                    end;
                if (n mod 2 = 0) then
                   n:=k
                else
                    begin
                         joueurs[tour,k+1]:=joueurs[tour-1,n];
                         n:=k+1;
                    end;
                {***   Ce if sert à déterminer le nombre de joueurs du tour suivant   ***}
                tour:=tour+1;
           end;
     tour:=tour-1;
     num_match:=num_match-1;
     winner:=joueurs[tour,1];
     {***   Le plus grand élément de tout le tableau est dans winner   ***}
     num_adv:=1;
     for i:=1 to num_match do
     {***   On parcourt le tableau matchs pour trouver les adversaires de winner   ***}
         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;
     {***   Les adversaires de winner sont dans adv   ***}
     num_adv:=num_adv-1;
     ind_dpge:=adv[1];
     for i:=2 to num_adv do
         if (t[adv[i]] > t[ind_dpge]) then
            ind_dpge:=adv[i];
     {***   On cherche le plus grand élément de adv, qui est le 2e plus grand élément cherché   ***}
End;



Begin
     clrscr;
     initialisation(A,8);
     DPGE(A,8,winner,ind_dpge);
     Writeln('Plus grand élément : ',A[winner],' (indice : ',winner,')');
     Writeln('Deuxième plus grand élément : ',A[ind_dpge],' (indice : ',ind_dpge,')');
     readkey;
End.

J’ai du mal à saisir pourquoi une taille supérieure ne provoque plus d’erreur, mais comme je connais pas le pascal :slight_smile:

Et bien en fait, c’est parce que j’ai pas mis toutes les étapes de mon programme sur le forum… à une époque, j’avais nmax=1000…
Mais l’optimisation la plus importante était au niveau du tableau des matchs… qui passe de [1…nmax,1…nmax] à [1…nmax,1…2] :smiley:
Et là, tout de suite, ça fait BEAUCOUP plus léger :slight_smile:

Ok :slight_smile:

boulet :slight_smile:

T’as pas changé toi… t’as même empiré :stuck_out_tongue:
Et dire que t’es de nouveau modo… traitre, tyran, vendu, pourri, fumier :slight_smile:

=)

Ben hé :slight_smile: quand on alloue des tableaux de 1000x1000 sur la pile :slight_smile:

100010004 = 4Mo sur la pile… (qui doit pas en faire plus d’un)