1. #1
    Membre du Club
    Profil pro
    Inscrit en
    novembre 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2008
    Messages : 61
    Points : 57
    Points
    57

    Par défaut Algorithme pour Baguenaudier

    Bonjour,

    Je suis en train d'essayer de résoudre ce problème :

    Malgré plusieurs tests, mon programme plante au 16è test pour cause de mémoire insuffisante.

    Ma question est de savoir comment mesurer la mémoire que mon programme utilise ? (en Java)

    Et si vous avez une solution pour satisfaire aux contraintes mémoire. (Pourtant mon algo n'est pas récursif)

    Merci à vous.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 354
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 354
    Points : 2 878
    Points
    2 878

    Par défaut

    Ta question 'comment connaitre la mémoire dispo en Java' est une question de SYNTAXE sur le LANGAGE JAVA.
    Pose cette question dans un forum JAVA.

    Pour ta 2ème question, pourquoi ton algorithme explose en mémoire ? Il faudrait que tu nous montres l'algorithme.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    novembre 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2008
    Messages : 61
    Points : 57
    Points
    57

    Par défaut

    Bonjour,

    A mon avis c'est plus un problème d'algorithmie que de syntaxe java, je n'ai pas voulu multiplié les posts, mais je demanderais éventuellement.
    (C'est bien la première fois de ma vie ou j'ai un dépassement de mémoire pour faire un programme )

    Code java : 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
     
     
    import algorea.Scanner;
    class Main
    {
       static Scanner entree = new Scanner(System.in);
     
       static int nbIterations(int n)
       {
          int result = (int) Math.pow(2,n+1);
          if ( n % 2 == 0 ) result -= 2;
          else result -= 1;
          result = (int) result / 3;
          return result;
       }
     
        static boolean paire(int n)
        {
          return (n % 2 == 0);
        }
     
        static int lastOne(byte[] bague)
        {
          int n = bague.length;
          for (int i=n-1; i>=0; i--)
             if ( bague[i] == 1 )
                return i;
          return 0;
        }
     
       public static void main(String[] args)
       {
     
            // Lecture première ligne
            int n = entree.nextInt();
     
            int nbIterations = nbIterations(n);
            boolean paire = paire(n);
     
            // Initialisation bague = 1 1 1 1 1
            byte[] bague = new byte[n];
            for (int i=0; i<n; i++)
             bague[i] = 1;
            //System.out.println( paire );
            //System.out.println( bague[0] + " " + bague[1] + " " + bague[2] + " " + bague[3] );
            nbIterations = nbIterations/2;
            if ( !paire )
            {
               System.out.println( 1 );
     
               if ( bague[n-1] == 1)
                   bague[n-1] = 0;
                else
                   bague[n-1] = 1;
                //paire = false;
            }
     
            for (int iter = 0; iter <nbIterations; iter++ )
            {
                // pair
                int lastOne = n;
                do
                {
                   lastOne--;
                } while (bague[lastOne]==0);
     
                   System.out.println( n-lastOne+1 );
                   if ( bague[ lastOne-1 ] == 1)
                      bague[ lastOne-1 ] = 0;
                   else
                      bague[ lastOne-1 ] = 1;
                   // impair
                   System.out.println( 1 );
     
                   if ( bague[n-1] == 1)
                      bague[n-1] = 0;
                   else
                      bague[n-1] = 1;
                   //paire = false;
               //}
            //System.out.println( bague[0] + " " + bague[1] + " " + bague[2] + " " + bague[3] );
            }
       }       
     
     
    }

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 354
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 354
    Points : 2 878
    Points
    2 878

    Par défaut

    J'essaye de comprendre ton algorithme, mais je n'y arrive pas.
    Tu commences par calculer nbiterations, en utilisant une formule venue d'où ? Bizarre.

    Ensuite, je m'attendrais à voir un truc qui mémorise plusieurs scénarios, plusieurs options : Au mouvement n°n, partant de telle situation, j'ai plusieurs mouvements possibles, disons k mouvements possibles. Je vais donc supprimer le scénario actuel de mon catalogue, et insérer k nouveaux scénarios. Je ne vois rien qui ressemble à ça dans ton algo.

    Détail : tu as une fonction lastone() qui n'est pas utilisée.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    novembre 2008
    Messages
    61
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2008
    Messages : 61
    Points : 57
    Points
    57

    Par défaut

    Hello,

    Merci déjà d'avoir regardé.

    Alors le nombre d'itération pour résoudre le baguenaudier, c'est ( 2^(n+1) - 1 )/3 ou ( 2^(n+1) - 2 )/3 selon la parité.
    Ca se démontre surement par récurrence, j'ai pris la formule sur le wiki et elle est juste.

    Oui lastOne() ne sert plus à rien, j'ai le bout de code

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
                int lastOne = n;
                do
                {
                   lastOne--;
                } while (bague[lastOne]==0);
    qui fait exactement la même chose. J'ai essayé de minimiser les appels aux fonctions pour ne pas consommer de la mémoire.
    Non seulement mon code est devenu moins lisible, mais j'ai toujours des problèmes de mémoire.

    En fait c'est un peu comme les tours de Hanoï, c'est un faux problème, il n'y a qu'un seul scénario qui permet d'arriver à la résolution du problème en temps minimal.

    Pour la structure de données, c'est assez facile 1 => rempli 0 => vide

  6. #6
    Membre à l'essai
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 22
    Points : 23
    Points
    23

    Par défaut

    Citation Envoyé par Rumpel Voir le message
    Bonjour,

    A mon avis c'est plus un problème d'algorithmie que de syntaxe java, je n'ai pas voulu multiplié les posts, mais je demanderais éventuellement.
    (C'est bien la première fois de ma vie ou j'ai un dépassement de mémoire pour faire un programme )

    Code java : 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
     
     
    import algorea.Scanner;
    class Main
    {
       static Scanner entree = new Scanner(System.in);
     
       static int nbIterations(int n)
       {
          int result = (int) Math.pow(2,n+1);
          if ( n % 2 == 0 ) result -= 2;
          else result -= 1;
          result = (int) result / 3;
          return result;
       }
     
        static boolean paire(int n)
        {
          return (n % 2 == 0);
        }
     
        static int lastOne(byte[] bague)
        {
          int n = bague.length;
          for (int i=n-1; i>=0; i--)
             if ( bague[i] == 1 )
                return i;
          return 0;
        }
     
       public static void main(String[] args)
       {
     
            // Lecture première ligne
            int n = entree.nextInt();
     
            int nbIterations = nbIterations(n);
            boolean paire = paire(n);
     
            // Initialisation bague = 1 1 1 1 1
            byte[] bague = new byte[n];
            for (int i=0; i<n; i++)
             bague[i] = 1;
            //System.out.println( paire );
            //System.out.println( bague[0] + " " + bague[1] + " " + bague[2] + " " + bague[3] );
            nbIterations = nbIterations/2;
            if ( !paire )
            {
               System.out.println( 1 );
     
               if ( bague[n-1] == 1)
                   bague[n-1] = 0;
                else
                   bague[n-1] = 1;
                //paire = false;
            }
     
            for (int iter = 0; iter <nbIterations; iter++ )
            {
                // pair
                int lastOne = n;
                do
                {
                   lastOne--;
                } while (bague[lastOne]==0);
     
                   System.out.println( n-lastOne+1 );
                   if ( bague[ lastOne-1 ] == 1)
                      bague[ lastOne-1 ] = 0;
                   else
                      bague[ lastOne-1 ] = 1;
                   // impair
                   System.out.println( 1 );
     
                   if ( bague[n-1] == 1)
                      bague[n-1] = 0;
                   else
                      bague[n-1] = 1;
                   //paire = false;
               //}
            //System.out.println( bague[0] + " " + bague[1] + " " + bague[2] + " " + bague[3] );
            }
       }       
     
     
    }
    Pourrais-tu le faire en pseudo-code, j'ai du mal avec Java
    Merci.

Discussions similaires

  1. algorithme pour arbre
    Par d-a-v-e dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 06/02/2006, 21h16
  2. algorithme pour calcul de probabilité
    Par filsdugrand dans le forum Général Algorithmique
    Réponses: 9
    Dernier message: 14/12/2005, 14h11
  3. Quel algorithme pour insertion d'objets "triés" da
    Par phplive dans le forum Langage
    Réponses: 3
    Dernier message: 04/08/2005, 09h27
  4. Algorithme pour trier trois nombres
    Par legosam dans le forum Général Algorithmique
    Réponses: 9
    Dernier message: 17/01/2005, 21h47
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 10h47

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