Problème transformation du boulanger

Version imprimable

Bonjour
J'ai réalisé un programme qui permet d'étudier la transformation du boulanger.
le principe étant d'appliquer une transformation à une image et que après un certain nombre d'itérations on retrouve l'image d'origine. Alors qu'une image est formée de pixels je l'ai assimilée à un tableau de taille m x n, j'ai réalisé la fonction et le programme qui permet de calculer la période sauf que si je définit un tableau très grand (par exemple 100x100) ça ne fonctionne pas et le programme bloque et de même si les valeurs de m et n que j'entre ne fonctionnent pas forcément ( a vrai dire a part 2x2 ou 4x4 , 4x2 .. etc) ça ne marche pas. j'ai essayé aussi une autre méthode de calcul avec le ppcm mai sil ne marche pas.
Je vous prie alors de m'aider à résoudre ce problème.
Voici le programme main :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <conio.h>
#include "boul_int.h"
 
main()
{
      int n,m,p=0;
      int l,i,j;
      long k;
      printf("m=?\n");
      scanf("%d",&m);
      printf("n=?\n");
      scanf("%d",&n);
      k=boul_periode (n,m);
      printf("periode=%d",k);
      k=boul_ppcm(m,n);
      printf("periode=%d",k);
getch();
}

voici la bibliothèque boul_int que j'ai integré:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#include <stdio.h>
#include <string.h>
#include "pileint.h"
 
struct p_t
    {int n,p;
    };
typedef struct p_t it;
 
 
 
void B1 ( it [30][30] ,int, int, it [15][60] );
void B2 ( it [30][30] ,int ,int ,it [15][60] );
void boulanger_boul ( it [30][30] ,int ,int );
long boul_periode (int , int );
long ppcm (int , int );
long boul_ppcm (int , int );
 
void B1 ( it T[30][30], int n, int m, it U[15][60] )
{ int i,j;
     for(i=0;i<m/2;i++)
                       for(j=0;j<2*n;j++)
                                         {
                                               if(i%2==0)
                                                         if(j%2==0)
                                                                   U[i][j]=T[i][j/2];
 
                                                         else
                                                                   U[i][j]=T[i+1][(j-1)/2];
                                               else
                                                         if(j%2==0)
                                                                   U[i][j]=T[2*i][j/2];
                                                         else
                                                                   U[i][j]=T[i+2][(j-1)/2];
                                         }
}
 
 
 
 
void B2 ( it I[30][30], int n, int m, it J[15][60] )
{
     int i,j;
     for(i=0;i<m;i++)
                     for(j=0;j<n;j++)
                                     if(i<=m/2-1)
                                               I[i][j]=J[i][j];
                                     else
                                               I[i][j]=J[m-i-1][2*n-j-1];
}
 
 
void boulanger_boul ( it M[30][30], int n, int m)
{
     it V[15][60];
     B1(M,n,m,V);
     B2(M,n,m,V);
}
 
long boul_periode (int n, int m)
{
     long periode=0;
     it T[30][30];
     int i,j,k=0,p=0;
         for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               T[i][j].n=k;
                               k++;
                           }
     if((n==1)&&(m==1))
                       return(1);
     else
 
       do{
                       boulanger_boul (T,n,m);
                       p=0;
                       for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                               if (T[i][j].n!=(m*i+j))
                                  {p=1; i=m;j=n;}
 
 
                          periode ++;
 
 
                               }
 
       while ((p==1)&&(periode<9999));
     return(periode);
}
 
 
long boul_ppcm (int n, int m)
{
     pile *p;
     long periode=1;
     it T[30][30];
     int i,j,c,k=0,per=0,t=0;
     init_pile (p);
         for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               T[i][j].n=k;
                               T[i][j].p=1;
                               k++;
                           }
        while((t==0)&&(per<9999));
            {
                t=1;
                boulanger_boul(T,m,n);
                for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               if (T[i][j].n==(m*i+j))
                                {T[i][j].p=per;
                                empiler (p,per);
                                printf("la periode de T[%d][%d] est %d",i,j,per);
                                T[i][j].n=-1;
                                }
                           }
                for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               if (T[i][j].p==-1)
                               {t=0; i=m; j=n;}
                           }
                per++;
            }
             for (i=0;i<m*n;i++)
                {depiler(p,&c);
                periode= ppcm (periode,c);
                }
            return(periode);
 
}
long ppcm (int a, int b )
{
    long s;
    if (a==0 || b==0)
        return 0;
    else
       { if (a<=b)
            s=a;
        else
            s=b;
       }
    while (a%s!=0 || b%s!=0 )
        {s--;}
    s=a*b/s;
    return (s);
}

et la bibliothèque pileint qui contient des fonctions sur les piles :

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
#include <stdio.h>
#include <string.h>
typedef struct {
        char t[100];
        int sommet;
        } pile;
 
void init_pile (pile*);
int empiler (pile* , int);
int depiler (pile* ,int* );
int pile_vide (pile);
int pile_pleine (pile);
 
 
 
void init_pile (pile *p)
{
     p->sommet = (-1);
}
 
 
int empiler (pile *p, int c)
{int a;
    if (p->sommet==99)
    {printf("overflow\n");
    a=0;}
 else
 {(p->sommet)++;
 p->t[p->sommet]=c;
 a=1;}
 return(a);
}
 
 
int depiler (pile *p ,int *c)
{int a;
    if (p->sommet==-1)
    {printf("underflow");
    a=0;}
else
    {(*c)=p->t[p->sommet];
    (p->sommet)--;
    a=1;}
    return(a);
 
}
 
int pile_vide (pile p)
{if (p.sommet==1)
    return (1);
 else
 return(0);
}
 
int pile_pleine (pile p)
{if (p.sommet==99)
    return(1);
 else
     return(0);}

merci a l'avance a ceux qui essaieront de m'aider

deja corrige un peu les indentations, c'est illisbile comme ca 8O

Ensuite juste en ayant approche ce qui etait lisible :
j'espere que le fichier que tu montres comme etant boul_int n'est pas le "boul_int.h" dans l'include du main...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 long ppcm (int a, int b ) { long s; if (a==0 || b==0) return 0; else { if (a<=b) s=a; else s=b; while (a%s!=0 || b%s!=0 ) {s--;} s=a*b/s; return (s); } }

09/05/2008, 20h51
psyglobe

Citation:

j'espere que le fichier que tu montres comme etant boul_int n'est pas le "boul_int.h" dans l'include du main...

Merci beaucoup pour la première correction et pour le fichier boul_int c'est bien le fichier ".h" qui contient les fonctions que j'ai utilisé dans le main

ALORS C'EST UNE GROSSE BETISE....

On ne met pas du code dans un ".h".

On met juste la definiton des fonctions dont le code est ailleurs et/ou des structures / typedef utilises.

Exemple :

boul_int.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
#ifndef BOUL_INT_H
#define BOUL_INT_H
 
extern void B1 ( it [30][30] ,int, int, it [15][60] );
extern void B2 ( it [30][30] ,int ,int ,it [15][60] );
extern void boulanger_boul ( it [30][30] ,int ,int );
extern long boul_periode (int , int );
extern long ppcm (int , int );
extern long boul_ppcm (int , int );
 
#endif

boul_int.c

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#include <stdio.h>
#include <string.h>
#include "pileint.h"
 
struct p_t
    {int n,p;
    };
typedef struct p_t it;
 
 
 
void B1 ( it [30][30] ,int, int, it [15][60] );
void B2 ( it [30][30] ,int ,int ,it [15][60] );
void boulanger_boul ( it [30][30] ,int ,int );
long boul_periode (int , int );
long ppcm (int , int );
long boul_ppcm (int , int );
 
void B1 ( it T[30][30], int n, int m, it U[15][60] )
{ int i,j;
     for(i=0;i<m/2;i++)
                       for(j=0;j<2*n;j++)
                                         {
                                               if(i%2==0)
                                                         if(j%2==0)
                                                                   U[i][j]=T[i][j/2];
 
                                                         else
                                                                   U[i][j]=T[i+1][(j-1)/2];
                                               else
                                                         if(j%2==0)
                                                                   U[i][j]=T[2*i][j/2];
                                                         else
                                                                   U[i][j]=T[i+2][(j-1)/2];
                                         }
}
 
 
 
 
void B2 ( it I[30][30], int n, int m, it J[15][60] )
{
     int i,j;
     for(i=0;i<m;i++)
                     for(j=0;j<n;j++)
                                     if(i<=m/2-1)
                                               I[i][j]=J[i][j];
                                     else
                                               I[i][j]=J[m-i-1][2*n-j-1];
}
 
 
void boulanger_boul ( it M[30][30], int n, int m)
{
     it V[15][60];
     B1(M,n,m,V);
     B2(M,n,m,V);
}
 
long boul_periode (int n, int m)
{
     long periode=0;
     it T[30][30];
     int i,j,k=0,p=0;
         for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               T[i][j].n=k;
                               k++;
                           }
     if((n==1)&&(m==1))
                       return(1);
     else
 
       do{
                       boulanger_boul (T,n,m);
                       p=0;
                       for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                               if (T[i][j].n!=(m*i+j))
                                  {p=1; i=m;j=n;}
 
 
                          periode ++;
 
 
                               }
 
       while ((p==1)&&(periode<9999));
     return(periode);
}
 
 
long boul_ppcm (int n, int m)
{
     pile *p;
     long periode=1;
     it T[30][30];
     int i,j,c,k=0,per=0,t=0;
     init_pile (p);
         for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               T[i][j].n=k;
                               T[i][j].p=1;
                               k++;
                           }
        while((t==0)&&(per<9999));
            {
                t=1;
                boulanger_boul(T,m,n);
                for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               if (T[i][j].n==(m*i+j))
                                {T[i][j].p=per;
                                empiler (p,per);
                                printf("la periode de T[%d][%d] est %d",i,j,per);
                                T[i][j].n=-1;
                                }
                           }
                for (i=0;i<m;i++)
                           for (j=0;j<n;j++)
                           {
                               if (T[i][j].p==-1)
                               {t=0; i=m; j=n;}
                           }
                per++;
            }
             for (i=0;i<m*n;i++)
                {depiler(p,&c);
                periode= ppcm (periode,c);
                }
            return(periode);
 
}
long ppcm (int a, int b )
{
    long s;
    if (a==0 || b==0)
        return 0;
    else
       { if (a<=b)
            s=a;
        else
            s=b;
       }
    while (a%s!=0 || b%s!=0 )
        {s--;}
    s=a*b/s;
    return (s);
}

Note : maintenant je n'ai pas regarde le code en tant que tel...

09/05/2008, 22h06
psyglobe

j'ai aussi essayé de regrouper tout dans un seul fichier (fonctions et main) mais le problème persiste , il ne sert pas à grand chose vu qu'il ne sait calculer que les périodes de très peu de points. et merci pour la correction, j'avais pensé à alléger mon main mais je tacherai de ne plus commettre la même erreur .

je ne sais pas ce que tu veux faire exactement, mais il y a au moins 2 choses frappantes :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
                                               if(i%2==0)
                                                         if(j%2==0)
                                                                   U[i][j]=T[i][j/2];
 
                                                         else
                                                                   U[i][j]=T[i+1][(j-1)/2];
                                               else
                                                         if(j%2==0)
                                                                   U[i][j]=T[2*i][j/2];
                                                         else
                                                                   U[i][j]=T[i+2][(j-1)/2];

ne fait pas ce que tu penses que ca fait..

Mets des accolades pour isoler les blocs entre les if... else...

Pareil pour B2.

En gros pareil pour tous les if.. ou for...

10/05/2008, 00h37
psyglobe

je ne pense pas que le problème vienne de là parce que j'ai appliqué la fonction a un tableau connu et le résultat était correct mais je vais essayer quand même

Bonjour,

c'est sûr qu'avec cette ligne :

Code:

while ((t==0)&&(per<9999));

dans le code suivant :

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
 
    while ((t==0)&&(per<9999));
    {
        t=1;
        boulanger_boul(T,m,n);
        for (i=0;i<m;i++)
            for (j=0;j<n;j++)
            {
                if (T[i][j].n==(m*i+j))
                {
                    T[i][j].p=per;
                    empiler (p,per);
                    printf("la periode de T[%d][%d] est %d",i,j,per);
                    T[i][j].n=-1;
                }
            }
        for (i=0;i<m;i++)
            for (j=0;j<n;j++)
            {
                if (T[i][j].p==-1)
                {
                    t=0;
                    i=m;
                    j=n;
                }
            }
        per++;
    }

ne donnera pas l'effet escompté, en effet, il y a un ; après le while, ce qui, à mon avis génère une boucle infinie :roll:

De plus, voici votre code correctement indenté, avec les accolades qui vont bien...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef BOUL_INT_H
#define BOUL_INT_H
 
#include <stdio.h>
#include <string.h>
#include "pileint.h"
 
struct p_t
{
    int n,p;
};
typedef struct p_t it;
 
extern void B1 ( it [30][30] ,int, int, it [15][60] );
extern void B2 ( it [30][30] ,int ,int ,it [15][60] );
extern void boulanger_boul ( it [30][30] ,int ,int );
extern long boul_periode (int , int );
extern long ppcm (int , int );
extern long boul_ppcm (int , int );
 
#endif

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include "boul_int.h"
 
void B1 (it T[30][30], int n, int m, it U[15][60])
{
    int i,j;
    for (i=0;i<m/2;i++)
    {
        for (j=0;j<2*n;j++)
        {
            if (i%2==0)
            {
                if (j%2==0)
                    U[i][j]=T[i][j/2];
 
                else
                    U[i][j]=T[i+1][(j-1)/2];
            }
            else
            {
                if (j%2==0)
                    U[i][j]=T[2*i][j/2];
                else
                    U[i][j]=T[i+2][(j-1)/2];
            }
        }
    }
}
 
 
 
 
void B2 (it I[30][30], int n, int m, it J[15][60])
{
    int i,j;
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            if (i<=m/2-1)
                I[i][j]=J[i][j];
            else
                I[i][j]=J[m-i-1][2*n-j-1];
        }
    }
}
 
 
void boulanger_boul (it M[30][30], int n, int m)
{
    it V[15][60];
    B1(M,n,m,V);
    B2(M,n,m,V);
}
 
long boul_periode (int n, int m)
{
    long periode=0;
    it T[30][30];
    int i,j,k=0,p=0;
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            T[i][j].n=k;
            k++;
        }
    }
    if ((n==1)&&(m==1))
        return 1;
    else
    {
        do
        {
            boulanger_boul (T,n,m);
            p=0;
            for (i=0;i<m;i++)
            {
                for (j=0;j<n;j++)
                {
                    if (T[i][j].n!=(m*i+j))
                    {
                        p=1;
                        i=m;
                        j=n;
                    }
                }
            }
            periode ++;
        } while ((p==1)&&(periode<9999));
    }
    return periode;
}
 
 
long boul_ppcm (int n, int m)
{
    pile *p;
    long periode=1;
    it T[30][30];
    int i,j,c,k=0,per=0,t=0;
    init_pile (p);
 
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            T[i][j].n=k;
            T[i][j].p=1;
            k++;
        }
    }
    while ((t==0)&&(per<9999))
    {
        t=1;
        boulanger_boul(T,m,n);
        for (i=0;i<m;i++)
        {
            for (j=0;j<n;j++)
            {
                if (T[i][j].n==(m*i+j))
                {
                    T[i][j].p=per;
                    empiler (p,per);
                    printf("la periode de T[%d][%d] est %d",i,j,per);
                    T[i][j].n=-1;
                }
            }
        }
        for (i=0;i<m;i++)
        {
            for (j=0;j<n;j++)
            {
                if (T[i][j].p==-1)
                {
                    t=0;
                    i=m;
                    j=n;
                }
            }
        }
        per++;
    }
    for (i=0;i<m*n;i++)
    {
        depiler(p,&c);
        periode= ppcm (periode,c);
    }
    return periode;
 
}
long ppcm (int a, int b )
{
    long s;
    if (a==0 || b==0)
        return 0;
    else
    {
        if (a<=b)
            s=a;
        else
            s=b;
    }
    while (a%s!=0 || b%s!=0 )
    {
        s--;
    }
    s=a*b/s;
    return s;
}

Je n'est pas testé le code, juste mis en forme et supprimé une erreur (celle du while sus-mentionnée), de plus, si les prototypes sont dans le .h, elles n'ont plus lieu d'être dans le .c

++

12/05/2008, 23h07
psyglobe

Merci pour votre aide, j'ai réussi à résoudre mon problème, il venait de la fonction B1, j'avais commis une faute dans l'estimation de cette fonction et le programme marche bien à part pour les très grandes tailles.
Merci beaucoup