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 :

Blocage exercice C


Sujet :

C

  1. #1
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut Blocage exercice C
    Bonjour, je suis étudiant en 1 ère année dans une école d'informatique et j'ai un projet à rendre pour bientôt dans lequel je bloque complètement, il s'agit du BSQ..
    Ce projet consiste a trouver, dans une map donnée : exemple :
    .....o..
    .o......
    .o...o.o
    .o......
    .....o..
    .oo...o.
    .o.o....
    ..o.....
    Le plus grand CARRE dans cette map et le remplacer par des X comme ceci :
    .....o..
    .oXXX...
    .oXXXo.o
    .oXXX...
    .....o..
    .oo...o.
    .o.o....
    ..o.....

    Alors voila j'ai récupérer la map dans un buffer puis ensuite je l'ai stocké dans un tableau à 2 dimensions pour facilité la recherche. Mais l'algorithme de recherche je ne le comprend pas, du moins je ne vois pas du tout comment le coder si ce n'est avec 5678 variables peut être et encore ... J'ai vu qu'il y avait une méthode qui consistait à partit d'un point qui serait le coté haut/gauche de mon carré et ensuite de descendre et étendre par la droite mais je ne vois pas comment je peux crée ça avec les while et les if, vraiment pas...
    ( ah oui je précise que j'ai stocké dans un tableau de int à double entrée mais cela ne change pas grand chose de toute manière..
    Voila mon ébauche de code et je suis donc dans la fonction algo qui doit crée la recherche ... =>

    En espérant une aide, merci et bonne journée..

    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
     
    int             bsq(char *filepath, int my_size)
    {
      int           fd;
      char          *str;
      char          buffer[my_size];
      int           r;
      int           cpt;
      int           column;
      int           lane;
     
      str = malloc(my_size * sizeof(char));
      fd = fs_open_file(filepath);
      while ((r = read(fd, buffer, my_size)) > 0)
        {
          column = cpt_column(buffer, cpt, column);
          lane = cpt_lane(buffer, cpt, lane);
          if (r != 0)
            {
              buffer[r] = 0;
              my_strcat(str, buffer);
            }
        }
      buff_in_int(buffer, column, lane);
      /* printf("%c", '\n'); */
      /* printf("%c", '\n'); */
      /* printf("%c", '\n'); */
      printf("%s", str);
      close(fd);
      return (0);
    Le stockage du buffer dans le tableau :
    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
     
    void            buff_in_int(char *buffer, int column, int lane)
    {
      int           tab_int[lane][column];
      int           cpt;
      int           a;
      int           b;
      int           dim;
     
      a = 0;
      b = 0;
      cpt = 0;
      dim = 0;
      while (buffer[a] != '\n') // je met a la 2eme ligne                                        
        a = a + 1;
      a = a + 1;
      while (b != lane - 1) // on crée notre tableau de int                                      
        {
          while (cpt != column)
            {
              if (buffer[a] == '.')
                tab_int[b][cpt] = 0;
              else if (buffer[a] == 'o')
                tab_int[b][cpt] = 1;                                                             
              a = a + 1;
              cpt = cpt + 1;
            }
          a = a + 1;
          cpt = 0;
          b = b + 1;
        }
      algo(column, lane, tab_int);
    }
    Mon compteur de ligne et de colonne :
    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
     
    int             cpt_lane(char *buffer, int cpt, int lane)
    {
      lane = 0;
      cpt = 0;
      while (buffer[cpt] != '\0')
        {
          if (buffer[cpt - 1] == '\n')
            lane = lane + 1;
          cpt = cpt + 1;
        }
      return (lane);
    }
    int             cpt_column(char *buffer, int cpt, int column)                                
    {
      cpt = 0;
      column = 0;
      while (buffer[cpt] != '\n')
        cpt = cpt + 1;
      while (buffer[cpt + 1] != '\n')
        {
          column = column + 1;
          cpt = cpt + 1;
        }
      return (column);
    }
    Puis l'algo ... :

    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
     
    int             algo(int column, int lane, int tab_int[lane][column])
    {
      int           cpt;
      int           cpt2;
      int           cpt3;
      int           a;
     
      a = 0;                                                                                     
      cpt = 0;
      cpt2 = - 1;
      cpt3 = 0;
      while (cpt < column)
        {
          if (tab[a][cpt] == 0)
            {
     
            }
          cpt = cpt + 1;
        }
    }

  2. #2
    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
    Tu devrais peut-être écrire ton algo en français, au calme, sur un morceau de papier au lieu d'imaginer déjà sa transcription en C. C'est plus une question pour la section algorithmique.

    Voici la façon dont j'aborderais le problème si j'y étais confronté :
    1. on part d'un coin de la matrice ;
    2. c'est pour l'instant le plus grand carré qu'on ait trouvé (1x1, forcément il répond aux critères), on stocke ses coordonnées (x_min <- 0, x_max <- 1, y_min <- 0, y_max <- 1) et la valeur qu'il contient ;
    3. on étend le carré en ajoutant 1 à ses côtés tant qu'il contient uniquement cette valeur, en mettant à jour le set de coordonnées à chaque itération ;
    4. on revient à l'étape 1 en partant cette fois du point (x_max, 0), si x_max est égal à la largeur de la matrice, on part du point (0, y_max) ;
    5. on s'arrête :
      • soit lorsqu'il n'est plus possible, dans l'aire restant à traiter, de caser un plus grand carré que le carré actuellement stocké ;
      • soit lorsque x_max = largeur et y_max = hauteur.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut
    Bonjour,

    Merci de ta réponse !
    J'ai déjà essayer de le poser sur papier mais je vais retenter une nouvelle fois..
    J'avais déjà penser à cette idée d'etendre le carré en partant du point en haut a gauche donc il suffit de lui dire tant qu'il y a un point a X colonnes et X lignes continue.. Mais ce qui me bloque c'est (par exemple pour un carré de 2 x 2)
    On lui dit avance en x + 1 et en y + 1, super il y a des points ! Ce qui nous ferait par exemple :

    XX.........
    X...........
    .............

    Mais comment vérifie t'on qu'il n'y est pas d'obstacles alors en coordonné (1,1) (le coté en bas a droite) et vice versa pour le 3x3, 4x4 etc ??.. C'est surtout ça que je n'arrive pas à comprendre.

  4. #4
    Membre chevronné

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Points : 1 878
    Points
    1 878
    Billets dans le blog
    21
    Par défaut
    Mmm... je ne connais pas l'algorithme dont tu parles. Si tu es pressé et veux faire du vite fait pas optimisé, je peux te proposer cela:

    1) faire une fonction pour voir si un carré de côté c est possible au coordonnées x, y dans le tableau:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int does_fit(int x, int y, int s, const int tab** t, int m, int n) // le tableau est de dimension m*n
    {
      int cm, cn;
      if (m < x+s || n < y+s) return 0; // si on déborde du tableau
      for (cm = x; cm < x+s; ++cm)
        for (cn = y; cn < y+s; ++cn)
          if (tab[cm][cn] != 0) return 0;
      return 1;
    }
    2) utilise cette fonction sur le coin supérieur gauche sur chaque case, en agrandissant à chaque fois. Une fois le carré le plus grand obtenu pour la première case, tu ne testes que les carrés plus grands sur les autres cases à cibler. Déterminer les autres cases à cibler est le point le plus difficile.

    A) Tu peux faire force brute et tester toutes les cases, ça ne prendra de toute façon que quelques milisecondes tant que le rectangle d'accueil est de taille raisonnable:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void max_possible(const int tab** t, int m, int n, int* x, int* y, int* s) // les trois derniers int pour stocker le résultat: coordonnées angle supérieur et taille
    {
      int tmpmax = 0, tmpx = 0, tmpy = 0;
      int ix, iy;
      for (ix = 0; ix < m; ++ix)
        for (iy = 0; iy < n; ++iy) {
          while (does_fit(ix, iy, tmpmax, tab, m, n))
            { ++tmpmax; tmpx = ix; tmpy = iy; }
        }
      *x = tmpx; *y = tmpy; *s = --tmpmax;
    }
    B) Une première optimisation simple est de raccourcir la boucle en diminuant les limites de la taille du plus grand carré déjà obtenu: au delà, les carrés obtenus seront nécessairement plus petits:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void max_possible(const int tab** t, int m, int n, int* x, int* y, int* s) // les trois derniers int pour stocker le résultat: coordonnées angle supérieur et taille
    {
      int tmpmax = 0, tmpx = 0, tmpy = 0;
      int ix, iy;
      for (ix = 0; ix < m-tmpmax; ++ix) // on enlève à la boucle la taille du plus grand carré obtenu
        for (iy = 0; iy < n-tmpmax; ++iy) { // idem
          while (does_fit(ix, iy, tmpmax, tab, m, n))
            { ++tmpmax; tmpx = ix; tmpy = iy; }
        }
      *x = tmpx; *y = tmpy; *s = --tmpmax;
    }
    C) à toi de jouer pour d'autres optimisations, mais il faut déjà plus réfléchir...

    PS: je n'ai pas testé mon code, il peut y avoir des petites erreurs à corriger

  5. #5
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut
    Bonjour,

    Je n'ai pas tout à fait compris le code car je n'ai pas la droit d'utiliser la boucle for et je ne vois pas dans la première fonction a quoi correspond la variable s.
    Je vais essayer de m'y attardé un peu plus longtemps.. Merci

    ( PS : Les tests qui vont passés sur le programme peuvent avoir une map très très grande mais je ne veux pas de l'optimisation pour le moment de toute manière..)

  6. #6
    Membre chevronné

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Points : 1 878
    Points
    1 878
    Billets dans le blog
    21
    Par défaut
    tu n'as pas le droit d'utiliser la boucle for!!! quelle drôle d'idée!
    enfin l'équivalent avec while est juste un peu plus lourd:

    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
    int does_fit(int x, int y, int s, const int tab** t, int m, int n) // le tableau est de dimension m*n
    {
      int cm, cn;
      if (m < x+s || n < y+s) return 0; // si on déborde du tableau
      cm = x;
      while (cm <  x+s) {
        cn = y;
        while (cn < y+s) {
          if (tab[cm][cn] != 0) return 0;
          ++cn;
        }
        ++cm;
      }
      return 1;
    }
    s pour size, la taille / le côté du carré

  7. #7
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut
    Merci de vous donner du mal pour mon problème mais je ne vois définitivement toujours pas comment faire pour trouver le plus grand carré avec les ressources que j'ai et que vous m'avez donné.. Je ne vois pas la logique pour vérifier qu'on à bien un carré,..
    comme cité plus haut par exemple si on a un point a tel endroit, on avance en x et en y, il y a des points super, on avance encore une fois donc on arrive la (pour exemple ):

    XXX....
    X.......
    X........

    mais la après tout m'échappe pour vérifier s'il y a bien des points au lieu des obstacles aux endroits ici en rouge :
    XXX....
    XXX.....
    XXX......

    Je pense abandonner le projet je suis démoralisé c'est la première fois que je bloque vraiment sur un algorithme dont j'ai plus ou moins la logique... Désolé de vous avoir fait perdre du temps..

  8. #8
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut
    Bon je persévère encore un peu j'ai essayer de coder quelque chose asser tordu donc je vous ai mis des indications... Je le fais tourner a la main point par point avec pour exemple :

    .....o..
    .o......
    .o...o.o
    .o......
    .....o..
    .oo...o.
    .o.o....
    ..o.....

    Donc voila il y a encore pas mal de soucis que je n'arrive pas à reglé, et surtout, le fait de "sauvegarder/afficher les X" pour le plus grand carré... Pour le moment l'algo que je fais ne fait que se déplacer mais de carré en carré (plus ou moins...) J’espère que vous comprendrez le code...

    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
     
    int             algo(int column, int lane, char tab_char[lane][column])
    {
      int           x;
      int           y;
      int           z;
      int           cpt;                                                                                                                                                                                                                                                                                                        
     
      x = 0;
      y = 0;
      z = 0;
      cpt = 0;
      while (y < lane) // jusqu'a la fin de mes lignes                                                                                                                                                                                                                                                                          
        {
          while (x < column) // jusqu'a la fin de mes colonnes                                                                                                                                                                                                                                                                  
            {
              while (tab_char[y][x] == '.') // tant qu'on trouve un "."                                                                                                                                                                                                                                                         
                {
                  while (tab_char[y][x + 1] == '.' && tab_char[y + 1][x] == '.') // si sur le coté droit et juste en dessosu on a un point on descend en bas a droite du carré                                                                                                                                                  
                    {
                      x = x + 1;
                      y = y + 1;
                      cpt = cpt + 1;
                    }
                  while (cpt != 0) // si on tombe sur un 'o' on remonte a notre ligne de depart a l'aide d'un compteur                                                                                                                                                                                                          
                    {
                      y = y - 1;
                      cpt = cpt - 1;
                    }
                  if (cpt == 0 && tab_char[y][x + 1] == 'o') // du bidouillage pour avancer...                                                                                                                                                                                                                                  
                    x = x + 1;
                }
              if (tab_char[y][x] == 'o') // si on rencontre un 'o' et non un '.' on avance, mais si on en est sortit a Y lignes, on remonte a notre ligne d'origine a l'aide de compteur                                                                                                                                        
                {
                  if (cpt == 0)
                    x = x + 1;
                  while (cpt != 0)
                    {
                      y = y - 1;
                      cpt = cpt - 1;
                    }
                }
            }
          y = y + 1; // dès que j'ai fini mes colonnes, je descend d'une ligne et je réinitialise pour repartir de la gauche;.                                                                                                                                                                                                  
          x = 0;
        }
      my_putchar('\n');
    }

  9. #9
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Octobre 2014
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Aisne (Picardie)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Octobre 2014
    Messages : 22
    Points : 16
    Points
    16
    Par défaut
    Je reconnais l'immonderie du code par ailleurs..

Discussions similaires

  1. Blocage sur un exercice du livre de Bjarne Stroustrup
    Par Go'Gaule dans le forum Débuter
    Réponses: 17
    Dernier message: 13/02/2012, 14h23
  2. [CVS] "blocage" de ressource ?
    Par xa1 dans le forum Eclipse Java
    Réponses: 1
    Dernier message: 06/10/2003, 17h26
  3. Blocage à 60 images par seconde
    Par houssa dans le forum OpenGL
    Réponses: 5
    Dernier message: 24/06/2003, 09h52
  4. [Kylix] Blocage Kylix 3
    Par DevX dans le forum EDI
    Réponses: 2
    Dernier message: 13/11/2002, 21h29
  5. Pouvez vous m'aider a resoudres ces 3 exercices
    Par algorithmique dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 09/08/2002, 18h26

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