[C] Sacar mínimos de una matriz

zildjian #1 Sep '09

Hola MVeros! No, esta vez no va de recursividad xD La cuestión es que quiero sacar los valores mínimos de una matriz, uno por uno, sin repetirlos (tiene que ver algo con grafos). La cuestión es que he programado lo siguiente:

int GetMinimumValue(int **M, int **V, int n, int *x, int *y){
	int minimum, i, j;
	minimum = INT_MAX;

for(i=0;i<n;i++){
	for(j=0;j<n;j++){
		if((M[i][j]<minimum) && (M[i][j]>0) && (V[i][j]!=1) && (V[j][i]!=1)){
			minimum = M[i][j];
			V[i][j] = 1;
			V[j][i] = 1;

			*x = i;
			*y = j;
		}
	}
}
printf("MIN: %d\n", minimum);

return minimum;
}

Donde M es la matriz con valores y la V está inicializada a 0 salvo cuando un nodo ya se ha visitado, que se marca con un 1. Así, no volverá a ser visitado. Pero al ejecutar el código no me saca los mínimos en el orden correcto. La matriz en cuestión es algo tal que así:

 0  5 14 10  0  0  0  0  0  0
 5  0 19  0  0  3  0  0  0  0
14 19  0  6  6  5  8  0  0  0
10  0  6  0 11  0  0  0  0  0
 0  0  6 11  0  0 10  0  7  0
 0  3  5  0  0  0  9  8  0  0
 0  0  8  0 10  9  0  3  8 14
 0  0  0  0  0  8  3  0  0  2
 0  0  0  0  7  0  8  0  0  3
 0  0  0  0  0  0 14  2  3  0

Y los resultados que obtengo son:
MIN: 2
MIN: 3
MIN: 3
MIN: 7 <-------- Hay cincos y seises en la matriz, por qué no me los imprime??

Thx por adelantado y saludos!

Josepanaero #2 Sep '09

Varias cosillas:

La parte del if ha salido cortada (al menos a mí no se me ve). ¿La puedes poner en dos líneas?
¿Puedes escribir el programa que llama a esta función?
Si x e y son dos simples enteros, ¿por qué los pasas como punteros? ¿No sería más elegante pasarlos por referencia (usando &)?
Si la matriz M no va a ser modificada en esta función, es una buena práctica pasarla como parámetro constante. Por la forma de declarar los iteradores i y j, doy por hecho que tu código está en C. No programo en C, sino en C++, donde existe el parámetro const, cosa que no sé si sucederá en C, así que lo mismo este punto lo puedes obviar, jeje.

Además, en estos casos lo mejor es usar un depurador e ir viendo paso a paso qué es lo que funciona mal.

EDIT: Esta función es muy ineficiente, porque recorres la matriz entera cuando únicamente es necesario recorrer la mitad.

zildjian #3 Sep '09

Lo acabo de solucionar, lo de marcar el 1 en la matriz V había que hacerlo fuera de los for. Y lo de la x y la y es porque necesito guardar el valor que toman en la función, por eso los paso en el main como &x &y . Y lo del if es otra condición de que no sea igual a 1. Si queréis, ya se puede chapar esto :$

EDIT: OSTIA es cierto, cómo podría hacer que recorriera sólo la mitad??

dagavi #4 Sep '09

#2 Es C, no C++. En C todos los parámetros se pasan por valor. Para realizar el paso por referencia se debe de simular vía punteros.

Josepanaero #5 Sep '09

Ok, gracias #4, no suelo programar en C y no lo sabía. Supongo que tampoco se usará "const", ¿verdad?

#3, para que recorra media matriz solamente tendrías que cambiar el segundo for, el relativo a j, y ponerle como condición "j < i + 1" en vez de "j < n".

Salu2!!

Fr4nk0 #6 Sep '09

Como dice #5 para recorrer la mitad sólo tienes que cambiar la segunda condición del for.

La razón es que si te fijas, esa Matriz es Simétrica, es decir la matriz es igual a su traspuesta, y su valor Aij = Aji . De ahi la razón de recorrer sólo la mitad, ya que la otra mitad de la matriz es la misma.

dagavi #7 Sep '09

#5 No, tampoco hay const.

COSMOS #8 Sep '09

no se la sintaxis de C pero a ver si te vale este algoritmo, veo que pides sacar asi ke te lo pongo por pantalla, que si es sacar al metodo principal se lia un poco y toy sobao ya xD

suponemos que menorValor es un numero muy grande para encontrar algo menor,del estilo INT_MAX para c++,cotainferior la usamos para delimitar el valor minimo que queremos y el contador para no tirarnos la vida dando vueltas

procedure metodo(A[][] matriz de enteros, entero menorValor,entero contaInferior,nat contadordevueltas)
{
if contadordevueltas< ( a.longitud*a[].longitud)
{
para(i=0 ;i< a.longitud;i++)//recorres filas
para(i=0 ;j< a[].longitud;j++) //recorres columnas
{

si(A[j] <menorValor)&& (A[j]!=0)&& (A[j]>contaInferior) menorValor=A[j]
**es menor que el menor actual y no es 0

**si ademas es mayor que la cotainferior es el que buscamos
}
printf("MIN: %d\n", menorValor);
metodo(A,INT_MAX,menorvalor,contadordevueltas++);
}
}

daremos tantas vueltas como elementos tiene la matriz pero no sacaremos elementos repetidos, si kieres mejorar eficiencia puedes meter booleanos que indican si no has encontrado un mayor de la cota para que salte etc.

espero que te sirva

edit: la llamada principal seria metodo(A,98231891389138913298123,0,0)

B

[Borrado] #9 Sep '09

#7: No sé si son cosas distintas, pero yo en C sí uso const xD (igual me estoy equivocando pero diría que no).

[C] Sacar mínimos de una matriz

Usuarios habituales

Tags