Discussion :

[Aspic]

Bonsoir,

Dans mon problème, j'utilise une matrice 2D représentant un terrain de jeu.
Par soucis d'optimisation, je n'ai pas voulu représenter ma matrice par un tableau 2D mais simplement par un tableau 1D.
En ayant le nombre de colonne, je peux donc retrouver ma matrice originale.

Considérons le terrain suivant 3x5 (3 lignes et 5 colonnes)

1 2 3 4 5
6 7 8 9 10
11 12 30 31 40

Si je veux la distance de manhattan entre les points 10 et 30, je prends les coordonnées (1, 4) et (2, 2) et j'applique la formule : M = abs(1 - 2) + abs(4 - 2) = 3

Maintenant, en mémoire, ma représentation est la suivante :

1 2 3 4 5 6 7 8 9 10 11 12 30 31 40

Comment appliquer la distance de manhattan dans ce cas ?

Merci

Bonne soirée

[anapurna]

tu te complique la vie la matrice 2d prend la même place en mémoire que le 1 d
mais si tu veut garder la linéarité il faut que tu calcule l'indice y
imagine que ta valeur soit en [3,3]
donc ton indice est x+(y-1)*L
donc dans note cas 3+(3-1)*5
=3+2*5 = 13
donc ta valeur ce trouve a la 13iem position

j’espère t'avoir mis sur la voie

[wiwaxia]

Bonjour,

Dans mon problème, j'utilise une matrice 2D représentant un terrain de jeu.
Par souci d'optimisation, je n'ai pas voulu représenter ma matrice par un tableau 2D mais simplement par un tableau 1D.
En ayant le nombre de colonnes, je peux donc retrouver ma matrice originale.
Considérons le terrain suivant 3x5 (3 lignes et 5 colonnes) ... Comment appliquer la distance de manhattan dans ce cas ?

La première réponse a ciblé l'essentiel ...

tu te compliques la vie la matrice 2d prend la même place en mémoire que le 1 d
... imagine que ta valeur soit en [3,3]

... mais peut-être aurait-il mieux valu proposer un couple de 2 valeurs différentes, par exemple (2, 4).

Pour repasser du terme de rang (k) de la liste indexée [1 ... N] à l'élément (i, j) de la matrice (LxC) contenant le même nombre de termes (N = L.C), il suffit d'un petit calcul d'arithmétique modulaire - puisque la descente d'une ligne augmente le rang (k) d'une quantité égale au nombre de colonnes (C):
i = 1 + ((k-1) DIV C) [ quotient de la division euclidienne ]
j = 1 + ((k-1) MOD C) [ reste de la division euclidienne ]

[anapurna]

salut ,

effectivement j'aurais pu donnée aussi cette solution mais vu l'heure de ma réponse, mon cerveau ne devez pas être a 100% de ses capacité
en fait tout dépend de ton point de départ.
j'ai supposé qu'il étais parti de son écran de jeux et donc de ces coordonnée en deux 2D
mais comme tu le démontre il est tout aussi facile de retrouver les coordonné à partir de l'indice du tableau linéaire

on a donc selon le cas les solution fournis précédemment
en gardant le même formalisme que le précédent post on aurais donc
ma proposition se traduirais donc comme ceci

k = I+(J-1)*C

par contre je ne suis pas certain de ta notation ne serait ce pas plutôt

J = 1 + ((k-1) DIV C) [ quotient de la division euclidienne ]
I = 1 + ((k-1) MOD C) [ reste de la division euclidienne ]

J donnant le nombre de lignes (pour moi c'est donc le Y)
I donnant la position sur la ligne (pour moi c'est donc le X)
prenons donc l'exemple proposé

(2, 4) =>K := 2+(4-1)*5 = 2+3*5 = 17

cherchons donc les indices dans une matrice

I = 1+((17-1) MOD 5) = 1+(16 MOD 5) = 1+1 = 2
J = 1+ ((17-1) DIV 5) = 1+(16 DIV 5) = 1+3 = 4

mes 2 cts

[wiwaxia]

Salut,

Je n'avais aucun objection au sujet de la concision de ta première réponse. Je regrettais seulement la trop grande simplicité de l'exemple numérique (3, 3), dont il apparaît qu'il masquait sournoisement une divergence de notation beaucoup plus sérieuse.

... par contre je ne suis pas certain de ta notation ne serait ce pas plutôt ...
J donnant le nombre de lignes (pour moi c'est donc le Y)
I donnant la position sur la ligne (pour moi c'est donc le X)

Il a toujours été d'usage (et je ne crois pas que cela ait changé récemment) de localiser l'élément (i, j) d'une matrice en parlant d'abord de la i^me ligne, puis de la j^me colonne.
Le lien suivant est tout à fait explicite (le passage relatif aux définitions n'a pas pu être correctement imprimé)
http:// https://fr.wikipedia.org/wiki/Matrice_%28math%C3%A9matiques%29

Dans ce cas, on dit que la matrice a m lignes et n colonnes, ou qu'elle est de dimension ou taille (m, n). En notant ai,j l'image d'un couple (i, j) par l'application A, la matrice peut alors être notée: A=(a_i,j),(1<=i<=m , 1<=j<=n)

La correspondance (i, j) <---> (y, x) ne conserve pas l'ordre alphabétique, ce qui est parfois une source d'erreurs - je me plante ainsi de temps à autre lors de la programmation d'un page d'écran texte, en rédigeant de tête des instructions du genre:

Code :

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

Ecrire(x, y, 'Chaine .. ')

Le seul moyen (primaire, je l'avoue) de s'en prémunir est de penser au mot "colline".

Par contre, je ne vois pas bien comment une matrice (3x5) peut contenir un terme de rang = 17:

prenons donc l'exemple proposé
(2, 4) =>K := 2+(4-1)*5 = 2+3*5 = 17
cherchons donc les indices dans une matrice
I = 1+((17-1) MOD 5) = 1+(16 MOD 5) = 1+1 = 2
J = 1+ ((17-1) DIV 5) = 1+(16 DIV 5) = 1+3 = 4

(2, 4) se situant à l'intersection de la 2^me ligne et de la 4^me colone, figure dans la liste au rang
k = j + (i-1)C = 4 + (1*5) = 9 , qui par la division euclidienne redonne:
i = 1 + (k-1) DIV C = 1 + 8DIV 5 = 1 + 1 = 2
j = 1 + (k-1) MOD C = 1 + 8 MOD 5 = 1 + 3 = 4
Les valeurs de (i) et (j) ont été permutées dans ton calcul ... Rien de pire que l'échange de symboles dans une formule !

[anapurna]

bonjour

c'est normal on ne part pas des même élément
je n'ai pas dis que la matrice étais de 3 par 5
j'ai juste repris tes éléments mais comme nous ne parlions pas de la même chose j'ai effectivement inversé les i et le j ...
étant développeur, l'utilisation de tableau ce font dans le sens Tbl[x,y] pour tout ce qui concerne le graphisme d'ou ma meprise
je reste cohérent avec moi même

bon le principe est le même le résultat diffèrent c'est certain
ouais la permutation de symbole c'est pas cool
le principale c'est que l'on ai répondu a la question du demandeur