Discussion :

[chelsea23]

bonjour alors je fais appele a vous pour un coup de main au niveau du
probléme
du remplissage d'un carré recursivement voila une partie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure trace(x, y, x_droite, y_bas, total_posees: integer);
begin
  tab[x, y] := '$';
  afficher_tableau;
  if (x >= dim) and (y >= dim) then exit; // point d'arrêt
  if y = 1 then
  begin
    if x >= dim then inc(x_droite); // effet de bord
    x := x_droite;
    y := y_bas + 1;
    if y > dim then dec(y); // effet de bord
    y_bas := y;
    if total_posees < dim * dim then // carré rempli ?
      trace(x, y, x_droite, y_bas, total_posees + 1);

l'instruction que je n'ai pas compris if x>=dim then
inc(x_droite);effet de bord
est ce que ça veut dire que qu'on depasse la taille de la dim on revien
a la
premiére case EN ICRéMENTANT??? ET POUR total_poseees lui on affecté
une
valeur pour la tester???
VOILA AISEZ MOI SVP

[millie]

Bonjour à toi.

Ce serait sympathique d'éditer ton post pour :
- éviter le langage SMS
- utiliser la balise CODE
- un peu mieux mettre en page ton post car c'est limite lisible.
- expliquer ce que tu entends par : remplissage d'un carré et comment modélises tu un carré ?

[chelsea23]

voila tout le probléme
Supposons qu'on a un carré de 10x10 cases, et qu'on veut noircir toutes ses cases; le remplissage ne s'effectuera pas en ligne ou en colonne mais en diagonale, de gauche à droite et du bas vers le haut.


Pour cela, si à un instant t on se trouve à la case de coordonnées (x,y), alors la prochaine case à noircir sera la case de coordonnées (x+1,y-1).


Il faut prendre soin de tester les effets de bord (ne pas sortir du carré à force de décrémenter x ou d'incrémenter y).


On en déduit donc que le point d'arrêt de la procédure est atteint quand les coordonnées x ou y se retrouvent en dehors du carré.


On sait ensuite que lorsqu'on aura atteint la première ligne (y=1), alors il faut redémarrer le remplissage à la première colonne.

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
procedure trace(x, y, x_droite, y_bas, total_posees: integer);
begin
  tab[x, y] := '$';
  afficher_tableau;
  if (x >= dim) and (y >= dim) then exit; // point d'arrêt
  if y = 1 then
  begin
    if x >= dim then inc(x_droite); // effet de bord
    x := x_droite;
    y := y_bas + 1;
    if y > dim then dec(y); // effet de bord
    y_bas := y;
    if total_posees < dim * dim then // carré rempli ?
      trace(x, y, x_droite, y_bas, total_posees + 1);
  end
  else
    if x >= dim then
    begin
      if y_bas = dim then inc(x_droite); // effet de bord
      x := x_droite; y := y_bas;
      if total_posees < dim * dim then // carré rempli ?
        trace(x, y, x_droite, y_bas, total_posees + 1);
    end
    else
      if total_posees < dim * dim then // carré rempli ?
        trace(x + 1, y - 1, x_droite, y_bas, total_posees + 1);

[millie]

Il n'y a pas besoin de recursivité pour ce problème.

Par exemple, voici un début de réponse (qui est finalement une réponse complète) :

Notation : rect[i][j], i correspond à la ligne i et j à la colonne j et rect[1][1] correspond à la case supérieur gauche.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Procédure rempli(Rectangle:rect)
 hauteur <- hauteur(rect);
 largeur <- largeur(rect);
 
 /*rempli la partie inférieur gauche*/
 De i=hauteur à 1
   De j=i à largeur
     rect[j][j-i+1] <- Noir
 
 /*rempli la partie supérieur droite*/
 De i=largeur à 2
   De j=i à hauteur
     rect[j][j-i+1] <- Noir

[chelsea23]

on peut pas le faire recursivement
en prenant le point d'appui uqand on dépasse la dimension du tableau

[khayyam90]

bien le bonsoir,

ton algo récursif n'est pas forcément le plus simple.
si tu tiens absolument à remplir un carré récursivement, on peut faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
trace(entiers x,y){
   // on vérifie qu'on est toujours dans le tableau 
   // et qu'on n'est pas sur une case déjà noircie
   if (x>dim) ou (y < 1) ou (tableau[x][y] = '$')
      return ; // on ne fait rien et on quitte la fonction
 
   else{
      // on remplit et on récursive
      tableau[x][y] = '$';
      trace(x,y-1)
      trace(x+1,y)
   }
}

et il suffira d'appeler trace(1,10)

[rostomus]

Bonjour,

Si votre tableau est un carré, ca veut dire que largeur =hauteur, et ca sera plus simple a le faire. Voila une proposition:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
for i=1 to dim
    for j=1 to i
        tab(i-j+1,j)='$';
    end
end
  for i=1 to dim-1
      for j=1 to dim-i
          tab(dim-j+1,j+i)='$';
      end
  end

[chelsea23]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for i=1 to dim
    for j=1 to i
        tab(i-j+1,j)='$';
    end
end
  for i=1 to dim-1
      for j=1 to dim-i
          tab(dim-j+1,j+i)='$';
      end
  end

bon la premiére boucle nous permet de remplire la premiére colonne
et la 2ém boucle je l'ai pas trés bien compris elle permet de remplire en diagonal ??

[chelsea23]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for i=1 to dim
    for j=1 to i
        tab(i-j+1,j)='$';
    end
end
  for i=1 to dim-1
      for j=1 to dim-i
          tab(dim-j+1,j+i)='$';
      end
  end

bon la premiére boucle nous permet de remplire la premiére colonne
et la 2ém boucle je l'ai pas trés bien compris elle permet de remplire en diagonal ??

[rostomus]

Bonjour,

Je dois d'abord verifier si j'ai bien compri ce que vous voulez faire: soit un tableau de 3*3, donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
0 0 0   $ 0 0   $ 0 0   $ $ 0   $ $ 0   $ $ 0   $ $ $   $ $ $   $ $ $   $ $ $
0 0 0   0 0 0   $ 0 0   $ 0 0   $ 0 0   $ $ 0   $ $ 0   $ $ 0   $ $ $   $ $ $
0 0 0   0 0 0   0 0 0   0 0 0   $ 0 0   $ 0 0   $ 0 0   $ $ 0   $ $ 0   $ $ $

si c'est juste, le programme fait exactement ca. seulement je dois mentionner que tab(i,j) ==> i : ligne et j: colonne
mes deux premieres boucles imbriqué font le remplissage du premier triangle en gauche superieur. et les deux dernieres font le reste (triangle droite inferieur)

[chelsea23]

merci!oui c'est ce que je veux mais avec la récursivité alors j'ai pu implémenté la 1er boucle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 procedure carré(var i,dim:integer);
     begin
   if i<=dim then
         for j=1 to dim do
   t[i,j]:=$;
   carré(i+1,dim-1);

mais mon code n'est pas términé car j'ai pas pu remplir le 2em triangle(droit) récursivement biensure!
vous n'avez une idée

[Sivrît]

C'est pas vraiment récursif par nature comme problème. Cet ordre de remplissage suppose de remplir des diagonales de plus en plus grandes puis de plus en plus petites donc pas facile à traiter tout pareil. Par rapport à des boucles ça risque d'ajouter des calculs et de donner un résultat sous-optimal.

Je vois ça plutôt avec deux fonctions (ou alors un booléen en paramètre et/ou un test en plus mais c'est moche).
Première idée :

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
 
procedure carré(var i, dim : integer);
begin
   for j=1 to i do
      t[i-j+1, j]:=$;
 
   if i<dim then
      carré(i+1, dim);
   else carré_bis(dim-1, dim);
end
 
procedure carré_bis(var i, dim:integer);
begin
   if i>0 then
      for j=dim down to dim-i+1 do
         t[j, 2*dim-j-i+1]:=$;
 
      carré_bis(i-1, dim);
end

Dans la deuxième fonction remplacer "i" par "dim-i" pourrait simplifier mais j'ai voulu conserver le fait que l'on remplisse des diagonales de taille i.

Autre idée qui me plait plus :

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
 
procedure carré(var x, y, dim : integer);
begin
   if y=1 then
      diagonale(x, y, dim);
      if x=dim then
         carré(x, 2, dim);
      else carré(x+1, y, dim);
   else if y<=dim then
      diagonale(x, y, dim);
      carré(x, y+1, dim);
end
 
procedure diagonale(var x, y, dim : integer);
begin
   if x>=1 and y<=dim then
      t[x, y]:=$;
      carré_bis(x-1, y+1, dim);
end

[Nemerle]

directement, n étant la taille du carré, les éléments étant t[i][j] ou i,j parcourt 1,...,n:

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
x=1
y=1
pour i=1 à n*n{
   t[x][y]= $
   x=x-1
   y=y+1
   si(x=n+1){
      x=y+1
      y=n
   sinon{
      si(y=0){
         x=1
         y=x
      }
   }
}

[Nemerle]

quelqu'un a trouvé + court??

[henderson]

Salut !

Plus court non ... mais plus long oui !

J'ai essayé ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
#define dim 10
int x = 5;
int y = 2;
int s = 1;
int Carre[dim][dim];

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
for(int j = 0; j < (dim * dim); j++)
    {
    Carre[x][y] = 1;
    //Fin du premier triangle ?
    if((x == (dim-1)) && (y == 0))
        {
        x = 0; y = dim-1; //il semblerait donc remplir le deuxième
        }
    else
        {
        y = y + s;
        x = x + s;
        if(s == 1)
            {
            if(y == dim)
                {
                s = -1;
                y = dim-1;
                if(x == dim)
                    {
                    x = dim-1;
                    y = dim-2;
                    }
                }
            else
                {
                if(x == dim)
                    {
                    s = -1;
                    x = dim-1;
                    y = y-2;
                    }
                }
            }
        else
            {
            if(y < 0)
                {
                s = 1;
                y = 0;
                if(x < 0)
                    {
                    x = 1;
                    }
                else
                    {
                    x = x + 2;
                    }
                }
            else
                {
                if(x < 0)
                    {
                    s = 1;
                    x = 0;
                    }
                }
            }
        }
    }

Ca semble un peu poussif, mais ça fonctionne selon le mode de remplissage que je me suis fixé, à savoir un remplissage dont le sens alterne à chaque fois que l'on rencontre un bord.
Est-ce que ça peut se simplifier ?

A plus !

[rostomus]

Bonjour,

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
x=1
y=1
pour i=1 à n*n{
   t[x][y]= $
   x=x-1
   y=y+1
   si(x=n+1){
      x=y+1
      y=n
   sinon{
      si(y=0){
         x=1
         y=x
      }
   }
}

Je pense qu'il y a une erreur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
instruction        | x     |    y
x=1                    1    |
y=1                    1    |    1
x=x-1                  0    |    1
y=y+1                  0   |     2
si x=n+1                                   non ==> sinon
si y=0                                      non ==> pour i=......                       
x=x-1                  -1   |   2  ??
y=y+1                  -1   |   3  ??

vous voiez que x n'atteint jamais n+1 et y n'attent jamais 0

[Nemerle]

Bonjour,

Je pense qu'il y a une erreur

T'as raison, j'ai interverti les x et les y aux incréments/décréments!!

x=1
y=1
pour i=1 à n*n{
t[x][y]= $
y=y-1
x=x+1
si(x=n+1){
x=y+1
y=n
sinon{
si(y=0){
x=1
y=x
}
}
}

Sorry pour l'erreur

[rostomus]

Bonjour,
Je pense qu'il y a une autre erreur de frappe :

x=1
y=x

en fait, il faut inverser:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
y=x
x=1

2) lorsqu'on remplit la case t[n-1][1], donc on a aprés:
x=x+1 ==> x=n
y=y-1 ==> y=0
si (x=n+1) :non ==> si (y=0): oui ==> :
y=x ==> y=n
x=1 ==> x=1 donc on est sur la diagonale ..... aprés n-1 iterations (diagonale remplie) x=n et y=1:
x=x+1 ==> x=n+1
y=y-1 ==> y=0
si (x=n+1): oui ==>:
x=y+1 ==> x=1
y=n ==> y=n donc on est à nouveau sur la diagonale, et donc on sort pas de diagonale jusqu'à que i soit egal à n*n.
solution: il faut sauter à x=2 et y=n, donc x atteint n+1 lorsque y est a 1 et apres x=3 et y=n donc il faut remplacer x=y+1 par x=y+2.
donc:

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
 
x=1
y=1
pour i=1 à n*n{
     t[x][y]= $
     y=y-1
     x=x+1
     si(x=n+1){
            x=y+2
            y=n
      sinon{
            si(y=0){
                  y=x
                  x=1
             }
      }
}

[henderson]

Salut !

Sinon, il y a plus simple si on a le droit de préparer un tableau de 19 points représentant les coordonnées du premier point pour chaque diagonale.
En considérant que N représente l'index d'un point valide dans ce tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for(int j = 0; j < 19; j++)
    {
    P = Points[N];
    do{
        Carre[P.x][P.y]...
        P.x++;
        P.y++;
        }while((P.x < dim) && (P.y < dim));
    N = (N+1) % 19;
    }

A plus !

[Nemerle]

Bonjour,
Je pense qu'il y a une autre erreur de frappe :
en fait, il faut inverser:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
y=x
x=1

T'as raison! Comme quoi, taper un algo à la va-vite, c'est pas bien