Existe-t-il un moyen de trouver la ligne d'une cellule donnée dans une matrice ordonnée?

Par exemple, étant donné une matrice:Existe-t-il un moyen de trouver la ligne d'une cellule donnée dans une matrice ordonnée?

01|02|03|04|05 
    06|07|08|09|10 
    11|12|13|14|15

Et sachant que la matrice est 5x3, est-il possible que si on leur donne la valeur « 7 », que nous pouvons le savoir est dans la ligne 2? Le cas est que la matrice est toujours ordonnée de 1 à n, à partir de 0.

Enfin, la matrice est stockée linéairement dans un tableau à base zéro.

Source

2009-04-18 ApplePieIsGood

Voulez-vous une solution basée sur zéro ou non? Votre réponse acceptée n'est pas basée sur zéro. –

Une autre chose à considérer est de savoir si votre "ligne 1" est effectivement considérée comme la ligne 1 ou 0 dans votre matrice. Il y a beaucoup d'ambiguïté ici. –

Oui, rien comme indiqué est basé sur zéro. L'élément en haut à gauche est 1, et il semble avoir (row, col) = (1,1). – Kip

row = ceiling(7/5) or ceiling(position/width)

Source

2009-04-18 04:44:42 rvarcher

Pourquoi cela a-t-il été modifié? Est-ce que ce n'est pas correct? Cela semble correct et précis. – ApplePieIsGood

Je ne l'ai pas downmod ... mais je ferais remarquer que bien que ce soit la bonne réponse pour une classe de maths, ce n'est pas une solution idéale de * programmation * parce que vous auriez besoin de faire des calculs en virgule flottante inutiles. De plus, si la position et la largeur sont des entiers, une implémentation naïve de ceil (pos/width) serait en réalité équivalente ceil (floor (pos/width)) = floor (pos/width). Cela dépend du langage de programmation, bien sûr, certains utiliseront les mathématiques à virgule flottante pour toutes les divisions, à moins que vous ne fassiez un détour. – Kip

Let X be your index 
------------------- 
column = X % width 
row = ceiling(X/width)

Modifier: Semble travailler maintenant que je fait quelques changements.

Source

2009-04-18 04:32:06

Si la matrice est stockée dans un row-major ordre, puis les indices de ligne map à l'index des éléments comme suit:

rowIndex = (elementIndex - 1)/numcolumns 
columnIndex = (elementIndex % numcolumns) - 1

C'est toujours division entière - donc pas de reliquats. Vous obtiendrez les indices de ligne et de colonne à partir de 0.

Il nous reste un exercice pour comprendre ce qui se passe dans une disposition de colonne majeure.

Source

2009-04-18 04:37:03 dirkgently

Mais 7 - 1/4 est 1,5, laissant 1, et dans une matrice 3x4, 7 est dans la 3e rangée, ou l'index 2 dans un tableau basé sur zéro. A moins que je ne manque quelque chose, ta réponse ne va pas? – ApplePieIsGood

Merci! Correction d'une faute de frappe. S'il vous plaît voir le post mis à jour. – dirkgently

Dans votre cas, numcolumns = 5. Donc, rowIndex = (7 - 1)/5 = 6/5 = 1 (puisque les indices commencent à 0, cela indique la deuxième rangée). En outre, columnIndex = 7% 5 - 1 = 2 - 1 = 1 (la deuxième colonne). – dirkgently

si elle est base 0:

ligne: n/largeur
col: n% largeur

Dans votre exemple, vous dites qu'il est basé sur zéro, mais il commence réellement à 1, et vous comptez l'élément en haut à gauche en tant que (ligne, col) = (1,1), de sorte que vous devez ajuster les maths:

rangée: (n-1)/largeur + 1
col: (n-1)% largeur + 1

Dans votre cas, n = 7, largeur = 5:

rangée = (7-1)/5 + 1 = 1 + 1 = 2
col = (1/7)% 5 + 1 = 1 + 1 = 2

note: J'utilise nombre entier de programmeur norme math, où "a/b" signifie vraiment "floor (a/b)".

Source

2009-04-18 04:48:43 Kip

Mauvaise communication de ma part, je voulais dire qu'il est stocké dans un tableau basé sur zéro, pas que la première valeur est basée sur zéro. – ApplePieIsGood

Existe-t-il un moyen de trouver la ligne d'une cellule donnée dans une matrice ordonnée?

Répondre

Questions connexes