Discussion :

[Dadeap]

Bonjour,

je travaille actuellement sur un projet d'ordonnancement à machine parallèle. Il nous est demandé de transposer un algorithme en langage C. Le problème est que l'algorithme utilise un tableau de dimension m (m étant le nombre de machines utilisé pour l'ordonnancement). Par exemple, s'il y a deux machines, le tableau sera a deux dimensions, dimensions 3 si trois machines, etc ...

J'ai pour l'instant pondu ce code (ne pas faire attention au malloc j'ai mis une valeur au pif pour pas m’embêter) :

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
 
int impossibru (void ** tab,int C,int m)
{
    int i=0;
    if (m==1)
    {
        *tab=0;
        return 0;
    }
    else
    {
        for (i=0;i<C;i++)
        {
            tab[i]=malloc(sizeof(int)*5);
            if (tab[i] == NULL)
            {
                printf("Erreur d'allocation mémoire du tableau");
                exit(-1);
            }
            *tab[i]=impossibru(*tab[i],C,m-1);
        }
    }
}

Comme vous pouvez le voir, j'ai tenté avec la méthode de la récursivité. Tout d'abord, on déclare avec des pointeurs void comme on ne sait pas si se sera un pointeur d'entier ou un pointeur de pointeur.

Si m=1, cas d'arrêt, et on met la valeur dans le tableau. On return 0 pour dire que tout s'est bien passé. Sinon, s'il faut rajouter une nouvelle dimension, on alloue la place mémoire pour le nouveau tableau correspondant à la nouvelle dimension, et on refait appel à la fonction.

J'ai cependant des problèmes dans la gestion du pointeur en paramètre, en particulier avec la dernière ligne
1

Code :

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

*tab[i]=impossibru(*tab[i],C,m-1);

Cela me met le code d'erreur suivant : invalid use of void expression

Après avoir ressassé plusieurs fois sur mon bout de papier je ne vois pas trop d'où viens ce problème

[kwariz]

Bonjour,

tu parles bien d'un tableau avec plusieurs dimensions : M[10][10][10][10] est un tableau à 4 dimensions chacune de taille 10 ?
ou bien parles-tu d'un tableau à une dimension mais de taille dynamique M[n] où n est déterminé au run-time ?

[Neckara]

Bonjour,

Si tu parle de tableau du genre tab[10][10][10][10], saches qu'en mémoire, il est en fait représenté sous forme de tableau à une dimension.

Tu peux avoir faire "comme si" tu avais un tableau à X dimensions tout en déclarant un tableau à une dimension.

Il faudra juste convertir l'indice du tableau à une dimension en l'indice d'un tableau à X dimension.

Dans le cas du tableau, tab, si on a : tab[i][j][k] = tab[l], l = i*10*10+j*10+k et i = l/(10*10) ; j = (l/10)%10 et k = l%(10*10).

Grosso modo (dommage qu'on ne puisse pas rentrer de formules mathématiques ) :
Soit i l'ensemble des indice d'un tableau à n+1 dimensions et Ind l'indice d'un tableau uni-dimensionnel,

Ind = i0*10^n + i1*10^(n-1)*....+ in
et ix = (Ind/ 10^(n-x) )%10


N.B. Je n'ai pas vérifié les formules

[Dadeap]

Je parlais bien d'un tableau T[10][10][10][10] pour reprendre votre exemple.

Vous pensez donc que la récursivité est une mauvaise piste ? Je vais essayer de voir avec ta méthode Neckara, car le parcours du tableau n'est pas très aisé avec celle-ci ^^

NB : Le problème sur la dernière ligne venais d'un usage incorrect de void. Avec le code suivant, la compilation fonctionne (après à voir si c'est bien le résultat escompté ^^) :

Code :

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

*(int *)tab[i]=(int)impossibru(tab[i],C,m-1);

[kwariz]

Simplifie-toi la vie et suit la méthode Neckara ... mais attention tu pourras rapidement te retrouver sans mémoire à allouer suivant la taille de tes cellules et les tailles de tes dimensions ... un simple int (4 octets en général) avec 4 dimensions de taille 10 fait déjà dans les 40ko ...

Par curiosité, que va contenir ce «méga»-tableau ?

[Dadeap]

Après avoir cogité un peu, cette solution semble en effet plus simple : il suffit en effet de déclarer un tableau de taille C^m pour pouvoir stocker toutes les valeurs désirées.

Quand au pourquoi de ce tableau, en fait le but final est qu'il contienne des booleen pour permettre l'utilisation d'un algorithme de programmation dynamique. En fonction de la valeur des booléens, cela nous permet de savoir si l'ordonnancement devient meilleure dans un sens ou non.