Multiplicacion de Matrices en C

Como escribí en la primera entrada de este blog: Propósito mi intención es subir programas y ejercicios resueltos de los libros de Deitel Como Programar en Java y C++, asi como los del libro El lenguaje de programacion C de Kernighan y Ritchie, y algunos de Algoritmos de Sedgewick. Sin embargo, el algoritmo clásico de la multiplicación de dos matrices es bastante común y me parece que no esta fuera de lugar colocar aquí el código en C. He hecho el programa pensando en que sea útil, más que en poner el algoritmo simplemente. Ustedes pueden definir el tamaño de las matrices así como las entradas y también pueden ver desplegadas las matrices en la pantalla ( si los resultados son lo bastante chicos como para entrar en la pantalla de su computadora ). Este problema también aparece resuelto para el lenguaje C++ en la entrada Multiplicación de Matrices en C++ de enero de 2011, en un programa menos complicado que éste.

#include <stdio.h>
#define M 2
#define N 3
#define P 4

Multiplicacion_Matrices(void)

// Todo el problema se resuelve en esta funcion, la funcion main
// solo sirve para llamar a esta
// Es necesario hacer esta funcion mas pequenia

{ // Abre la funcion Multiplicacion_Matrices

int i; // Estos tres indices controlaran tres ciclos en el algoritmo
int j; // principal del programa, aunque se usaran fuera de este para
int k; // controlar otros ciclos sin ninguna ambiguedad

// se define una matriz de N filas por M columnas
// esta va a ser la primera matriz, es importante el orden porque
// en general la multiplicacion de matrices es no conmutativa

int Matriz1[M][N] = { {0}};
// con esto todas las entradas se inicializan a cero

// Aqui se reciben las entradas de la primera matriz
// Este programa contiene mas cosas de las que se pide normalmente
// en este problema clasico, una de ellas es pedir las entradas de las
// matrices una por una, en lugar de ponerlas al definir las matrices
// esto lo hace bastante mas comodo y practico de usar, en lugar de solo
// ser un algoritmo

printf("\nESTE PROGRAMA MULTIPLICA DOS MATRICES, LA PRIMERA DE : %d POR %d", M, N);
printf(" Y LA SEGUNDA DE %d POR %d. SI QUIERE MODIFICAR RENGLONES Y ", N, P);
printf(" COLUMNAS, CAMBIE LAS VARIABLES SIMBOLICAS M, N & P EN EL CODIGO.\n");
printf("\nAQUI SE RECIBEN LOS ELEMENTOS DE LA PRIMERA MATRIZ.\n");

for ( i = 0; i < M; i++)
{ // Abre primer for
for ( j = 0; j < N; j++)
{ // abre segundo for

printf("\nIntroduzca la entrada (%d,%2d) para la primera matriz \n", i, j);
scanf("%d", &Matriz1[i][j]);

} // Cierra segundo for
} // Cierra primer for

// Se define una matriz de N filas por P columnas
// La segunda matriz no es totalmente arbitraria. Se requiere que tenga tantos
// renglones como columnas tiene la primera

int Matriz2[N][P] = {{ 5}};

printf("\nAQUI SE RECIBEN LOS ELEMENTOS DE LA SEGUNDA MATRIZ:\n");

for ( i = 0; i < N; i++)
{ // Abre primer for
for ( j = 0; j < P; j++)
{ // abre segundo for

printf("\nIntroduzca la entrada (%d,%2d) para la segunda matriz \n", i, j);
scanf("%d", &Matriz2[i][j]);

} // Cierra segundo for
} // Cierra primer for

//Se define una matriz de M filas por P columnas
// La matriz producto es de el mismo numero de renglones que la primera
// y del mismo numero de filas que la segunda

int Matriz_Producto[M][P] = {{0}};

// EL ALGORITMO PRINCIPAL, NUCLEO DEL PROBLEMA
// Esta es la esencia del problema, lo demas es recibir e imprimir los
// resultados, lo cual no deja de ser laborioso. Esto es todo lo que se pide.
// Recuerdo que alguna vez en mi primer curso de programacion me pusieron
// este ejercicio en un examen. La clave consiste en hacer las cosas simples
// al principio. Se puede empezar por escribir el producto punto o interno
// de un par de vectores, uno fila y otro columna, eso incluye un ciclo for
// corriendo sobre M, el numero de columnas de la primera matriz y de
// filas de la segunda. Posteriormente hay que escribir el producto de un
// vector renglon por una matriz de N por P, con P arbitrario, esto incluye
// un par de ciclos for. Y por ultimo hay que dejar que en vez de un vector
// fila la multiplicacion sea de una matriz con M vectores fila de N entradas
// eso incluye un tercer ciclo for.
// La compejidad del programa debe valorarse por el numero de instrucciones
// aqui. La complejidad es O(MNP), lo cual es aproximadamente de O(n3)
// Desde luego, el programa sera mucho mas lento con la impresion y la
// recepcion de los numeros.



for ( k = 0; k < M; k++)
{ // abre primer ciclo for
for ( j = 0; j < P; j++)
{ // abre el segundo ciclo for

for ( i = 0; i < N; i++ )
Matriz_Producto[ k ][j ] += Matriz1[k][i]*Matriz2[i][j];

} // Cierra el segundo ciclo for
} // cierra primer ciclo for

// FIN DEL ALGORITMO PRINCIPAL

// Aqui se imprimen la dos matrices y la matriz producto

printf("\n\nAQUI SE IMPRIMEN LAS DOS MATRICES Y EL PRODUCTO: \n\n");
for ( i = 0; i < M; i++ )
{ // abre for que controla numero de renglones

// Este ciclo imprime la primera matriz
// No hay ningun problema para imprimir la primera matriz, ya que se
// trata de un par de ciclos for. Sin embargo se quiere imprimir las
// tres matrices, lo cual hace un poquito mas complicado el asunto.
// De todas formas la primera se imprime renglon por renglon
// solo que antes de pasar al siguiente renglon, se escriben las entradas
// correspondientes de la segunda y tercera matrices.

for ( k = 0; k < N; k++)
{ // Abre ciclo for
printf("%3d", Matriz1[i][k]);
// Se imprime el renglon i de la matriz 1
} //Cierra ciclo for

printf("\t\t"); // Esta instruccion separa una matriz de otra

// Este ciclo imprime la segunda matriz

for ( j = 0; j < P; j++)

{ // abre for

if ( i <= (N - 1)) // El numero de columnas de la segunda matriz puede ser
// menor o mayor que el numero de filas de la primera
// Si es mayor no pasa nada, pero si es menor se estara
// haciendo referencia a un elemento inexistente en el arreglo
// El caso en el que N > M se trata fuera del ciclo controlado por i
// El -1 es debido a que i empieza a correr en cero

printf("%3d", Matriz2[i][j]); // se imprime el renglon i de la matriz 2

else // De lo contrario solo se imprimen 3 espacios en blanco
     // correspondientes con 3d

printf(" ");

} // Cierra for

printf ("\t\t"); // Esta instruccion separa la matriz 2 de la matriz
                 // producto

// Este es el ciclo que imprime la matriz producto

for ( j = 0; j < P; j++ )
{ // abre for
printf("%3d", Matriz_Producto[i][j]);
// se imprime el renglon i de la matriz producto
} // Cierra for

printf("\n");

// Aqui se cambia de renglon

} // Cierra for que controla numero de renglones


// Es probable que N > M, por lo cual en el ciclo anterior no se
// imprimiria la segunda matriz en su totalidad
// Con el siguiente bloque se imprime lo que falta

if ( N > M)
{ // Abre if

int l = M;

while ( l < N )
{ // Abre while

for ( i = 0; i < N; i++)
printf(" ");

printf("\t\t\t");      

for ( j = 0; j < P; j++ )
printf("%3d", Matriz2[l][j]);

printf("\n"); // Aqui se cambia de linea
l++; // Se incrementa el numero de linea

} // Cierra while

} // Cierra if

} // Cierra la funcion Multiplicacion_Matrices


//////////////////////////////////////////////////////////
// MAIN
/////////////////////////////////////////////////////////

int main()

{

Multiplicacion_Matrices();

return 0;
}


/* Defectos en el programa: Como se menciono, la funcion Multiplicacion esta
muy llema de bloques, seria preferible reescribir su contenido en varias
funciones menores.
A la hora de imprimir se ha supuesto que el numero de entradas es chico
comparado con el tamanio de la pantalla. Si se trabaja con matrices en las
que N, M y P sean muy grandes, en realidad no saldra nada util en la pantalla.
De la misma manera si se toman numeros chicos pero con entradas de tres o
cuatro cifras*/