affecter dynamiquement un tableau

Version imprimable

Bonsoir !

Je veux affecter un tableau de tableaux de manière dynamique et je ne sais pas quelle taille aura ce tableau.

Lorsque j'essaie de le faire une erreur apparait :
Code:

1 2 error: variable-sized object may not be initialized int **open_set[0][ligne][colonne] = board[ligne][colonne];
Voici le code en question. Il s'agit d'implémenter l'algorithme A-Star pour un cours d'intelligence artificielle.

**open_set représente les noeuds du graphe des chemins à suivre qui doivent encore être évaluer.
Code:

1 2 3 4 5 6 7 8 9 void A_star(){ int **closed_set=NULL; for(int ligne = 0; ligne < d; ligne++){ for(int colonne = 0; colonne<d;colonne++){ int **open_set[0][ligne][colonne] = board[ligne][colonne]; } }
Pouvez vous m'aider à comprendre comment affecter dynamiquement ce tableau?

Merci d'avance !

07/10/2016, 19h42
Sve@r

Bonjour

Quand tu as un pointeur truc *pt, tu n'as pas le droit de taper dans "*pt" si tu n'as pas écrit auparavant pt=adresse_valide. Et si tu n'as aucune adresse à ta disposition tu dois alors allouer de la mémoire via malloc.

Toi tu as un double pointeur. Si on doit faire une analogie, alors il faut voir autant d'étoiles que de dimensions (attention, ce n'est pas une équivalence stricte (sinon tous les puristes vont me hurler dessus -a raison !!!-), c'est juste une façon d'imaginer).
Donc si tu as in int **open_set (il y a d'ailleurs une erreur dans ta fonction car on y lit "closed_set"), ça veut dire que tu pars "à priori" sur un tableau 2D (comme un échiquier).

Mais comme pour un échiquier, tu dois d'abord définir combien tu auras de lignes (qui se comporteront comme d'autant de tableaux 1D). Tu dois alors impérativement allouer open_set en lui disant qu'il devra gérer "L" lignes: open_set=malloc(L * sizeof(int*)).

Maintenant tu as à ta disposition L pointeurs allant de open_set[0] jusqu'à open_set[L-1]. Mais chacun de ces pointeurs doit être alloué pour pouvoir stocker "c" éléments (le "c" représentant les colonnes de ton échiquier). Donc tu dois boucler de 0 à L et écrire à chaque itération open_set[i]=malloc(c * sizeof(int)). Et bien entendu, en vérifiant que chaque malloc se passe bien (donc qu'il n'ait pas renvoyé NULL) et en ayant prévu une échappatoire si c'est le cas ; échappatoire qui s'occupe alors de désallouer tout ce qui a été alloué => exemple: si tu as alloué les open_set[i] de 0 à 8 et que ça plante au open_set[9] tu dois alors libérer les 8 open_set[i] correctement alloués puis libérer le open_set alloué au tout début (celui qui gère les lignes).

Sinon une fois que tout est alloué sans erreur, tu as alors le droit de taper dans open_set[i][j] (lui affecter un entier, ou aller lire l'entier qui s'y trouve).

En tout état de cause, tu ne peux pas aller taper dans "**open_set[x][y][z]" vu que open_set n'a que 2 dimensions (et en plus tu y as rajouté 2 étoiles ce qui "signifierait" que "open_set" a en réalité 5 dimensions !!!

Bref beaucoup d'incohérences dans ce que tu écris. Tu devrais revoir sérieusement le cours sur les pointeurs et les tableaux...

euh je comprends pas ton code

Code:

1
2
3
4
5
6
7
8
 
void A_star(){ 
    int **closed_set=NULL;
    for(int ligne = 0; ligne < d; ligne++){
        for(int colonne = 0; colonne<d;colonne++){
            int **open_set[0][ligne][colonne] = board[ligne][colonne];
        }
    }

Je comprends pas trops ton code mais peut-être que tu voulais faire sa:

Code:

1
2
3
4
5
6
7
 
   int **open_set[1][d][d];
    for(int ligne = 0; ligne < d; ligne++){
        for(int colonne = 0; colonne<d;colonne++){
            open_set[0][ligne][colonne] = board[ligne][colonne];
        }
    }

08/10/2016, 00h47
AntoineCompagnie

1 pièce(s) jointe(s)
D'accord, le point à travailler est bien entendu l'allocation avant l'insertion.

Dans la mesure ou j'essaye de stocker les nœuds de la résolution du jeu du Taquin de taille d*d, je cherche à stocker dans open_set les différents tableaux découverts que l'on doit encore évaluer selon l'algorithme A étoile.

Juste au cas ou, ci ca peut aider voici un exemple de jeu résolu.

Pièce jointe 222185

J'essaie de le résoudre automatiquement grâce à A étoile. Ne sachant pas combien de tableau j'ai à gérer, comment allouer cette mémoire?

Code:

open_set=malloc(???*sizeof(int*))

Tout en bouclant à chaque itération:
Code:

1 2 open_set[i]=malloc(d*d * sizeof(int))
Ne serait il pas plus simple de représenter les tableau du jeu sous forme de liste?

Imaginons que j'ai bien mes pointeurs de tableau désormais. Pourquoi ne pas utiliser

Code:

**open_set[x][y][z]

? x aurait été le numéro du tableau, y et z les coordonnées de chaque numéro.

Je sais que c'est confus, j'ai débarqué en L3 informatique après deux ans de facs d'éco et je me suis battu pour entrer en M1.
08/10/2016, 10h04
Matt_Houston

Ton programme doit fonctionner avec des dimensions de grille arbitraires, mais es-tu autoriser à le recompiler pour modifier ces paramètres ?

Ma question est destinée à déterminer quel degré d'allocation mémoire dynamique est nécessaire.

C'est tentant de représenter une grille rectangulaire par un tableau multidimensionnel lorsque l'on débute mais c'est une fausse bonne idée. Particulièrement lorsque le tableau multidimensionnel doit être alloué dynamiquement (donc de manière non contigüe) et qu'on ne maîtrise pas la gestion mémoire.
08/10/2016, 11h45
picodev

Bonjour,

comme tu utilise A* tu vas devoir utiliser un type de données de genre file de priorité. Je ne peux que te conseiller de créer un module proposant ce type et les primitives le manipulant. L'écriture de ton code sera simplifiée.
Pour l'implémentation de cette file tu peux au choix utiliser les listes chaînées ou les tas avec, pour l'un comme pour l'autre, une implémentation soit à base de «pointeurs à la C» ou à base de tableaux.
Implémente déjà ta file de priorité avant de mettre la main dans le cambouis.
08/10/2016, 15h27
AntoineCompagnie

Citation:

Envoyé par Matt_Houston

Ton programme doit fonctionner avec des dimensions de grille arbitraires, mais es-tu autoriser à le recompiler pour modifier ces paramètres ?

Oui, la taille est donnée dès le départ lors de l'appel du programme par ./fifteen 3 par exemple, qui donnera un tableau de taille 3*3.

Citation:

Envoyé par Matt_Houston

C'est tentant de représenter une grille rectangulaire par un tableau multidimensionnel lorsque l'on débute mais c'est une fausse bonne idée. Particulièrement lorsque le tableau multidimensionnel doit être alloué dynamiquement (donc de manière non contigüe) et qu'on ne maîtrise pas la gestion mémoire.

Rah, oui c'est rageant, ça ressemble à la forme qu'on lui donne dans sa tête. Donc si j'ai bien compris il faut que j'utilise des tas avec des règles de priorité? Je ne sais pas encore ce que c'est que tout ça. Je vais me renseigner! Merci!

Citation:

Envoyé par AntoineCompagnie

D'accord, le point à travailler est bien entendu l'allocation avant l'insertion.

Bien entendu. On ne peut peut évidemment pas insérer avant d'avoir la place pour ça. Ceci dit c'est bien d'en avoir conscience (tu te démarques déjà de 50% de débutants qui croient qu'en C la mémoire est générée automatiquement !!!)

Citation:

Envoyé par AntoineCompagnie

Dans la mesure ou j'essaye de stocker les nœuds de la résolution du jeu du Taquin de taille d*d, je cherche à stocker dans open_set les différents tableaux découverts que l'on doit encore évaluer selon l'algorithme A étoile.Je sais que c'est confus, j'ai débarqué en L3 informatique après deux ans de facs d'éco et je me suis battu pour entrer en M1.

Je comprends mieux ce que tu veux faire.

A mon avis, une bonne façon de faire serait que tu dissocies
l'état du jeu lui-même
les différents jeux possibles

Dans cette optique, tu pourrais créer un outil destiné à stocker l'état du jeu. A mon avis je pense qu'un tableau 2D serait parfait. On pourrait éventuellement envisager la possibilité d'un tableau 1D car on peut par exemple considérer ton jeu final comme la suite "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0" mais si on ne symbolise pas le fait que "12" est au dessus du "0" (symbolisant le vide) on risque d'avoir des difficultés quand on voudra calculer les déplacements possibles. Et même si ces difficultés ne sont pas insurmontables, si on part directement sur du 2D on s'affranchit quand-même de certains soucis de positionnement.

Donc imaginons ton jeu se déclarant comme un int jeu[x][y]. Tu pourrais alors prévoir une structure de liste destinée à stocker les différents jeux possibles. Cette structure pourrait alors être
Code:

1 2 3 4 5 6 7 8 9 10 typedef struct s_noeud{ int jeu[x][y]; struct s_noeud *next; } t_noeud; typedef struct { t_noeud *first; t_noeud *last; size_t nb_noeuds; } t_liste;
Le problème, vois-tu, c'est qu'au delà d'un certain niveau de complexité, le cerveau ne peut plus suivre. C'est pour ça qu'en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2". Donc au lieu de représenter les différents jeux par un gros tableau multidimensionnel (2D pour le jeu et une 3° dimension pour les différents jeux) tu as d'un coté une entité te permettant de manipuler les pions d'un jeu et de l'autre une entité te permettant de manipuler différents jeux distincts.

A partir de là, tu peux mieux appréhender. Par exemple rajouter un jeu en fin de la liste des jeux déjà existants ça pourrait se faire ainsi
Code:

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 t_noeud *ajouter_jeu(int jeu[x][y], t_liste *liste) { t_noeud *nouveau; // On crée le noeud à insérer nouveau=malloc(sizeof(t_noeud)); // Si l'allocation a échoué if (nouveau == NULL) { // Inutile de continuer return NULL; } // On remplit le noeud créé avec le jeu à stocker memcpy(nouveau->jeu, jeu, x*y*sizeof(int)); // L'avantage du tableau c'est qu'il est contigu en mémoire donc le jeu tout entier peut se copier d'un bloc nouveau->next=NULL; // S'il n'y a pas de premier noeud if (liste->first == NULL) { // On positionne le noeud créé en tête de liste liste->first=nouveau; } // S'il y a un dernier noeud déjà présent if (liste->last != NULL) { // Le dernier noeud présent enchaine sur celui qu'on vient de créer liste->last->next=nouveau; } // Quoi qu'il arrive, le noeud nouvellement créé ira en fin de liste (puisque quoi qu'il arrive c'est le dernier a avoir été créé) liste->last=nouveau; // On a un noeud de plus dans la liste liste->nb_noeuds++; // Le travail a été fait - On renvoie une valeur indiquant qu'il n'y a pas eu de soucis - Le plus simple est alors de renvoyer l'adresse crééé return nouveau; }
Avec cette fonction tu n'as plus de soucis de mémoire. Dès que tu veux stocker un nouveau jeu, tu l'appelles et tu la laisses se débrouiller (en vérifiant tout de même son retour pour t'assurer que le jeu a bien été stocké)...

Okay, merci pour ces précisions et ce plan de route. Ca m'a permit d'apprendre ce qu'étaient les structures, typedef...

Si je considère avoir déjà traité la création des jeux représenté par la variable board[ligne][colonne], je suis donc en train d'essayer de mettre en place la "structure permettant de manipuler différents jeux". Néanmoins j'ai un problème dans la mesure ou la taille x,y de "jeu[x][y]" que vous m'avez donné n'est pas fixée dès le départ dans la mesure ou cela dépend de ce que le joeur entre comme taille d lorsqu'il entre l'argument de type int au programme.

Cela résulte en une erreur fields must have a constant size dans le code de la structure de s_noeud qui représente les états de mon jeu et que j'ai mis à la fin du main:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int main(int argc, string argv[]) { // ensure proper usage if (argc != 2) { printf("Usage: fifteen d\n"); return 1; } // ensure valid dimensions d = atoi(argv[1]); //lots of code to greet, initialise, draw the array and move the tiles... Not yet how A_star is called. typedef struct s_noeud{ int jeu[d][d]; struct s_noeud *next; } t_noeud; }
Autre question plus théorique, je ne comprends pas pourquoi en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2".

Merci pour votre aide en tout cas!

08/10/2016, 22h11
Sve@r

Citation:

Envoyé par AntoineCompagnie

Autre question plus théorique, je ne comprends pas pourquoi en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2".

C'est juste une façon de parler. Plus facile (enfin de mon point de vue) de manipuler d'un coté une simple liste de trucs et de l'autre coté un jeu 2D plutôt qu'un tableau 3D représentant le jeu 2D dans différents êtats...

Citation:

Envoyé par AntoineCompagnie

Oui, la taille est donnée dès le départ lors de l'appel du programme par ./fifteen 3 par exemple, qui donnera un tableau de taille 3*3.

Ok. Alors non, tu ne pourras pas compiler l'exécutable entre deux changements de paramètres. ;) Il faut donc qu'il fonctionne d'emblée pour toute taille de grille.

Formulé autrement : la taille de l'espace mémoire occupé par une grille ne peut être déterminée qu'au moment de l'exécution, raison pour laquelle tu ne pourras pas utiliser directement la construction proposée par Sve@r plus haut car :
Code:

1 2 3 4 typedef struct s_noeud{ int jeu[x][y]; struct s_noeud *next; } t_noeud;
...implique que les valeurs d'x et d'y soient connues à la compilation, comme tu as pu t'en rendre compte puisque le compilateur t'as jeté sans ménagement.

Tu dois en conséquence utiliser l'allocation dynamique pour allouer les grilles une fois les paramètres récupérés. Or l'allocation dynamique et l'utilisation d'un objet qui ressemble à un tableau multidimensionnel statique (ton int **) est bien plus compliquée que celle d'un buffer classique à une dimension.

D'où mon conseil : alloue un simple int * et adresse-le sur une seule dimension : board[y * w + x]. Cela te dispense d'une indirection superflue et te garantit un bloc contigü en mémoire système, i.e. adressable d'une traite sans discontinuité. Ça permet notamment des trucs plutôt sympa comme memcpy.

Cela étant dit je rejoins les autres intervenants sur leurs conseils de méthodologie : la clef du succès en développement logiciel est de segmenter le problème. Vas-y par étapes :
définis d'abord la structure de la grille de jeu et les données associées, sans aucune référence à l'algorithme de résolution, exemple :
Code:

1 2 3 4 typedef struct { int *grid; size_t size; } board_t;
;
écris un ensemble de petites fonctions utilitaires pour effectuer des opérations sur une grille : allouer (exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 /* sur le modèle des fonctions d'allocation standard, il revient à l'appelant de s'assurer de la conformité de l'adresse retournée */ board_t *board_alloc(size_t size) { board_t *b = malloc(sizeof(board_t)); if (!b) return NULL; b->grid = malloc(size * size * sizeof(int)); if (!b->grid) { free(b); return NULL; } b->size = size; return b; }
), réinitialiser, copier, détruire, déplacer la case i vers le haut/bas/gauche/droite, etc... ;
assure-toi que tout cela fonctionne en écrivant des petits tests unitaires (on doit presque pouvoir jouer au taquin, puisque c'est ce que l'IA devra faire au final) ;
décris sur papier le fonctionnement logique de ton algorithme de résolution et déduis-en les fonctionnalités intermédiaires dont tu auras besoin (listes, files...) comme te l'a conseillé picodev ;
implémente ces fonctionnalités en C, et là encore assures-toi qu'elles fonctionnent correctement avec des données arbitraires ;
implémente ton A*.
Ça peut sembler fastidieux, je te l'accorde. Mais le temps que tu passes en analyse et en tests, tu le gagnes en prises de tête par la suite. Tu seras au bar avec une bière et en bonne compagnie pendant que tes camarades en seront encore à débugger leur programme. ;)

09/10/2016, 17h39
Sve@r

Citation:

Envoyé par Matt_Houston

Ça permet notamment des trucs plutôt sympa comme memcpy.

Moui. C'est effectivement un gros avantage. Mais on perd l'info sur le positionnement 2D des pions les uns par rapport aux autres. Donc à réfléchir sur ce qu'on veut garder et perdre. Sachant aussi que même si on fait de l'allocation double étoile (2D) on peut ensuite construire un équivalent de memcpy() adapté au jeu ainsi alloué. De même, si on reste en 1D, on peut aussi construire ensuite des outils permettant de faire remonter les infos de positionnement manquantes. Donc quel que soit le choix, il y aura des avantages, des inconvénients mais on pourra toujours y arriver.

Citation:

Envoyé par Matt_Houston

Ça peut sembler fastidieux, je te l'accorde. Mais le temps que tu passes en analyse et en tests, tu le gagnes en prises de tête par la suite

J'approuve. C'est comme pour une maison: il faut commencer par poser de bonnes bases. On perd du temps au début mais ensuite on va 10 fois plus vite.
09/10/2016, 20h47
Matt_Houston
Refaisons le point pour ne pas créer la confusion chez l'OP. Il existe en C trois sortes de tableaux bidimensionnels (limitons-nous à la 2D puisque c'est le sujet) ou désignés comme tels par abus de langage :
- le « vrai » tableau bidimensionnel, statique, qui peut éventuellement être utilisé pour indexer des objets de genre « matrice » (nombre d'éléments fixe au sein des lignes et des colonnes) : matrice mathématique, échiquier, image (c'est rare les images de taille prévisible :mrgreen:)... ;
- le tableau de pointeurs utilisé en « double adressage » ou buffer alloué en double étoile, comme tu dis (le terme me plaît bien, c'est explicite), dynamique, non contigü, qui nécessite plusieurs allocations ;
- le VLA bidimensionnel, mais trop avancé pour l'OP et impossible à intégrer à une struct (sauf via une obscure extension GCC) donc hors sujet ici, j'en cause même pas.
Seul le second est applicable au cas d'utilisation de l'OP. Mais je lui déconseille car - et ça n'engage que moi - c'est inutilement compliqué. De plus, sémantiquement un tableau de pointeurs ne devrait IMHO jamais être utilisé pour indexer des matrices (sauf contrainte technique, i.e. : la matrice est tellement énorme qu'il faut la streamer par lignes ou par colonnes).

Citation:

Envoyé par Sve@r

Sachant aussi que même si on fait de l'allocation double étoile (2D) on peut ensuite construire un équivalent de memcpy() adapté au jeu ainsi alloué.

Oui et c'est justement ce que j'essaie d'éviter à l'OP. Souviens-toi du code proposé dans le premier post de ce fil : il est motivé mais il part de loin, hein. ;)

Je ne sais plus où ça se trouve dans le K&R mais les tableaux multidimensionnels, ça devrait pas être enseigné avant la gestion de mémoire (et puis même, c'est franchement dispensable). Au final on se récupère régulièrement des gars qui veulent faire du traitement d'image dans un buffer alloué (ou même pas alloué d'ailleurs) en double étoile avec les catastrophes qui s'ensuivent.
10/10/2016, 00h38
AntoineCompagnie

Je tiens à préciser que mon jeu fonctionne parfaitement jusqu'à présent! A la main mais il fonctionne!

Donc pour résumer:
Pour biend débuter mon algorithme A-star
Je dois d'une représenter le tableau de l'état courant mais c'est déjà fait avec board. Je dois, d'autre part, garder en mémoire les autres tableaux.
Pour cela j'utilise deux structure, comme dans une pile: un noeud et un suivant qui référence un noeud.

Pour cela je dois définir le jeu/ le board que je manipule dans le noeud.
Mais comment représenter ce jeu, telle est la question. Dans la mesure ou la taille du tableau est donné comme argument, Matt_Houston me propose d'utiliser un

Citation:

int * et adresse-le sur une seule dimension : board[y * w + x]. Cela te dispense d'une indirection superflue et te garantit un bloc contigü en mémoire système, i.e. adressable d'une traite sans discontinuité. Ça permet notamment des trucs plutôt sympa comme memcpy

Ensuite des fonctions utilitaires pour effectuer des opérations sur une grille : allouer dont il donne un exemple (mais que je n'ai encore pas totalement saisi).

Cependant Sve@r ajoute que

Citation:

on perd l'info sur le positionnement 2D des pions les uns par rapport aux autres.

La conclusion est que je peux représenter les tableaux que j'ai visité de pointeurs utilisé en utilisant ce fameux « double adressage » ou buffer alloué en double étoile.

Par conséquent sachant que la contrainte donnée par le prof est d'utiliser ce fameux tableau board[x_i][y_i] étant donnée la taille d, comment puis-je stocker les nœuds?
10/10/2016, 10h21
Matt_Houston

Le prof vous a donc fourni la structure qui représente un état du jeu ? Alors effectivement c'est une contrainte. Tu disposes donc déjà d'une fonction d'allocation j'imagine ?

Sve@r t'a proposé une construction qui permet de chaîner des états de jeu ensemble (t_noeud : remplace le membre jeu par ton type de board, grid ou que sais-je). Pour le reste, mes conseils s'appliquent toujours : tu as besoin de fonctions utilitaires qui opèrent sur cette structure. Écris plutôt de petites fonctions qui réalisent des tâches simples.

Pour ajouter une grille à la liste d'états par exemple, il faut d'abord disposer d'une copie complète de l'état d'origine. Pour obtenir une copie, il faut allouer l'espace nécessaire puis copier le ou les bloc(s) mémoire. Chaque expression en gras ci-avant désigne une fonction à implémenter. Les fonctions qui réalisent des tâches complexes invoquent celles qui réalisent des tâches plus simples.

Citation:

Envoyé par AntoineCompagnie

Cependant Sve@r ajoute que

Citation:

on perd l'info sur le positionnement 2D des pions les uns par rapport aux autres

Pas vraiment, si i est l'index considéré avec size la taille de la grille alors on retrouve x et y via respectivement i % size et i / size. Rien n'interdit non plus de stocker x et y plutôt qu'un unique index.

Citation:

Envoyé par Matt_Houston

Refaisons le point pour ne pas créer la confusion chez l'OP. Il existe en C trois sortes de tableaux bidimensionnels (limitons-nous à la 2D puisque c'est le sujet) ou désignés comme tels par abus de langage :

le « vrai » tableau bidimensionnel, statique, qui peut éventuellement être utilisé pour indexer des objets de genre « matrice » (nombre d'éléments fixe au sein des lignes et des colonnes) : matrice mathématique, échiquier, image (c'est rare les images de taille prévisible :mrgreen:)... ;
le tableau de pointeurs utilisé en « double adressage » ou buffer alloué en double étoile, comme tu dis (le terme me plaît bien, c'est explicite), dynamique, non contigü, qui nécessite plusieurs allocations ;
le VLA bidimensionnel, mais trop avancé pour l'OP et impossible à intégrer à une struct (sauf via une obscure extension GCC) donc hors sujet ici, j'en cause même pas.

[...]

Il y a aussi la solution «bâtarde» qui mélange les deux premières options : tableaux de pointeurs utilisé en «double adressage» mais en allouant «tout le tableau en 1d» à la case [0][0] puis en faisant pointer les autres [i][0] au bon endroit dans ce tableau 1D.
Code:

1 2 3 4 5 6 7 8 int **matrix_create(size_t lines, size_t cols) { int **matrix=malloc(lines * sizeof *matrix); matrix[0]=malloc(lines * cols * sizeof *matrix[0]); for(size_t l=1; l<lines; ++l) matrix[l]=&(matrix[0][l*cols]); return matrix; }
Code tapé à la volée, il faut ajouter les vérifications sur les mallocs et un peu d'indulgence si je me suis trompé.

On combine un peu les avantages des deux premières solutions :

localité des données
nombre d'allocations et de libérations limitées
choix d'accès : soit via un «tableau 1D» soit avec une «notation matricielle»

Citation:

Envoyé par Matt_Houston

Le prof vous a donc fourni la structure qui représente un état du jeu ? Alors effectivement c'est une contrainte. Tu disposes donc déjà d'une fonction d'allocation j'imagine ?

Oui, si j'ai bien compris ce qu'était l'allocation voici celle donnée par le prof ainsi que son appel dans le main (j'ai essayé de faire light):

Code:

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
 
// constants
#define DIM_MIN 3
#define DIM_MAX 9
 
int board[DIM_MAX][DIM_MAX];
 
int main(int argc, string argv[])
{
    // ensure proper usage
    if (argc != 2)
    {
        printf("Usage: fifteen d\n");
        return 1;
    }
 
    // ensure valid dimensions
    d = atoi(argv[1]);
    if (d < DIM_MIN || d > DIM_MAX)
    {
        printf("Board must be between %i x %i and %i x %i, inclusive.\n",
            DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX);
        return 2;
    }
 
    // greet user with instructions
    greet();
 
    // initialize the board
    init();
 
    // accept moves until game is won
    while (true)
    {
        // clear the screen
        clear();
 
        // draw the current state of the board
        draw();
 
        // log the current state of the board (for testing)
        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < d; j++)
            {
                fprintf(file, "%i", board[i][j]);
                if (j < d - 1)
                {
                    fprintf(file, "|");
                }
            }
            fprintf(file, "\n");
        }
        fflush(file);
 
    }
 
}
 
void init(void)
{
    nombre = d*d-1;
    for(int ligne = 0; ligne<d; ligne++){
        for (int colonne= 0;colonne<d;colonne++){
            board[ligne][colonne]=nombre;
            nombre = nombre-1;
        }
    }
 
        if(d%2==0){
            printf("on a un nombre paire");
            board[d-1][d-3]=1;
            board[d-1][d-2]=2;
        }
    //i will always remain the same    
    int i = d * d - 1;
    srand(time(NULL));
    while (i > 0) {
      int j = (rand() * i)%((d*d)-1);
      int xi = i % d;
      int yi = i / d;
      int xj = j % d;
      int yj = j / d;
 
        if(xj<0){
            printf("\nproblème, xj = %i\n",xj);
            printf("i = %i\n",i);
            break;
        }
                if(yj<0){
            printf("\nproblème, yj = %i\n",yj);
                        printf("j = %i\n",j);
                        break;
        }
 
        swapTiles(xi, yi, xj, yj);
      --i;
      }
 
 
}

Pour moi l'allocation est faite dans init avec les déclarations d'au dessus. Dites moi si je me trompe, j'apprends toujours de mes erreurs :)

Je vais donc continuer à réflechir sur comment faire les fonctions suivantes. Je n'ai pas encore d'idée précise.

ajouter une grille à la liste d'états
obtenir une copie
allouer l'espace nécessaire
copier le ou les bloc(s) mémoire.

Merci picodev pour l'idée de solution batârde! Je vais creuser!

Non, l'allocation est réalisée ici : int board[DIM_MAX][DIM_MAX]; . Le tableau de DIM_MAX * DIM_MAX est présent dès le début du programme, ses dimensions sont fixes et il n'y a donc pas d'allocation manuelle à réaliser.

En fait ton prof utilise une technique très simple à laquelle personnellement je n'avais pas pensé :mrgreen: : définir une taille maximum (à savoir DIM_MAX), allouer (en statique) une grille de cette taille et n'utiliser à l'exécution que ce dont on a besoin. C'est bourrin mais tout à fait adapté ici et ça simplifie pas mal de choses, tu peux en conséquence utiliser la structure de Sve@r en remplaçant x et y par DIM_MAX et tu n'as plus qu'un seul appel à malloc à faire par noeud. Si cela ne t'évoque pas grand chose, renseigne-toi sur les termes allocation dynamique, liste chaînée et sur leur application en C.

Y'a-t-il d'autres contraintes dans l'énoncé ? Ça pourrait nous aider à y voir plus clair.

Citation:

Envoyé par AntoineCompagnie

Pour moi l'allocation est faite dans init avec les déclarations d'au dessus. Dites moi si je me trompe, j'apprends toujours de mes erreurs :)

Non, on désigne sous le nom d'allocation le fait de demander au système d'exploitation de nous réserver un espace en mémoire d'une taille que l'on spécifie. En l'occurrence pour y stocker l'état d'une grille de jeu. Cette allocation est ici automatique pour la grille principale, car elle est déclarée comme tableau statique (car ses dimensions et son type, donc sa taille en mémoire, sont connues à la compilation) à portée globale (car hors de toute fonction). Les données contenues dans un bloc mémoire tout juste réservé sont inexploitables, il faut les initialiser après obtention.

L'initialisation consiste à remplir un bloc préalablement alloué (réservé) avec les données que l'on spécifie. L'allocation est donc un préalable à tout traitement sur des données stockées en mémoire système, puisqu'il est interdit de toucher à de la mémoire qu'on n'a pas réservé.

Exemple :
Code:

1 2 3 4 int i; // allocation d'un bloc mémoire de taille sizeof(int), il peut contenir n'importe quoi i = 0; // initialisation du bloc identifié par i à la valeur 0 int j = 42; // allocation d'un bloc de taille sizeof(int), immédiatement initialisé à la valeur 42
@picodev : c'est vrai il existe aussi cette possibilité, astucieux. :)