Tableaux 3*3 à partir d'un 9*9

Bonsoir !
J'ai une matrice 9*9 (mais ça doit pouvoir s'appliquer à d'autres), et j'aimerais récupérer toutes les matrices 3*3 qui sont à l'intérieur (enfin, les unes "à coté" des autres).
Un exemple simple :

Code:

---

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

Tableau de départ:   [ 1 2 3 4] [ 5 6 7 8] [ 9 10 11 12] [13 14 15 16]   ------------------- En sortie:   [1 2] [3 4] [5 6] [7 8]   [ 9 10] [11 12] [13 14] [15 16]

---

Pour cela, il doit y avoir des algos, non ?
Je ne trouve pas comment le faire avec un commplexité assez faible (j'ai trois boucles imbriquées 8O ).

Merci pour votre aide !

ben trois boucles for imbriquées, ce n'est pas vraiment l'horreur, je trouve.

enfin, je ne vois pas où est le problème, c'est plutot rapide comme code (avec des boucles de 0à3, ça te fait que 27 fois ta procédure pour toute la grille, c'est pas phénoménal.)



salut :wink:

Tu peux faire en deux boucles (tu parcours toute ta matrice) et avec des tests tu identifie le bloc (la matrice 3 * 3) dans lequel tu es. Cependant je ne sais pas si celà va être beaucoup plus efficace que tes trois boucles.

Pour identifier le bloc dans lequel tu es, tu divise l'indice ou tu es (x pour savoir le n° de ma trice sur x et y pour savoir le numéro de la matrice sur y) par la taille de la matrice que tu veux extraire. (division entière).

Et sincèrement si tu te limite aux matrices 9 * 9, le nombre d'iteration n'est pas énorme.

Salut
L'algo est de cette forme en supposant que matrice est un tableau de 9 matrices 3 X 3

Code:

---

1 2 3 4 5 6 7 8 9 10 11

pour i de 1 à 9 par pas de 1 pour j de 1 à 9 par pas de 1 // calcul du numero de matrice 3 X 3 num <- i div 3 + 3 * ( j div 3) // calcul du numero de ligne de la matrice mi <- i mod 3 // calcul du numero de colonne mj <- j mod 3 matrice[num][mi][mj] <- matrice_initiale[i][j] fin pour fin pour

---

Oki, mais je risque d'avoir une matrice nettement plus grande ensuite (carrée tout de même), car de taille 2187*2187, que je subdiviserais en 9*9...puis 3*3...
Pour de la convolution.
Si vous avez un algo de complexité assez faible pour cela, je prend !

Edit: Merci Trap D quand même :)

Pour pousser le vice, on pourrait même le faire en une seule boucle:

Code:

---

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

pour k de 1 à 81 par pas de 1 //calcul de i i <- k div 9 //calcul de j j <- k mod 9 // calcul du numero de matrice 3 X 3 num <- i div + 3 * ( j div 3) // calcul du numero de ligne de la matrice mi <- i mod 3 // calcul du numero de colonne mj <- j mod 3 matrice[num][mi][mj] <- matrice_initiale[i][j] fin pour

---

Mais franchement, la complexité à l'air d'être plus faible mais elle l'était déjà avant. Le fait d'avoir trois boucles ne veut pas dire que la complexité est élevé. L'algorithme de départ était en O(n) où n est le nombre d'éléments, celui-ci l'est aussi... Mais si on regardait le temps de calcul, avec une boucle, il y a des modulos, des divisions ce qui va rendre le tout beaucoup plus lent.

Jc

Citation:

---

Envoyé par fearyourself

Pour pousser le vice, on pourrait même le faire en une seule boucle

---

On peut démontrer que n'importe quel programme peut s'écrire avec une seule boucle. Je m'en souviens bien, j'avais eu ça comme question à un exam d'IA.

Etrange de vouloir évaluer la complexité d'un algo qui s'applique à une matrice de taille constante...

De retour !
Je n'ai plus un tableau 2 dimensions, mais un vecteur !
Il me faut toujours extraire en 3*3...
En clair, sur ceci :

Citation:

---

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

---

Il me faut avoir au final :

Citation:

---

0=> 0 1 2 9 10 11 18 19 20
1=> 4 5 6 12 13 14 21 22 23
2=> 6 7 8 15 16 17 24 25 26
etc...

---

Et alors là, je suis paumé dans les div et les modulo !!!
Merci de m'aider :s