Discussion :

[emna1987]

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

[anapurna]

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 x :

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

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 x :

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

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

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

[emna1987]

sur quel base j'attribue les valeurs de xmax et ymax ?

[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

[tbc92]

A mon avis, xmax, ça veut dire x.maximum, et ymax y.maximum.

[Flodelarab]

Bonjour

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à !

[anapurna]

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


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 :

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

1
2
3
4
 
  x = 1;
  y = 1;
  direction = 1;

on boucle sur la matrice carré

Code :

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

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 :

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

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

1
2
 
  FIN

[Flodelarab]

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.

[tbc92]

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 :

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

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

[wiwaxia]

Bonjour, 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

[picodev]

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

Code c :

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
#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.

[wiwaxia]

Bonjour,

Ça marche, mais j'ai perdu beaucoup de temps 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 :

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

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 :

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

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 :


@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.

[picodev]

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

[wiwaxia]

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. 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 ...
https://rosettacode.org/wiki/Categor...ming_Languages
https://rosettacode.org/wiki/Categoryascal (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.

[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.

[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 :

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

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.

[wiwaxia]

Bonjour

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 :

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

[Flodelarab]

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.

[wiwaxia]

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

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

... 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 !

[anapurna]

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 :

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

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 :

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

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 :

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

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;