Estos últimos días he estado programando algunas cosas, y aquí les dejo un pequeño tip que aprendi hace un tiempo, pero lo utilice bastante estos dias que vuelvo a programar en C, ya después cuando tenga tiempo posteo algunas funciones que me parezcan útiles y que sirvan de ayuda, pero por los momentos les digo como modelar una matriz cuadrada en un vector, si ya se que no es muy difícil, pero es así, una matriz normalmente se modela con dos índices, algo así

M[i,j]
ahora para modelar eso en un vector lo haríamos así
V[i*N+j]

El numero de elementos de la matriz es N*N osea que el vector sera de longitud N*N.

Nada del otro mundo hasta el momento, la gran diferencia es cuando se usa memoria dinámica, ya que al hacerlo con un vector tomas toda una porción continua de memoria lo cual es más óptimo que tomar pedacitos en el modelado como matriz, tampoco es que es que es recontra-hyper mejor en cuanto a rendimiento del algoritmo de hecho casi no se nota pero si influye lo suficiente como para tomarlo en cuenta.

Ahora, que pasa cuando solo quiero usar la triangular superior de la matriz? sabemos que en la matriz lo hacemos así

M[i,j] siempre que j sea mayor o igual a i

pero y en el vector? en el vector lo haríamos así

V[(i*N+j)-i]

Ahora cuando trabajamos la matriz asi, aun tenemos N*N posiciones, pero no las usamos todas, fijense que queda la triangular inferior “vacia” (se le puede dar otro uso, dependiendo del problema), si el caso es que no se usara la triangular inferior, es muchisimo mejor usar el vector, pero de cuantas posiciones? no puede ser de N*N porque desperdiciarias la misma cantidad de espacio.

El vector tendria que ser de

(N*N+N)/2

Así que allí tienen este pequeño aporte mas adelante estaré posteando algunas funciones de las que usé estos últimos días, como el calculo de matrices de Alcance (Roy-Warshall) y así iré posteando otros algoritmos o tips como este
nota: esto funciona siempre y cuando los indices comienzen en 0 y la matriz sea cuadrada

Esta entrada fue publicada el Jueves, Diciembre 15th, 2005 a las 12:19 am y esta bajo las categorias General, Programacion, Prozac. Puedes seguir las respuestas de esta entrada a traves del RSS 2.0 feed. You can leave a response, or trackback from your own site.