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

**progfou** · 18/12/2005, 17h46

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 :

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

).

Merci pour votre aide !

**méphistopheles** · 18/12/2005, 20h17

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

**PRomu@ld** · 19/12/2005, 09h39

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.

**Trap D** · 19/12/2005, 11h18

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

Code :

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

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

**progfou** · 19/12/2005, 17h08

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

**fearyourself** · 19/12/2005, 17h26

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

Code :

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

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

**sovitec** · 20/12/2005, 11h52

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.