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
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
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 :
maintenant il faut définir les différents cas possible
Code x : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 TansQue x <= xMax et y <= yMax Faire DEBUT
on sait que lorsque l'on atteint les bord il va falloir changer de direction
il ne te reste plus que les diagonales soit montantes soit descendantes
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
pour se faire c'est toujours pareil c'est les extrêmes qui vont te fournir le sens
le reste est très simple je te laisse donc finir de compléter par toi même
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
Blaise PascalNous souhaitons la vérité et nous trouvons qu'incertitude. [...]
Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
PS : n'oubliez pas le tag
sur quel base j'attribue les valeurs de xmax et ymax ?
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
Blaise PascalNous souhaitons la vérité et nous trouvons qu'incertitude. [...]
Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
PS : n'oubliez pas le tag
A mon avis, xmax, ça veut dire x.maximum, et ymax y.maximum.
N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.
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 -1indice.
Et voilà !
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
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
on boucle sur la matrice carré
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 x = 1; y = 1; direction = 1;
il y a 4 test a faire
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;
Fin de la boucle
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
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2FIN
Blaise PascalNous souhaitons la vérité et nous trouvons qu'incertitude. [...]
Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
PS : n'oubliez pas le tag
Tu ne dis pas rien. Tu dis, au moins, une grosse bêtise.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
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.
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
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
N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.
Bonjour, Je me suis gouré cette nuit en oubliant de codifier ce qui se passe à partir de la seconde diagonale, donc pour (x + y) >= xmax) ... 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 = xmax = ymax )
--- (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: Ik+1 = F(Ik) , 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 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.
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):
plante l'exécution du programme au niveau de la 2nde 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 TYPE Mat_B = ARRAY[0..Lim, 0..Lim] OF Byte; ... Test: Boolean; ... Test:= (Sxy<Lim)
mettant en jeu le rang (z, localement Z1) de la case abordée, et sa valeur maximale (Zmax = Lim2).
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))
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.
Il y a aussi la possibilité de trouver la valeur de la case (i,j) en connaissant la taille n de la matrice :
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) = N2 -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) = n2 - 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 ; n2-1] à partir du coin supérieur gauche (a0,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.
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.
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 à
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.
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]
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
Bravo. C'est ce que j'ai dit dès mon premier message pour lequel j'ai reçu un joli pouce baissé.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) .
Toutes vos solutions ont des conditions. Alors qu'aucune condition n'est nécessaire.
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du 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.
Ce n'est pas moi, juré; je le réserve aux trolls - au fait, a-t-on des nouvelles de FleurEnPlastique ?... pour lequel j'ai reçu un joli pouce baissé ...
Là, je veux bien connaître ton programme, et le voir fonctionner ...... Toutes vos solutions ont des conditions. Alors qu'aucune condition n'est nécessaire ...
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 !
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 ^^
en l'utilisant comme ceci pour remplir la matrice
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;
pour obtenir les couleur de sa grille
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));
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;
Blaise PascalNous souhaitons la vérité et nous trouvons qu'incertitude. [...]
Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
PS : n'oubliez pas le tag
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager