Algo

[Algo] Rotation de matrice?

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [Algo] Rotation de matrice?

Ryu Braska

Anciennement ZeroCoolZ

Admettons que j'ai une matrice de 4x4 à laquelle je veux faire une rotation de 90 degrés vers la droite

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

qui deviendrait alors

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

Est-ce possible de faire l'opération sans utiliser une matrice intermediaire?

Message édité par Ryu Braska le 07-02-2005 à 11:31:33

Publicité

Emmanuel Delahaye

C is a sharp tool

Ryu Braska a écrit :

C'est une question d'algorithme qui n'a pas grand chose à voir avec le langage C...

-> forum 'Algo'

Message édité par Emmanuel Delahaye le 07-02-2005 à 08:29:45

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/

moi23372

oui c'est une question d'algo pas tès compliquée franchement...

si tu n'es pas capable de faire ça, tu ne seras jms un bon programmeur...

skeye

moi23372 a écrit :

oui c'est une question d'algo pas tès compliquée franchement...

si tu n'es pas capable de faire ça, tu ne seras jms un bon programmeur...

[:kiki]
Il doit tout juste commencer la programmation, vu la question...ta remarque est franchement stupide.

---------------
Can't buy what I want because it's free -

Ryu Braska

Anciennement ZeroCoolZ

moi23372 a écrit :

oui c'est une question d'algo pas tès compliquée franchement...

si tu n'es pas capable de faire ça, tu ne seras jms un bon programmeur...

Super sympa, merci! :jap:

vttman2

Je suis Open ...

Tu vois comment faire, utilisation
de tableau par exemple ...

Les données de tes matrices sont stockées ou ?

Tu utilises quel langage ?

Ryu Braska

Anciennement ZeroCoolZ

Du C.... les données sont dans un tableau à 2 dimensions... je veux pouvoir les "tourner" sans effacer des données et sans utiliser un tableau intermediaire :pt1cable:

skeye

Ryu Braska a écrit :

Du C.... les données sont dans un tableau à 2 dimensions... je veux pouvoir les "tourner" sans effacer des données et sans utiliser un tableau intermediaire :pt1cable:

Ca doit être faisable...Tu prends la première valeur, tu calcules sa nouvelle position, tu stockes la valeur qui s'y trouve, tu remplaces par la première valeur, et ainsi de suite jusqu'à avoir tout fait... [:ddr555]

---------------
Can't buy what I want because it's free -

Ryu Braska

Anciennement ZeroCoolZ

Je sais bien mais je me suis installé devant une feuille de papier, mais je ne sais pas pourquoi j'arrive pas à trouver une solution simple et pourtant j'ai l'impression que c'est hyper simple. C'est pourquoi je demandais pour voir si quelqu'un ne connaitrait pas une belle solution toute simple

skeye

Bah t'as plus qu'à trouver la formule pour calculer la nouvelle position à-partir de l'ancienne, c'est pas bien complexe...

---------------
Can't buy what I want because it's free -

Publicité

Ryu Braska

Anciennement ZeroCoolZ

Bah [i,j] -> [j,max-i] mais c'est la boucle pour tout faire efficacement sans perdre de données qui m'échappe

skeye

Ryu Braska a écrit :

Bah [i,j] -> [j,max-i] mais c'est la boucle pour tout faire efficacement sans perdre de données qui m'échappe

Commence à l'écrire, tu te rendras compte tout seul des variables qu'il te faut...

---------------
Can't buy what I want because it's free -

vttman2

Je suis Open ...

Dans ce cas
=>
pour i de 1 à Max
pour j de 1 à max
Bah [i,j] -> [j,max-i]
fpourj
fpouri

A transcrire en c ... non ?

skeye

vttman2 a écrit :

Dans ce cas
=>
pour i de 1 à Max
pour j de 1 à max
Bah [i,j] -> [j,max-i]
fpourj
fpouri

A transcrire en c ... non ?

Bravo, tu viens d'écraser la moitié de tes données... [:dawa]

---------------
Can't buy what I want because it's free -

skeye

(même plus, d'ailleurs... [:ddr555] )

---------------
Can't buy what I want because it's free -

masklinn

í dag viðrar vel til loftárása

skeye a écrit :

(même plus, d'ailleurs... [:ddr555] )

~~il a écrasé toute ses données et a tout remplacé par la donnée situées en [1,1]~~ [:aloy]
(j'ajouterais qu'on commence habituellement un tableau à l'indice 0)

Ryu > tu veux faire une rotation "en place" (càd donner une matrice en entrée et retrouver la même en matrice tournée) ou une rotation "copie" (càd avoir 2 matrices en sortie, l'originelle et la matrice tournée)?

Pour une rotation en place, pense simplement au stockage temporaire de données et combien de données tu dois stocker à chaque instant T

Message édité par masklinn le 07-02-2005 à 12:19:16

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?

skeye

Masklinn a écrit :

il a écrasé toute ses données et a tout remplacé par la donnée situées en [1,1] [:aloy]

euh...non. :heink:

Masklinn a écrit :

(j'ajouterais qu'on commence habituellement un tableau à l'indice 0)

pas en algo...

---------------
Can't buy what I want because it's free -

masklinn

í dag viðrar vel til loftárása

skeye a écrit :

euh...non. :heink:

ah merde j'avais pas vu le déroulement de l'algo, my bad, chuis un moisi des yeux [:matleflou]

Ryu Braska

Anciennement ZeroCoolZ

Ouais effectivement on efface des données de cette facon...

Masklinn > sur place...

masklinn

í dag viðrar vel til loftárása

Ryu Braska a écrit :

Ouais effectivement on efface des données de cette facon...

Masklinn > sur place...

Ben t'as juste à déterminer le nombre de valeurs à stocker temporairement à chaque instant [:cupra]

darkoli

Le Petit Dinosaure Bleu

Dans le cas simple d'une rotation de 90° dans le sens des aiguilles d'une montre et avec une matrice 3x3 :

a ? b
? * ?
c ? d

Si on traite le point a, on va se rendre compte qu'il va prendre la place du point b, qui va prendre à son tour la place du point c, ...
Voilà un peut la réflexion que j'aurais.

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

vttman2

Je suis Open ...

skeye a écrit :

Bravo, tu viens d'écraser la moitié de tes données... [:dawa]

:ouch:
Je suis en forme aujourd'hui, ça se voit !
:lol:

Chronoklazm

Pourquoi ne pas simplement faire une fonction swap, toute conne et l'appliquer a tous les elements de la matrice? Si t'as une matrice 4*4 tu peux le faire directement, si c'est pour une matrice n*n tu fait ca en boucle ...

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !

darkoli

Le Petit Dinosaure Bleu

Chronoklazm a écrit :

Le problème est que tu ne peux pas "swapper" deux éléments simplement, en fait il fait faire tourner quatre éléments à la fois.

Voici l'approche que j'ai utilisé :

Lorsque je rote un élément je fais aussi roté l'élément sur lequel j'arrive, je n'ai donc pas besoin de travailler sur la totalité de la matrice pour réaliser la rotation puisque chaque rotation déplace 4 points.

Pour une matrice 3x3 voilà les points de départ que je vais utiliser :

1 2 x
x o x
x x x

Pour une matrice 4x4 :

1 2 x x
3 4 x x
x x x x
x x x x

Pour une matrice 5x5 :

1 2 3 x x
4 5 6 x x
x x o x x
x x x x x
x x x x x

Un exemple avec une matrice 2x2 :

a b
c d

Il faut déterminer le centre de la rotation, dans le cas d'une matrice 2x2, le centre est (0.5,0.5).

Pour chaque point à faire tourner, il faut déterminer son décalage par rapport au point de rotation. Dans le cas d'une matrice 2x2, il y a un seul point à faire tourner (4x). À chaque rotation, on enregistre la valeur de l'élément sur lequel on se trouve et on écrit la valeur de l'élément dont on vient.

Les coordonnées se calculent de la façon suivante (pour une matrice 2x2) :
- Décalage du point de départ de la rotation (a) avec le centre de rotation : Dx=-0,5 et Dy=-0,5.
- On obtient les coordonnées du premier point (b) :
=> bx = (rx-Dy)
=> by = (ry+Dx)
- Pour le deuxième point (c) :
=> cx = (rx-Dx)
=> cy = (ry-Dy)
- Pour le troisième point (d) :
=> dx = (rx+Dy)
=> dy = (ry-Dx)
- Pour le quatrième point, on en connait déjà les coordonnées !

Cette méthode s'applique a n'importe quelle taille de matrice.

Je ne sais pas si j'ai été clair, voilà un exemple du petit programme que j'ai écrit :

/home/darkoli/hfr > ./rotation_matrice a b c d e f g h i j k l m n o p q r s t u v w x y
La matrice est de taille : 5x5.

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y

u p k f a
v q l g b
w r m h c
x s n i d
y t o j e

Mais bon, dupliquer la matrice pour faire cette rotation est vachement plus simple !

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

FlorentG

Ouaip, en dupliquant c'est plusse mieux...

Ryu Braska

Anciennement ZeroCoolZ

Plus simple oui mais pas mieux

sircam

I Like Trains

C'est sympa, ton approche "point de pivot au centre" et je me concentre sur ce qu'il y a au-dessus à gauche.

J'avais pensé à ceci :

Tu attaques la matrice par le "périmètre extérieur" :

1 2 3 4
5 x x 8
9 x x 12
13 14 15 16

Et tu appliques la "4 swap points exploding technique" que tu as décrite à la rangée du dessus (donc tout le périmètre extérieur va subir la rotation).

Ensuite, tu passes au périmètre intérieur suivant

x x x x
x 6 7 x
x 10 11 x
x x x x

Et rebelote.

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}

darkoli

Le Petit Dinosaure Bleu

sircam a écrit :

C'est sympa, ton approche "point de pivot au centre" et je me concentre sur ce qu'il y a au-dessus à gauche.

J'avais pensé à ceci :

Tu attaques la matrice par le "périmètre extérieur" :

Pas réellement, voilà le détail pour une matrice 3x3 :

a b c
d e f
g h i

Je fais la rotation de l'élément a, tout en sauvegardant l'élément c.

a b a
d e f
g h i

Donc l'élément c prend la place de l'élément i.

a b a
d e f
g h c

L'élément i prend la place de l'élément g.

a b a
d e f
i h c

Et enfin l'élément g prend la place du premier élément.

g b a
d e f
i h c

Il faut faire de même avec les éléments b, f, h et d.

Message édité par darkoli le 07-02-2005 à 22:20:06

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

sircam

I Like Trains

Enfin soit, ça revient +/- au même à un chouia près, problème résolu.

D'autres questions ?

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}

Lam's

Profil: bas.

Darkoli, dans ta méthode, il y a combien de lignes de code pour faire la rotation ?

Parce qu'avec la méthode sircam (celle qui m'a paru la plus évidente intuitivement), j'ai 9 lignes de code (2 for, 2 accolades, et 5 lignes d'affectations pour transvaser les valeurs).

darkoli

Le Petit Dinosaure Bleu

Lam's a écrit :

Moi j'ai 25 lignes de code. La rotation est faite directement sur la liste des paramètres (normalement appelée "argv" ).
Le tout fonctionne bien quelque soit la taille de la matrice 2x2 ou 16x16 (par exemple mais la ligne de commande devient grande ).

Code :

lzr=(l+1)>>1;
hzr=l>>1;
m=l-1;
for (j=0;j<hzr;j++)
{
dy=(j<<1)-m;
for (i=0;i<lzr;i++)
{
dx=(i<<1)-m;
x=i;
y=j;
t2=parametres[(y*l)+x+1];
for (k=0;k<4;k++)
{
td=dx;
dx=-dy;
dy=td;
x=(m+dx)>>1;
y=(m+dy)>>1;
t1=parametres[(y*l)+x+1];
parametres[(y*l)+x+1]=t2;
t2=t1;
}
}
}

En fait je ne suis pas certain d'avoir bien compris la méthode de sircam. En utilisant par exemple le périmètre extérieur, chaque élément va être déplacé 4 fois (pour une matrice 4x4) ?

Message édité par darkoli le 08-02-2005 à 19:33:38

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

Lam's

Profil: bas.

Code :

#include <stdlib.h>
#include <stdio.h>
#define max 4
int tab[max+1][max+1];
int main()
{
size_t i,j;
for (i=0; i<=max; ++i)
for (j=0; j<=max; ++j)
tab[j][i] = i*(max+1)+j+1;
for (i=0; i<=max; ++i)
{
for (j=0; j<=max; ++j)
printf("%2d ", tab[j][i]);
printf ("\n" );
}
printf ("\nApres:\n" );
for (j=0; j<max-1; ++j)
{
for (i=j; i<max-j; ++i)
{
int temp =tab[i][j] ;
tab[i][j] = tab[max-j][i];
tab[max-j][i] = tab[max-i][max-j];
tab[max-i][max-j] =tab[j][max-i];
tab[j][max-i] = temp;
}
}
for (i=0; i<=max; ++i)
{
for (j=0; j<=max; ++j)
printf("%2d ", tab[j][i]);
printf ("\n" );
}
return 0;
}

Message édité par Lam's le 08-02-2005 à 19:43:45

vttman2

Je suis Open ...

En retard Méthode Similaire Sircam donc ...
Pour ma part, je propose un vbscript ...
J'effectue une rotation sur le "carré" de valeurs extérieur (dim 5)
1 2 3 4 5 10 15 20 25 24 23 33 21 16 11 6 1
puis sur les "carrés" plus petit (ici dim 3)
7 8 9 14 19 18 17 12 7

=>

Dim i ,tab(5,5)

tab(1,1)=1
tab(1,2)=2
tab(1,3)=3
tab(1,4)=4
tab(1,5)=5
tab(2,1)=6
tab(2,2)=7
tab(2,3)=8
tab(2,4)=9
tab(2,5)=10
tab(3,1)=11
tab(3,2)=12
tab(3,3)=13
tab(3,4)=14
tab(3,5)=15
tab(4,1)=16
tab(4,2)=17
tab(4,3)=18
tab(4,4)=19
tab(4,5)=20
tab(5,1)=21
tab(5,2)=22
tab(5,3)=23
tab(5,4)=24
tab(5,5)=25

max=6
for i = 1 to 2
for j = i to Max-i-1
tmp = tab(j,max-i)
tab(j , max-i) = tab(i , j)
tmp1 = tab(max-i, max-j)
tab(max-i, max-j) = tmp
tmp = tab(max-j, i )
tab(max-j, i ) = tmp1
tab(i , j ) = tmp
next
next

Remarque :
=>
Marche pour toute matrice
La variable Max est le nombre de colonne + 1 (ici 5+1)

Verif ligne par ligne
=>

for i = 1 to (Max -1)
MsgBox tab(i,1) & " " & tab(i,2) & " " & tab(i,3) & " " & tab(i,4) & " " & tab(i,5)
next

Message édité par vttman2 le 09-02-2005 à 13:32:04

sircam

I Like Trains

vttman2 a écrit :

Pour ma part, je propose un vbscript ...

Aïe... Je crains le pire.

vttman2 a écrit :

Dim i ,tab(5,5)

tab(1,1)=1
tab(1,2)=2
tab(1,3)=3
tab(1,4)=4
tab(1,5)=5
tab(2,1)=6
tab(2,2)=7
tab(2,3)=8
tab(2,4)=9
tab(2,5)=10
tab(3,1)=11
tab(3,2)=12
tab(3,3)=13
tab(3,4)=14
tab(3,5)=15
tab(4,1)=16
tab(4,2)=17
tab(4,3)=18
tab(4,4)=19
tab(4,5)=20
tab(5,1)=21
tab(5,2)=22
tab(5,3)=23
tab(5,4)=24
tab(5,5)=25

[:kiki] Mes craintes étaient fondées. C'est quoi, cette immondice vomitive ? [:austiniste]

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}

vttman2

Je suis Open ...

C pas sympa ça ...
ça a pas de style (je reconnais)
mais ça fonctionne !
Cela dit le vbscript je pratique pas ;-)

Lam's

Profil: bas.

Boah, t'as qu'à faire comme dans les lignes 12 à 14 de mon bout de code...

sircam

I Like Trains

vttman2 a écrit :

C pas sympa ça ...
ça a pas de style (je reconnais)
mais ça fonctionne !
Cela dit le vbscript je pratique pas ;-)

Oh dis, désolé, ne le prends pas mal, t'es sans doute un gars bien, c'est rien de perso ni un jugement de valeur, mais ça... ça... ce truc là... C'est dégueulasse !

On serait dans la cat "VB" que ça ne choquerait personne , mais dans la cat "algo", ça fait pas bon genre.

Ca mériterait un coup de pelle à clous. Je t'en fais grâce.

EDIT : le VBscrap, je ne pratique pas non plus, mais c'est pas une raison, on n'est pas vendredi

Message édité par sircam le 09-02-2005 à 13:42:39

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}

vttman2

Je suis Open ...

C sûr ...
Mais bon là je m'étais un peu focalisé sur le pb
et pas sur l'entrée des données

Je le referai plus M'sieur !

sircam

I Like Trains

:ange:

---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}

Lan Wezel

Juste un ptit truc, je pense qu'on peut un tout petit peu améliorer la méthode de darkoli en faisant la rotation dans l'autre sens :

a b c
d e f
g h i

on sauvegarde a, on met g dans a, i dans g, c dans i puis a dans c : on n'a utilisé qu'une seule affectation de variable.

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

Algo

[Algo] Rotation de matrice?

Sujets relatifs
recherche algo pour expansion d'une structure.	[algo] Problème d'affectation
Jeu DEMINEUR:algo ki affiche toutes les cases vides à partir du click	[scheme] Renom: Ajouter une ligne à une matrice
Algo compression Decompression TMS	[algo] Tracer un cercle
Programme Image--->Matrice	[VBA/SQL/Algo] Access : importation automatique de fichiers
rotation en opengl ac les fleches	[ocaml/algo] Comment représente-t-on une file en ocaml ?? :??:
Plus de sujets relatifs à : [Algo] Rotation de matrice?

Page générée en 0.135 secondes