Lire une matrice carrée en zig-zag

Version imprimable

Voir 40 message(s) de cette discussion en une page

26/05/2016, 13h38
emna1987

1 pièce(s) jointe(s)

Lire une matrice carrée en zig-zag

bonjour,
j'ai passée toute une journée a ecrire un algorithme pour une matrice en zig-zag mais aucun resultat
svp qu'elqu'un peut me proposer comment procède pour que je démarre
Pièce jointe 210875

salut

pour commencer

tu initialise deux variable a zero appelons au hasard x et y

donc le but est au final d'arrivé au point maximal de ta matrice
xmax et ymax

tans que tu n'as pas atteint les deux valeur tu doit bouger

donc :
Code:

1 2 TansQue x <= xMax et y <= yMax Faire DEBUT
maintenant il faut définir les différents cas possible
on sait que lorsque l'on atteint les bord il va falloir changer de direction
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 SI (X = 0) Or (X = Xmax) ALORS // ON DECEND SI (Y = Ymax) ALORS // CAS OU ON ATEINT LE BAS X = X + 1 // ON SE DECALE SUR LA DROITE SINON Y = Y + 1 // ON SE DECALE VERS LE BAS FIN SI AfficherValeur(tableau(X,Y)) SINON SI (Y = 0) Or (Y = Ymax) ALORS If (X = Xmax) ALORS // CAS OU ON ATEINT LE COTE DROIT Y = Y + 1 // ON SE DECALE VERS LE BAS SINON X = X + 1 // ON SE DECALE SUR LA DROITE FIN SI AfficherValeur(tableau(X,Y)) FIN SI FIN SI
il ne te reste plus que les diagonales soit montantes soit descendantes
pour se faire c'est toujours pareil c'est les extrêmes qui vont te fournir le sens
Code:

1 2 SI (X = 0 Or Y = Ymax) ALORS croissant = FAUX FIN SI SI (Y = 0 Or X = Xmax) ALORS croissant = VRAI FIN SI
le reste est très simple je te laisse donc finir de compléter par toi même

26/05/2016, 17h21
emna1987

sur quel base j'attribue les valeurs de xmax et ymax ?
26/05/2016, 18h06
anapurna

salut

la taille de ta matrice

si tu as une matrice de 7*7
Xmax = 7 et Ymax = 7
ce n'est pas plus compliqué que cela
26/05/2016, 18h16
tbc92

A mon avis, xmax, ça veut dire x.maximum, et ymax y.maximum.
27/05/2016, 15h36
Flodelarab

Bonjour :coucou:

D'où vient ce dessin ? Moi, je ne ferais pas comme ça. Je prendrais toutes les pseudo-diagonales dans le même sens.
Et comme elles ont toutes la propriété d'avoir le même x+y, le parcours devient facile.

Soit NxN la taille de la matrice carrée.
Il faut donc faire une boucle de 2 à N+N (indiquant la diagonale que tu traites)
A l'intérieur, faire une autre boucle pour les x de 1 à N. Le y se déduit facilement.
Et tu remplis le tableau final.

Maintenant, si tu tiens tellement à ton changement de sens, il suffit de rajouter un facteur -1^indice.

Et voilà !

salut

sauf que tu ne répond pas à la question vu que tu as des flèches t'indiquant que c'est un chemin et non un remplissage de diagonal ;)
je dis ça je dis rien :D

sinon effectivement avec une boucle for de 1 à N*N il y a une solution
et pas besoin d'une boucle interne pour les x

on initialise
Code:

1 2 3 4 x = 1; y = 1; direction = 1;
on boucle sur la matrice carré
Code:

1 2 3 4 5 6 POUR element de 1 à taille*taille FAIRE DEBUT TAB[X,Y] := element; x = x + direction; y = y - direction;
il y a 4 test a faire
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 SI (x = 0) ALORS // Si x = 0 direction := -direction; x := x + 1; FIN SI; SI (X = taille +1) ALORS // si X est au max direction := -direction; x := x - 1; y := y + 2; FIN SI; SI (y = 0) ALORS // si y est a zero direction := -direction; y := y + 1; FIN SI SI (y = taille + 1) ALORS // si y est au max direction := -direction; y := y - 1; x := x + 2; FIN SI
Fin de la boucle
Code:

1 2 FIN

27/05/2016, 19h06
Flodelarab

Citation:

sauf que tu ne répond pas à la question vu que tu as des flèches t'indiquant que c'est un chemin et non un remplissage de diagonal
je dis ça je dis rien

Tu ne dis pas rien. Tu dis, au moins, une grosse bêtise.

Exemple avec une matrice 3x3:
2: 1,1
3: 2,1 puis 1,2
4: 1,3 puis 2,2 puis 3,1
5: 3,2 puis 2,3
6: 3,3

Ta solution est bien trop compliquée.

Tout ça, ça donne , sauf erreur (j'ai une chance sur 2 d'avoir mis ça dans le bon sens) :
sur une grille où les colonnes sont numérotées de 1 a N, et les lignes aussi de 1 à N

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
pour somme = 2 a 2*N
   si modulo(somme,2) = 1 alors 
      pour i = N a 1 pas -1
          j = Somme - i
          si j >= 1 et j <= N alors info( " Point suivant = lig :" + i + " col=" + j ) 
      fin
   sinon
      pour i = 1 a N
          j = Somme - i
          si j >= 1 et j <= N  alors info( " Point suivant = lig :" + i + " col=" + j ) 
      fin
   fin
fin

28/05/2016, 00h51
wiwaxia

Lire une matrice carrée en zig-zag

Bonjour, :D Je me suis gouré cette nuit en oubliant de codifier ce qui se passe à partir de la seconde diagonale, donc pour (x + y) >= x_max) ... je rectifie, donc.

Ne serait-il pas plus simple de considérer que 4 sortes de déplacements interviennent, et se succèdent d'une manière cyclique, le changement étant déclenché par les valeurs extrêmes des indices (x ou y = 0 ou Lim) ?

D1 = déplacement horizontal vers la droite: _ _ _ _ _ (x = x + 1)

D2 = descente en diagonale vers la gauche:_ _ _ _ _ (x = x - 1) et (y = y + 1)

D3 = déplacement vertical vers le bas:_ _ _ _ _ _ _ _(y = y + 1)

D4 = montée en diagonale vers la droite: _ _ _ _ _ _ (x = x + 1) et (y = y - 1)

On observe d'abord les transitions suivantes, de périodicité égale à 4:
D1 ──────────> D2 ──────────> D3 ──────────> D4 ──────────> D1 ... { pour (x + y) < Lim , en posant Lim = x_max = y_max )
--- (Si y=0) -------- (Si x=0) --------- (Si x=0) -------- (Si y=0)
le cycle s'inversant au-delà de la seconde diagonale:
D4 ──────────> D3 ──────────> D2 ──────────> D1 ──────────> D4 ... { pour (x + y) >= Lim )
--- (Si x=Lim)------ (Si x=Lim) ------ (Si y=Lim)------- (Si y=Lim)

Le nouveau déplacement serait commandé par un indice d'état vérifiant la relation de récurrence: I_k+1 = F(I_k) , avec:
si (x + y)<Lim alors si (n < 4) alors F(n) = n + 1
- - - - - - - - - - - - - - - - -sinon F(n) = 1
- - - - - - - -sinon si (n > 1) alors F(n) = n - 1
- - - - - - - - - - - - - - - - -sinon F(n) = 4

Bonjour,
une solution compacte en c qui remplit un tableau en zigzag et l'affiche :

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
#include <stdio.h>
 
void do_zigzag(size_t n, int array[n][n])
{
  int k=0;
  for(size_t i=0; i<2*n; ++i)
    for(size_t j=(i<n)?0:i-n+1; j<=i && j<n; ++j)
      if (i % 2==1)
        array[j][i-j]=k++;
      else
        array[i-j][j]=k++;
}
 
void print_array(size_t n, const int array[n][n])
{
  for(size_t i=0; i<n; ++i) {
    for(size_t j=0; j<n; ++j)
      printf("%2d ", array[i][j]);
    putchar('\n');
  }
}
 
int main(void)
{
  int test[5][5];
  do_zigzag(5,test);
  print_array(5,test);
 
  return 0;
}

Pas trop complexe et transciptible (?) facilement dans d'autres langages.

28/05/2016, 16h59
wiwaxia

2 pièce(s) jointe(s)

Lire une matrice carrée en zig-zag
Bonjour, :D

Ça marche, mais j'ai perdu beaucoup de temps :ptdr: avant de m'apercevoir que l'inversion des cycles devait intervenir au milieu de la seconde diagonale, et non vers l'une de ses extrémités. La condition évoquée dans le précédent message, et ne concernant que la somme des indices (Sxy = x + y) dans une matrice carrée d'ordre (Lim + 1):
Code:

1 2 3 4 5 TYPE Mat_B = ARRAY[0..Lim, 0..Lim] OF Byte; ... Test: Boolean; ... Test:= (Sxy<Lim)
plante l'exécution du programme au niveau de la 2^nde diagonale et doit être remplacée par une expression plus complexe:
Code:

1 2 3 4 5 Lim2 = Lim * (Lim + 2); // Lim2 = (Lim + 1)^2 - 1 ... m:= 2 * Z1; ... Test:= (Sxy<Lim) OR ((Sxy=Lim) AND (m<Lim2))
mettant en jeu le rang (z, localement Z1) de la case abordée, et sa valeur maximale (Z_max = Lim2).
De simples considérations de symétrie auraient dû me permettre de localiser plus rapidement l'erreur.

Voici le tableau obtenu dans le cas d'une matrice 12x12 :
Pièce jointe 211095

@picodev: Même en éliminant les instructions relatives aux couleurs, mon code est nettement moins compact que le tien; quand à déchiffrer ce dernier, c'est pour moi une autre paire de manches ...
C'est cependant un exercice intéressant.

@anapurna: Lier le sens de parcours des diagonales à la parité de la somme (x +y) m'a paru une bonne idée de départ; mais le temps perdu sur la correction de mon propre programme ne m'a pas permis de la tester. Comme l'expérience vient encore de le montrer, il y a parfois loin entre un projet apparemment simple et l'obtention d'un programme viable.

# Je viens de joindre le code source, pour ceux que cela pourrait intéresser. C'est un fichier de Virtual Pascal, probablement compilable en Turbo et Free P. La clarté du langage, quasiment assimilable à du pseudo-code, en facilite la traduction.
28/05/2016, 17h43
picodev

Il y a aussi la possibilité de trouver la valeur de la case (i,j) en connaissant la taille n de la matrice :

$Formule mathématique$
29/05/2016, 18h34
wiwaxia

Lire une matrice carrée en zig-zag

Bonjour,

Merci pour l'info; la formule est impressionnante, mais laisse deviner certaines propriétés de la matrice et de la transformation:
# les termes en (-1)^i+j sont liés à l'inversion spécifique des rangées de longueur impaire, comme l'avait déjà remarqué un intervenant;
# l'existence d'une relation complémentaire ZZ(n, i, j) = N² -1 - ZZ(n, n - 1 - i, n - 1 - j) provient de ce que les valeurs des cases successives (c.a.d. leur rang) forment une suite arithmétique;
# les indices ne peuvent être égaux à l'ordre (n), et l'indexation s'étend donc de (0) à (n - 1), et celle des cases de ZZ(n, 0, 0) = 0 à ZZ(n, n - 1, n - 1) = n² - 1 .
Ça tombe bien, parce que j'avais justement pris ces conventions dans le programme précédent. :mrgreen: Point de vue égoïste, je le reconnais.
Pourrais-tu m'indiquer d'où tu tiens ce résultat (livre ou site web) ? A moins évidemment que tu ne l'aies établi toi-même ...

Je me suis comme les autres efforcé de trouver un algorithme "nomade" décrivant le parcours effectué d'une case à l'autre; et c'était bien là, il me semble, l'esprit de la question posée (quoique très brièvement exprimée).
Mais un autre procédé plus rapide pourrait être envisagé, en deux étapes:
a) remplissage de la matrice par les entiers naturels successifs de [0 ; n²-1] à partir du coin supérieur gauche (a_0,0), en suivant dans le sens toujours descendant les rangées consécutives parallèles à la seconde diagonale;
b) transposition des mêmes rangées d'ordre impair > 2 (pour les coins extrêmes, c'est inutile).

Cette dernière transformation est involutive, puisque son renouvellement conduit à la matrice d'origine. Ce procédé constitue cependant une tricherie, dans la mesure où l'obtention de la matrice transformée ne passe plus par le parcours imposé. A voir cependant ...

Un recherche sur le web, un peu décevante (très peu de références en français) montre cependant qu'il ne s'agit pas d'un simple sujet d'école; beaucoup d'articles concernent le traitement des images; encore faut-il choisir les bon termes:

# Zig-zag ordering: _ _ _ _ _ _ _ _ _ _ _ _ http://www.pcs-ip.eu/index.php/main/edu/7
# Zig-Zag Scanning Patterns: _ _ _ _ _ _ _ http://www.bretl.com/mpeghtml/zigzag.HTM
# Zig-Zag scan _ _ _ _ _ _ _ _ _ _ _ _ _ _ http://www.mathworks.com/matlabcentr...ntent/zigzag.m
# Séquence zig-zag: _ _ _ _ _ _ _ _ _ _ _ _http://home.nordnet.fr/~jpbaey/tipe/compression_jpeg/codage_de_la_matrice_dct_quantif.htm
# run-length encoding (RLE) algorithm _ _ _ https://en.wikipedia.org/wiki/JPEG

Le résultat le plus surprenant concerne le site rosetta.org
# Zig-zag matrix _ _ _ _ _ _ _ _ _ _ _ _ _ _ https://rosettacode.org/wiki/Zig-zag_matrix
sur lequel on l'algorithme en question proposé en 83 langages!
https://rosettacode.org/wiki/Zig-zag_matrix#Pascal
https://rosettacode.org/wiki/Zig-zag_matrix#C

On y trouve d'ailleurs bien d'autres programmes, proposé en plusieurs centaines de langages (394 en Pascal, et 775 en C) ... de quoi s'occuper jusqu'en maison de retraite, et même après ... :aie:
https://rosettacode.org/wiki/Categor...ming_Languages
https://rosettacode.org/wiki/Category:Pascal (là, c'est un bug du traitement de texte)
https://rosettacode.org/wiki/Category:C

Sur un sujet apparenté (simplement aperçu):
Spiral matrix https://rosettacode.org/wiki/Spiral_matrix

Mais peut-être que beaucoup de programmeurs connaissent déjà ces liens.
29/05/2016, 19h01
picodev

Pour débusquer la formule je suis parti de ce premier constat : quelle que soit la taille n des matrices le triangle supérieur (diagonale incluse) est toujours le même. Ensuite on remarque que le triangle inférieur est quasi symétrique en miroir sauf qu'on démarre à n²-1, ici on en déduit facilement la seconde partie de la formule, du moins on peut s'en convaincre assez aisément.
Comme on parcourt la matrice en diagonale la formule devait refléter un comportement à i+j constant.
En regardant les plus grands nombre de chaque diagonale on trouve la suite 0,2=0+2,5=2+3,9=5+4 → n(n+3)/2, formule qui donne le nombre en première ligne pour les colonnes paires soit quand (i+j) est pair. En regardant les plus petits nombres de chaque diagonale on trouve 0,1=0+1,3=1+2,6=3+3,10=6+4 → n(n+1)/2 qui donne le nombre en première ligne pour les colonnes impaires, soit quand (i+j) est impair. Du coup on trouve pas trop difficilement la formule pour la première ligne : A[0,n]=n(n+2+(-1)^n)/2.
Sur la diagonale on simplement A[i,j]=A[0,i+j] + i quand i+j est impair, et A[i,j]=A[0,i+j] - i quand i+j est pair. Ce que je résume par un A[i,j]=A[0,i+j] - (-1)^(i+j)×i.

J'espère ne pas avoir été trop confus dans mon explication.
30/05/2016, 00h37
wiwaxia
Ton argumentation paraît pertinente, et très claire; il faut bien sûr, dans ce genre de texte, tout reprendre d'une manière détaillée stylo en main.
Merci en tous cas pour cette réponse précise et rapide.
J'ai d'ailleurs l'impression - c'est peut-être illusoire mais pas aussi étonnant que cela - que le nouvel algorithme précédemment décrit suit d'assez près l'établissement de ta formule; et il se pourrait bien que l'on parvienne, une fois poussé suffisamment loin l'étude théorique, à un programme se réduisant pour l'essentiel à
Code:

1 2 3 FOR i:= 0 TO Lim DO FOR j:= 0 TO Lim DO Mat[i, j]:= F(n, i, j]
Pour l'instant,je n'ai fait que lire rapidement les programmes Zig-zag matrix disponibles sur rosetta.org; la brièveté de celui rédigé en C me paraît toujours sidérante.

1 pièce(s) jointe(s)

Lire une matrice carrée en zig-zag

Bonjour :D

Je viens de trouver un version plus simple pour l'algorithme de parcours de la matrice; il suffit de suivre les rangées successives parallèles à la seconde diagonale, le sens de parcours dépendant de la parité de la somme des indices (s = i + j) .
Ceux-ci appartiennent au domaine [0 ; Lim], et les bornes du balayage sont évidentes.

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
 
   CONST Lim = 19; Lim2 = 2 * Lim;
   TYPE Mat_B = ARRAY[0..Lim, 0..Lim] OF Word;
   ...
   Entete; m:= 0;
   FOR Sxy:= 0 TO Lim DO
     IF Odd(Sxy) THEN FOR i:= 0 TO Sxy DO BEGIN
                                            Inc(m); j:= Sxy - i;
                                            Mat[i, j]:= m
                                          END
                 ELSE FOR j:= 0 TO Sxy DO BEGIN
                                            IF Sxy>0 THEN Inc(m);
                                            i:= Sxy - j;
                                            Mat[i, j]:= m
                                          END;
   FOR Sxy:= (Lim+1) TO Lim2 DO
     IF Odd(Sxy) THEN FOR i:= (Sxy - Lim) TO Lim DO BEGIN
                                                      Inc(m); j:= Sxy - i;
                                                      Mat[i, j]:= m
                                                    END
                 ELSE FOR j:= (Sxy - Lim) TO Lim DO BEGIN
                                                      Inc(m); i:= Sxy - j;
                                                      Mat[i, j]:= m
                                                    END;
   AffM; O

Pièce jointe 211230

30/05/2016, 15h22
Flodelarab

Citation:

Je viens de trouver un version plus simple pour l'algorithme de parcours de la matrice; il suffit de suivre les rangées successives parallèles à la seconde diagonale, le sens de parcours dépendant de la parité de la somme des indices (s = i + j) .

Bravo. C'est ce que j'ai dit dès mon premier message pour lequel j'ai reçu un joli pouce baissé.

Toutes vos solutions ont des conditions. Alors qu'aucune condition n'est nécessaire. :roll:
30/05/2016, 16h26
wiwaxia

Lire une matrice carrée en zig-zag

Citation:

Envoyé par Flodelarab

... C'est ce que j'ai dit dès mon premier message ...

A ceci près qu'interviennent deux dichotomies: Sxy < ou > Lim_(diagonale) et (Sxy MOD 2) = 0 ou 1
qui conduisent à 4 sortes de doubles boucles imbriquées.

Citation:

... pour lequel j'ai reçu un joli pouce baissé ...

Ce n'est pas moi, juré; je le réserve aux trolls - au fait, a-t-on des nouvelles de FleurEnPlastique ?

Citation:

... Toutes vos solutions ont des conditions. Alors qu'aucune condition n'est nécessaire ...

Là, je veux bien connaître ton programme, et le voir fonctionner ...

Moi, je pense avoir une solution de ce genre: l'algorithme char d'assaut utilisant la formule établie par Picodev (voir l'un des messages précédents). Je songe d'ailleurs à l'écrire, pour vérification.

Nous en sommes déjà à 3 programmes mis au point, plus 2 autres (écrite de même en Pascal et en C) disponibles sur rosetta.org - sans compter les 81 autres versions présentes sur le même site ... Il va falloir bientôt créer une section "Matrices Zig-zag".

Au moins l'auteur du sujet (emna1987) ne pourra pas se plaindre que sa demande soit restée sans réponse ! :mrgreen:

salut

Etant curieux j'ai programmé la fonction defini plus haut
la fonction donne bien les éléments voulu sauf que le parcours de la matrice n'est pas correct
puisqu'il est parcouru ligne à ligne

voici les codes utile pour les curieux ^^
Code:

1 2 3 4 5 6 7 8 Function zz(n,i,j : Integer) :Integer; begin if (i+j) < n Then Result := Round(((i+j)*(i+j+2+Power(-1,i+j))/2)-(power(-1,i+j)*i)) else Result := Round(Power(n,2)-1-zz(Round(power(n,2)),n-1-i,n-1-j)); end;
en l'utilisant comme ceci pour remplir la matrice
Code:

1 2 3 4 For i:= 0 to nb do For j:= 0 to nb do Cells[j,i] := Inttostr(zz(nb*2,i,j));
pour obtenir les couleur de sa grille
Code:

1 2 3 4 5 6 7 8 If Arow = (Nb-acol) Then Result := clred else if odd(Arow+acol) Then Result := clGreen else Result := clGrayText;

Voir 40 message(s) de cette discussion en une page