Algorithmique

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: olive1978

Bonjour a tous,

Voila ... J'ai un tableau 2D dont je connais le nombre de lignes et dont chaque ligne a un nombre de colonnes connu. Le nombre de lignes doit pouvoi etre variable entre 2 executions du code. Je voudrais enumerer toutes les possibilites. Un exemple sera plus parlant ...

2 6
5
4 8
1

(on a : t(0)(0) = 2, t(2)(1) = 8, ...)

Je voudrais obtenir en sortie les suites :
2 5 4 1
2 5 8 1
6 5 4 1
6 5 8 1

D'avance merci


Posted by: virtualmeet

Bonjour,
J'avoue que j'ai essayé pendant une demi heure mais je n'y arrive pas non plus: ma tête commence a me faire mal. je pense qu'il faut utiliser une autre structure que les tableaux, par exemple les listes ou encore les arbres. Ça devrait être plus facile a traiter qu'avec les tableaux surtout que le nombre de colonne est variables, et cela tu ne peux pas le faire avec les tableaux sauf en remplissant tes cases avec des valeures "Nulles". Tout au moins, il te faudra créer un autre tableau pour stoquer le nombre de colonnes de chaque ligne...mais même avec ça je n'y arrive pas. J'essayerais ce soir et je te dirais ce qu'il en ait (si je trouve une solution bien sure ;-) ) .
Bonne continuation.


Posted by: Fract83

Hello,

Et ou est le probleme exactement ici ?

Bonne journee.


Posted by: Chimerade

Il faut faire une boucle de boucles... Je m'explique (rapidement, je n'ai guère le temps tout de suite)

Si le nombre de lignes avait été fixe (ce qui n'est pas le cas, je sais !) on aurait pu faire :

Code:
de i1=1 à nbcol(1) faire :
{
   de i2=1 à nbcol(2) faire :
   {
       de i3=1 à nbcol(3) faire :
       {
             etc...
       }

   }
}


Bon ! D'une part c'est très lourd comme codage, d'autre part ça ne marche, comme je l'ai dit ci-dessus que si le nombre de lignes est connu et constant.

Mais cela équivaut à :

Code:
i1=1
tant que i1<=nbcol(1) faire
{
   i2=1
   tant que i2<=nbcol(2) faire
   {
      i2=i2+1
   }
   i1=i1+1
}


Et là tu t'aperçois que tu peux faire une boucle "sur les débuts de boucles :

Code:
i1=1
tant que i1<=nbcol(1) faire
{
   i2=1
   tant que i2<=nbcol(2) faire
   {


et une boucle sur les fins de boucles :

Code:

      i2=i2+1
   }
   i1=i1+1
}


Je sais, ce n'est pas très clair...je reviendrai un peu plus tard pour expliciter davantage, mais essaie d'y réfléchir ; ça marche très bien, je l'ai fait de nombreuses fois...Désolé, je n'ai pas le temps pour le moment.


Posted by: Chimerade

Je vais essayer d'être plus clair.

Je reprends donc. Si l'on connaissait le nombre de lignes (nblig) et le nombre de colonnes de chaque ligne (stocké en nbcol[lig]) on pourrait écrire :

Code:

Pour ind[0]=0 à (nbcol[0]-1) faire
{
   Pour ind[1]=0 à (nbcol[1]-1) faire
   {
      Pour ind[2]=0 à (nbcol[2]-1) faire
      {
         Pour ind[3]=0 à (nbcol[3]-1) faire
         {
            etc...
            t[0][ind[0]],t[1][ind[1]],t[2][ind[2]],t[3][ind[3]],... 
            est la suite des valeurs qui nous intéressent
         }
      }
   }
}


Maintenant, entrons un peu dans le détail, le code ci-dessus est équivalent (en utilisant provisoirement un "goto" suranné) à :

Code:

ind[0]=0
Label 0 :
   ind[1]=0
   Label 1 :
   ind[1]=0
      Label 2 :
      ind[2]=0
         Label 3 :
         ind[3]=0
         etc...
         t[0][ind[0]],t[1][ind[1]],t[2][ind[2]],t[3][ind[3]],... 
         est la suite des valeurs qui nous intéressent
         ind[3]=ind[3]+1
         si ind[3]<nbcol[3] goto Label3
      ind[2]=ind[2]+1
      si ind[2]<nbcol[2] goto Label2
   ind[1]=ind[1]+1
   si ind[0]<nbcol[0] goto Label1
ind[0]=ind[0]+1
si ind[0]<nbcol[0] goto Label0


On voit que l’on peut traiter séparément la gestion des hauts de boucles et celle des bas de boucles. Le « haut » peut ressembler à :

Pour i=lig jusqu’à nblig+1 faire ind[i]=0 ;
… à condition de bien savoir à partir de quel indice lig on commence

Quant au « bas » il peut se traiter par une boucle dans le genre de :

lig=nblig-1
faire « ind[lig]=ind[lig]+1 » ; si on dépasse nbcol[lig] alors réduire lig et recommencer, sinon incrémenter lig et remettre à zéro tous les indices à partir de lig : cela est fait en tête de boucle.

Tout cela s’écrit en langage C comme suit :
Code:

   int cas=0;
   int lig=0;
   do
   {
      // Boucle sur gestion de "début de boucles"
      // Mise à zéro des indices à partir de lig
      for (int i=lig;i<nblig;i++)
         ind[i]=0;
      // Traitement de la suite des valeurs : tab[0][ind[0]],tab[0][ind[0]],...,tab[nblig-1][ind[nblig-1]],
      printf("CASE %3d : ",cas);
      for (int lig=0;lig<nblig;lig++)
         printf("%d",tab[lig][ind[lig]]);
      printf("\n");
      cas++;
      // Fin du traitement

      // Boucle sur gestion de "fin de boucles"
      // incrémentation des indices en commencant par le dernier
      // et en s'arrêtant dès qu'on ne dépasse pas la limite
      lig=nblig;
      do
      {
         lig--;
         if (lig>=0) ind[lig]++;
      }
         while ((lig>=0) && (ind[lig]>=nbcol[lig]));
      // lig est la dernière ligne dont on a incrémenter
      // l'indice ind. On ajoute 1 à lig pour mettre à zéro
      // les indices à partir de cette position en début de boucle
      lig++;
   }
      while (lig>0);


Ce code est extrèmement souple : il ne préjuge pas du nombre de lignes NBLIG qui est une variable pouvant être définie à l'exécution, ni du nombre de colonnes de chaque ligne, définissable lui aussi à l'éxécution par la définition du tableau NBCOL[i], i=0 à NBLIG-1.

Et voilà !


Posted by: virtualmeet

Merci Chimerade pour cette excellente réponse . Je ne sais pas par contre si olive1978 a pu en profiter...










-