algorithme recursif pour remplir un carré en diagonal

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:

---

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

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é ?

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:

---

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

---

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:

---

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

---

:tagcode:

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

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:

---

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)

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:

---

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

---

Code:

---

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 ??

Code:

---

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 ??

Bonjour,

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

Code:

---

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)

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

Code:

---

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

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:

---

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:

---

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

---

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

Code:

---

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 } } }

---

quelqu'un a trouvé + court??

Salut !

Plus court non ... mais plus long oui !

J'ai essayé ceci :

Code:

---

1 2 3 4 5

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

---

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

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 !

Bonjour,

Citation:

---

Envoyé par Nemerle

Code:

---

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:

---

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

Citation:

---

Envoyé par rostomus

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

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

Citation:

---

x=1
y=x

---

en fait, il faut inverser:

Code:

---

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:

---

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 } } }

---

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:

---

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 !

Citation:

---

Envoyé par rostomus

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

Code:

---

1 2

y=x x=1

---

---

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