Algorithme pour Baguenaudier

Version imprimable

03/04/2017, 15h10
Rumpel

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.
07/04/2017, 10h56
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.

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:

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

11/04/2017, 14h22
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.
15/04/2017, 00h23
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:

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

Citation:

Envoyé par Rumpel

Code:

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.