IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

affecter dynamiquement un tableau


Sujet :

C

  1. #1
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut affecter dynamiquement un tableau
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 !

  2. #2
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 685
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 685
    Points : 30 974
    Points
    30 974
    Billets dans le blog
    1
    Par défaut
    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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  3. #3
    Invité
    Invité(e)
    Par défaut euh je comprends pas ton code
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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];
            }
        }

  4. #4
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut
    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.

    Nom : taquin.png
Affichages : 235
Taille : 18,6 Ko

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    open_set=malloc(???*sizeof(int*))
    Tout en bouclant à chaque itération:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ? 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.

  5. #5
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    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.

  6. #6
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    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.

  7. #7
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    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 Voir le message
    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!

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 685
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 685
    Points : 30 974
    Points
    30 974
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par AntoineCompagnie Voir le message
    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 Voir le message
    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 c : Sélectionner tout - Visualiser dans une fenêtre à part
    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 c : 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
    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é)...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  9. #9
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut
    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 : 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
    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!

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 685
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 685
    Points : 30 974
    Points
    30 974
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par AntoineCompagnie Voir le message
    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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  11. #11
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    Citation Envoyé par AntoineCompagnie Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
      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 : 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
      /* 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.

  12. #12
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 685
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 685
    Points : 30 974
    Points
    30 974
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    Ç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 Voir le message
    Ç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.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  13. #13
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    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 )... ;
    • 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 Voir le message
    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.

  14. #14
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut
    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

    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

    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?

  15. #15
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    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 Voir le message
    Cependant Sve@r ajoute que

    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.

  16. #16
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Points : 2 601
    Points
    2 601
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    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 )... ;
    • 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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»

  17. #17
    Membre du Club
    Homme Profil pro
    Etudiant
    Inscrit en
    Novembre 2015
    Messages
    156
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Etudiant

    Informations forums :
    Inscription : Novembre 2015
    Messages : 156
    Points : 52
    Points
    52
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    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 : 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
     
    // 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!

  18. #18
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    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é : 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 Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

Discussions similaires

  1. Affectation dans un tableau dynamique
    Par psohier dans le forum Langage
    Réponses: 2
    Dernier message: 04/08/2010, 20h16
  2. Affectation "dynamique" de valeurs dans un tableau
    Par devdebutante dans le forum PHP & Base de données
    Réponses: 11
    Dernier message: 25/06/2009, 19h30
  3. affectation sur un tableau dynamique
    Par oranoutan dans le forum C
    Réponses: 35
    Dernier message: 27/06/2007, 01h16
  4. Réponses: 6
    Dernier message: 26/11/2005, 19h55
  5. Création dynamique de tableau.
    Par Yux dans le forum C
    Réponses: 6
    Dernier message: 05/11/2005, 16h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo