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

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2012
    Messages : 16
    Points : 17
    Points
    17

    Par défaut comprendre le fonctionnement de ces lignes de code java

    Bonjour,

    je n'arrive pas à comprendre le principe utilisé pour résoudre ce problème (Voir les commentaires dans le code). En fait cet algorithme résout le problème de 8 r sur une dame.

    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
    public static void main(String[] args) {
        int y = 0;
        b[0] = -1;
     
        while (y >= 0) {
     
        	do
        	{ b[y]++; 
        	System.out.println(""+b[y]);}
     
          while ((b[y] < 8) && unsafe(y));
     
          if (b[y] < 8) 
          {
            if (y < 7) {
              b[++y] = -1;  // à ce niveau la qu'est ce qu'il fait et quand appelle exactement putboard ?
              System.out.println("b["+y+"] = -1");
            } else {
     
              putboard(); // mettre les 8 r sur la dame
     
            }
          } else
          {y--;}//else
     
        }
     
     
      }
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    static boolean unsafe(int y) {
        int x = b[y];
        for (int i = 1; i <= y; i++) {
          int t = b[y - i];
          if (t == x || t == x - i || t == x + i) { // pourquoi on compare t et x +/- i ????
            return true;
     
          }
        }
     
        return false;
      }

  2. #2
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    septembre 2009
    Messages
    11 451
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2009
    Messages : 11 451
    Points : 26 892
    Points
    26 892
    Billets dans le blog
    2

    Par défaut

    Salut,

    1. b[++y] = -1; // à ce niveau la qu'est ce qu'il fait et quand appelle exactement putboard ?
      1. On fait d'abord ++y, ce qui incrémente y
      2. Ensuite, on met -1 dans la cellule d'index y du tableau b

      Tout simplement.

      Quant à l'appel de putboard, il suffit de regarder le test :

      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      5
      6
      7
      8
      f (y < 7) {
                 // on appelle pas putboard
              } else {
       
                // on appelle putboard
                putboard(); // mettre les 8 r sur la dame
       
              }
      Donc on appelle putboard quand y n'est pas inférieur à 7.


    2. if (t == x || t == x - i || t == x + i) { // pourquoi on compare t et x +/- i ????Déjà, pour répondre à cette question, il faut déterminer ce que sont x et t :
      • int x = b[y];
      • int t = b[y - i];


      Donc on compare deux cellules du tableau b, la première correspond à une cellule fixée par le paramètre de unsafe, l'autre correspond à différentes cellules successives (boucle for (int i = 1; i <= y; i++) {.

      on parcourt le tableau de y-y à y-1, donc de 0 à y exclus. Donc on compare chaque b[] (t) précédent celui fixé au début(x).

      C'est plus compliqué de savoir pourquoi on compare t et x+/-i sans avoir le programme/algorithme complet. Mais, on peut commencer à s'intéresser à la boucle do/while :

      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      5
      6
      do { 
       
         b[y]++; 
         System.out.println(""+b[y]);
       
      } while ((b[y] < 8) && unsafe(y));
      Quand on l'indente correctement (ça aussi ça aide à comprendre un code !), on voit qu'on incrémente la valeur d'une cellule de b (initialisée à -1, donc qui va prendre des valeurs de 0 à n), tant qu'une condition n'est pas vérifiée. Cette condition indique qu'on incrémente tant qu'on a à la fois b[y]<8 et unsafe(y) true, donc que le test (t == x || t == x - i || t == x + i) est true.
    3. Maintenant, pour comprendre l'algorithme entier, il vaudrait mieux regarder l'algorithme d'abord, non encodé dans un langage particulier, voire même en français dans le texte. Ensuite, on peut éventuellement exécuter le programme pas à pas, et voir comment progresse le contenu du tableau.

    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2012
    Messages : 16
    Points : 17
    Points
    17

    Par défaut

    j'ai essayé de l'éxecuter manuellement mais a chaque fois je me trouve bloqué surtout unsafe est la clé je pense pour comprendre le reste
    eh voici l'algorithme entier

    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
     
     
    public class NQueens {
     
      private static int[] b = new int[8];
      private static int s = 0;
     
      static boolean unsafe(int y) {
        int x = b[y];
        for (int i = 1; i <= y; i++) {
          int t = b[y - i];
          if (t == x || t == x - i || t == x + i) {
            return true;
     
          }
        }
     
        return false;
      }
     
      public static void putboard() { 
        System.out.println("\n\nSoluzione " + (++s));
        for (int y = 0; y < 8; y++) {
          for (int x = 0; x < 8; x++) { // 
            System.out.print((b[y] == x) ? "|R" : "|_");
          }
          System.out.println("|");
        }
      }
     
     
     
      public static void main(String[] args) {
        int y = 0;
        b[0] = -1;
     
        while (y >= 0) {
     
        	do
        	{ b[y]++; }
     
          while ((b[y] < 8) && unsafe(y));
     
          if (b[y] < 8) 
          {
            if (y < 7) {
              b[++y] = -1;
     
            } else {
     
              putboard();
     
            }
          } else
          {y--;}//else
     
        }
     
     
      }//void main
    }//NQueens

  4. #4
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    septembre 2009
    Messages
    11 451
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2009
    Messages : 11 451
    Points : 26 892
    Points
    26 892
    Billets dans le blog
    2

    Par défaut

    Déjà, avec le code complet, on voit tout de suite le modèle :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     private static int[] b = new int[8];
      private static int s = 0;
    s sert à "compter" les solutions (parce qu'il y a plusieurs solutions au problème), surtout pour afficher un titre du genre "solution numéro #".
    b est un tableau de 8 entiers. Donc à priori, on y stocke les numéros de colonnes des dames (le problème étant de positionner 8 dames sur un échiquier (un tableau 2D 8x8) de manière à ce qu'aucune dame ne puisse prendre une autre dame. Le numéro de ligne étant la position dans le tableau.

    En gros, rapidement, vu le nom de la méthode (unsafe), sans même exécuter le programme pas à pas, le principe doit être de placer les dames dans une position de base, puis de les déplacer jusqu'à ce qu'elle soit "safe", en sécurité. Le test de comparaison de x et t, +/- i doit permettre de tester si une dame peut en prendre une autre (soit x prend t, soit t prend x). unsafe retourne true lorsque une dame est menacée par une autre.

    Décomposons le test : (t == x || t == x - i || t == x + i)
    1. si t == x, alors les deux dames sont dans la même colonne : la prise est possible. C'est la prise en colonne. (La prise en ligne est éliminée de fait par le modèle : on met une seule dame dans chaque ligne).
    2. Les deux autres conditions concernent la prise en diagonale. Pour une position de dame donnée X (sur une ligne au hasard), une autre dame située sur une ligne adjacente et en position de prise si sa colonne est à +1 ou -1 de la colonne de X. Sur une ligne séparée de 2 lignes, à +2 ou -2 de la colonne de X, puis + ou -3, etc. On voit donc qu'il y a un ligne entre le nombre de ligne de séparation entre les deux dames, et la différence entre le numéro de colonnes entre les deux. D'où ce test x==t-i et x==t+i, en faisant varier i.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2012
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2012
    Messages : 16
    Points : 17
    Points
    17

    Par défaut

    Décomposons le test : (t == x || t == x - i || t == x + i)
    1 si t == x, alors les deux dames sont dans la même colonne : la prise est possible. C'est la prise en colonne. (La prise en ligne est éliminée de fait par le modèle : on met une seule dame dans chaque ligne).
    2 Les deux autres conditions concernent la prise en diagonale. Pour une position de dame donnée X (sur une ligne au hasard), une autre dame située sur une ligne adjacente et en position de prise si sa colonne est à +1 ou -1 de la colonne de X. Sur une ligne séparée de 2 lignes, à +2 ou -2 de la colonne de X, puis + ou -3, etc. On voit donc qu'il y a un ligne entre le nombre de ligne de séparation entre les deux dames, et la différence entre le numéro de colonnes entre les deux. D'où ce test x==t-i et x==t+i, en faisant varier i.
    merci pour la réponse mais je veux quelques explications :
    je veux savoir que représentent x et t exactement
    j'arrive pas à comprendre la vérification des diagonales commment ca se fait exactement?
    comment la prise est possible quand t==x ?
    POURQUOI au début x prend ce valeur x = b[y]?

    je vous remercie du temps que vous m'avez consacré

  6. #6
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    septembre 2009
    Messages
    11 451
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2009
    Messages : 11 451
    Points : 26 892
    Points
    26 892
    Billets dans le blog
    2

    Par défaut

    Citation Envoyé par ajlif Voir le message
    POURQUOI au début x prend ce valeur x = b[y]?
    On cherche à savoir si chaque dame est menacée. Donc, à un moment donné, on va regarder si une dame en particulier est menacée.
    On fait cette boucle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    do { 
       b[y]++; 
    }
    while ((b[y] < 8) && unsafe(y));
    On y incrémente b[y], autrement dit on fait varier le numéro de colonne de la dame de la ligne y. Et on teste si elle est menacée (si elle peut être prise par une autre dame). Ceci est fait par le test et en particulier par 'unsafe' à qui on passe 'y' justement. Donc dans 'unsafe' on commence par dire : on veut tester la dame qui est en ligne y, et ce qui nous intéresse c'est sa colonne, qu'on appelle x (ce qui se traduit en java par x=b[y]).

    Citation Envoyé par ajlif Voir le message
    j'arrive pas à comprendre la vérification des diagonales commment ca se fait exactement?
    Fait un dessin :

    * * *
    * * *
    * * *
    * * * D * * * *
    * * *
    * * *
    * * *
    * *

    D est une dame de coordonnées 3,3. Dans le modèle utilisé par le programme, on aurait b[3]=3. J'ai mis des étoiles dans toutes les cases où une dame pourrait menacer notre dame D.
    Notons LD la ligne de D et CD la colonne de D : LD=3, CD=3 donc.

    Prenons la case avec l'étoile rouge, appelons-la R. Elle a pour coordonnées 4,4. Disons que LR=4, CR=4. Soit si on compare à celle de D, LD+1, CD+1,.
    Idem pour la bleu B , de coordonnées LB=5,CB=5, soit LD+2, CD+2. Et la verte, LV=6,CV=6 soit LD+3,CD+3.

    Soit en résumé :
    LR-LD=1 et CR-CD=1. ou encore LR=LD+1, CR=CD+1...
    LB-LD=2 et CB-CD=2.
    LV-LD=3 et CV-CD=3.

    On voit qu'on peut faire une boucle :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    pour i de 1 à 3 
        L[n] = LD + i
        C[n] = CD + i
     
    fin pour

    On voit donc que si on parcourt des lignes, ou des colonnes, avec un index, celui-ci ajouté à la coordonnée de notre dame à tester correspond à une position de prise en diagonale.

    Maintenant reprend ce croquis et décale D en 3, 5 par exemple (ligne 3, colonne 5, ou ligne 5, colonne 3, comme tu veux) et applique le même raisonnement en déplaçant les étoiles, en calculant les différences entre les lignes et les colonnes : tu verras que tu obtiendras la même boucle. Tu auras toujours la différence entre numéro de colonnes égale à la différence entre numéro de lignes.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 3
    Dernier message: 07/01/2018, 20h42
  2. ANt en ligne de code java
    Par oussama.elhadri dans le forum ANT
    Réponses: 0
    Dernier message: 30/12/2012, 13h54
  3. Que signifie ces lignes de codes ?
    Par Gnap69 dans le forum Débuter
    Réponses: 2
    Dernier message: 12/04/2010, 20h27
  4. Récuperation de ligne de code java ..
    Par francis.frederic dans le forum ANT
    Réponses: 3
    Dernier message: 24/06/2008, 21h59
  5. Comprendre 3 lignes de codes
    Par Djohn dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 15/01/2008, 14h38

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