Discussion :

[Rumpel]

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.

[tbc92]

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.

[Rumpel]

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] );
        }
   }       
 
 
}

[tbc92]

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.

[Rumpel]

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

[valentin03]

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.