Cuestiones generales

La técnica de diseño de algoritmos llamada "divide y vencerás" (divide and conquer) consiste en descomponer el problema original en varios sub-problemas más sencillos, para luego resolver éstos mediante un cálculo sencillo. Por último, se combinan los resultados de cada sub-problema para obtener la solución del problema original. El pseudocódigo sería:

funcion divide_y_venceras_1(problema)
{
   descomponer el problema en n subproblemas más pequeños;
   para i=1 hasta n hacer
      resolver el subproblema k;
   combinar las n soluciones;
 }

Un ejemplo de "divide y vencerás" es la ordenación rápida, o quicksort, utilizada para ordenar arrays. En ella, se dividía el array en dos sub-arrays, para luego resolver cada uno por separado, y unirlos (ver algoritmos de ordenación). El ahorro de tiempo es grande: el tiempo necesario para ordenar un array de elementos mediante el método de la burbuja es cuadrático: kN². Si dividimos el array en dos y ordenamos cada uno de ellos, el tiempo necesario para resolverlo es ahora k(N/2)²+k(N/2)²=(kN²)/2. El tiempo necesario para ordenarlo es la mitad, pero sigue siendo cuadrático.

Pero ahora, si los subproblemas son todavía demasiado grandes, ¿por qué no utilizar la misma táctica con ellos, esto es, dividirlos a ellos también, utilizando un algoritmo recursivo (ver recursividad) que vaya dividiendo más el sub-problema hasta que su solución sea trivial? Un algoritmo del tipo:

funcion divide_y_venceras(problema)
{
   si el problema es trivial
      entonces resolver el problema;
   si no es trivial
   {
      descomponer el problema en n subproblemas más pequeños;
      para i=1 hasta n hacer
         divide_y_venceras(subproblema_k);
      combinar las n soluciones;
    }
 }

Si aplicamos este método al quicksort, el tiempo disminuye hasta ser logarítmico, con lo que el tiempo ahorrado es mayor cuanto más aumenta N.

Tiempo de ejecución

El tiempo de ejecución de un algoritmo de divide y vencerás, T(n), viene dado por la suma de dos elementos:

El tiempo que tarda en resolver los A subproblemas en los que se divide el original, A·T(n/B), donde n/B es el tamaño de cada sub-problema.

El tiempo necesario para combinar las soluciones de los sub-problemas para hallar la solución del original; normalmente es O(n^k)

Por tanto, el tiempo total es: T(n) = A·T(n/B) + O(n^k). La solución de esta ecuación, si A es mayor o igual que 1 y B es mayor que 1, es:

Determinación del umbral

Uno de los aspectos que hay que tener en cuenta en los algoritmos de divide y vencerás es dónde colocar el umbral, esto es, cuándo se considera que un sub-problema es suficientemente pequeño como para no tener que dividirlo para resolverlo. Normalmente esto es lo que hace que un algoritmo de divide y vencerás sea efectivo o no. Por ejemplo, en el algoritmo de ordenación quicksort, cuando se tiene un array de longitud 3, es mejor ordenarlo utilizando otro algoritmo de ordenación (con 6 comparaciones se puede ordenar), ya que el quicksort debe dividirlo en dos sub-arrays y ordenar cada uno de ellos, para lo que utiliza más de 6 comparaciones.

Problema de los puntos más cercanos

El problema es: "dado un conjunto de puntos P, hallar el par de puntos más cercanos". La distancia entre dos puntos i y j es sqrt[(x_i-x_j)²+(y_i-y_j)²]. Una primera solución podría ser mirar todos los pares de puntos y quedarse con el más pequeño; al haber n·(n-1)/2 pares de puntos, el tiempo de ejecución es de O(n²). El programa resultante es muy corto, y rápido para casos pequeños, pero al ser este procedimiento una búsqueda exhaustiva, debería haber un algoritmo más rápido.

Supongamos que ordenamos los puntos según la coordenada x; esto supondría un tiempo de O(n·log n), lo que es una cota inferior para el algoritmo completo. Ahora que se tiene el conjunto ordenado, se puede trazar una línea vertical, x = x_m, que divida al conjunto de puntos en dos: P_i y P_d. Ahora, o el par más cercano está en P_i, o está en P_d, o un punto está en P_i y el otro en P_d. Si los dos estuvieran en P_i o en P_d, se hallaría recursivamente, subdividiendo más el problema, por lo que ahora el problema se reduce al tercer caso, un punto en cada zona.

Llamemos d_i, d_d y d_c a las mínimas distancias en el primer caso, en el segundo, y en el tercero, respectivamente, y d_min al menor de d_i y d_d. Para resolver el tercer caso, sólo hace falta mirar los puntos cuya coordenada x esté entre x_m-d_min y x_m+d_min. Para grandes conjuntos de puntos distribuidos uniformemente, el número de puntos que caen en esa franja es sqrt(n), así que con una búsqueda exhaustiva el tiempo de ejecución sería de O(n), y tendríamos el problema resuelto. El tiempo de ejecución sería, según lo dicho en el otro apartado, O(n·log n).

Pero si los puntos no están uniformemente distribuidos, la cosa cambia. En el peor de los casos, todos los puntos están en la franja, así que la fuerza bruta no siempre funciona en tiempo lineal. Para ello, se puede recurrir a ordenar los puntos de la franja según la coordenada y, lo que supone un tiempo de ejecución de O(n·log n). Si la coordenada y difiere en más de d_min, se puede pasar al siguiente punto. El tiempo de ejecución es O(max(n·log n,n·log n))=O(n·log n), con lo que mantenemos el tiempo de ejecución anterior. El programa sería:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX 110L // Número máximo de puntos.

struct punto // Estructura de un punto.
{
   double x;
   double y;
 };

void busca(struct punto *,int);
int ordenax(const void *,const void *);
double dist(struct punto,struct punto);

struct punto c1,c2; // Puntos más cercanos.
double mindist=1e10; // Mínima distancia.

int main()
{
   int a,num;
   double x,y;
   struct punto p[MAX];

   for(scanf(" %d",&num),a=0;a<num;a++) // Coge la entrada
   {
      scanf(" %lf %lf",&x,&y);
      p[a].x=x;
      p[a].y=y;
    }

   busca(p,num); // Hacer la primera búsqueda.

   printf("Distancia minima: %.3lf\n",mindist);
   printf("Puntos: (%.3lf,%.3lf) y (%.3lf,%.3lf)\n",c1.x,c1.y,c2.x,c2.y);

   return(0);
 }

void busca(struct punto *p,int num)
{
   double d;
   int desde,hasta,a,b;

   if(num<=1) // Si no hay pares de puntos:
      return; // salir.
   // Ordenar los puntos por la coordenada x.
   qsort(p,num,sizeof(struct punto),ordenax);
   // Mirar en el subconjunto de la izquierda.
   busca(p,num/2);
   // Mirar en el subconjunto de la derecha.
   busca(p+num/2,(num+1)/2);

   // Hallar los límites del conjunto central.
   for(desde=num/2; desde>0 && p[num/2].x-p[desde].x<mindist; desde--);
   for(hasta=num/2; hasta<num-1 && p[hasta].x-p[num/2].x<mindist; hasta++);
   
   // Búsqueda exhaustiva en el conjunto central.
   for(a=desde;a<=hasta;a++)
      for(b=a+1;b<=hasta;b++)
         if((d=dist(p[a],p[b]))<mindist)
         {
            mindist=d;
            c1.x=p[0].x;
            c1.y=p[0].y;
            c2.x=p[1].x;
            c2.y=p[1].y;
          }
 }

 // Función auxiliar del qsort.
int ordenax(const void *a,const void *b)
{
   return(((*(struct punto *)a).x<(*(struct punto *)b).x)?-1:1);
 }

 // Función que calcula la distancia entre dos puntos.
double dist(struct punto a,struct punto b)
{
   return(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
 }

Hallar la mediana de un conjunto de puntos

La mediana es el elemento de un conjunto que cumple que en el conjunto hay el mismo número de elemntos mayores que él y menores que él. Dicho de otra forma, si el conjunto está ordenado, la mediana es el elemento central. Una forma de resolverlo es esa, ordenar el conjunto y localizar el elemnto central. El tiempo de ejecución sería de O(n·log n), pero, ¿se podría resolver en tiempo lineal utilizando una estrategia de divide y vencerás?

Hay un método llamado selección rápida que tiene un tiempo esperado lineal, pero que en algunos casos puede tener tiempo O(n²). Este método no sólo puede hallar la mediana, sino el elemento que ocupa la posición k-ésima. Para ello, se toma un elemento pivote (normalmente el primero), y se divide el conjuntos en dos sub-conjuntos, según los elementos sean mayores o menores que el pivote. El pivote ahora ocupará una posición p. Si p es igual a k, el número buscado es el pivote; si p es menor que k, el número buscado está en el primer subconjunto, y si p es mayor que k, el número buscado está en el segundo subconjunto. Este método se continua recursivamente, hasta que se halle el elemento buscado. El programa sería:

#include <stdio.h>
#include <stdlib.h>

int seleccionrapida(int *,int,int);

int k;

int main()
{
   int num,a,m;
   int *array;

   scanf(" %d",&num); // Pedir el tamaño del array
   array=(int *)malloc(sizeof(int)*num);
   for(a=0;a<num;a++) // Dar valores al array
      scanf(" %d",&array[a]);
   scanf(" %d",&k); // Pedir el valor k
   k--; // Por ir de 0 a num-1

   m=seleccionrapida(array,0,num-1); // Para llamar a la función

   printf("%d\n",m);

   return(0);
 }

int seleccionrapida(int *array,int desde,int hasta)
{
   int i,d,aux; // i realiza la búsqueda de izquierda a derecha
      // y j realiza la búsqueda de derecha a izquierda.

    for(i=desde+1,d=hasta; ; ) // Valores iniciales de la búsqueda.
    {
      for( ;i<=hasta && array[i]<=array[desde]; i++); // Primera búsqueda
      for( ;d>=0 && array[d]>=array[desde]; d--); // Segunda búsqueda
      if(i<d) // si no se han cruzado:
      {
         aux=array[i]; // Intercambiar.
         array[i]=array[d];
         array[d]=aux;
       }
      else // si se han cruzado:
         break; // salir del bucle.
    }
   if(d==desde-1) // Si la segunda búsqueda se sale del array
      d=desde; // es que el pivote es el elemento
         // más pequeño: se cambia con él mismo.
   aux=array[d]; // Colocar el pivote
   array[d]=array[desde]; // en su posición.
   array[desde]=aux;

   if(d==k)
      return(array[d]); // El pivote es el elemento buscado
   else if(d>k)
      return(seleccionrapida(array,desde,d-1)); // Buscar en el primer array.
   else
      return(seleccionrapida(array,d+1,hasta)); // Buscar en el segundo array.
 }

En esta solución en tiempo medio lineal se descartan sólo unos cuantos elementos cada vez que se llama a la función recursiva, dependiendo del pivote que elijamos. Para descartar una fracción constante de elementos (y mejorar el tiempo de ejecución del peor caso) habría que elegir un mejor pivote, a ser preferible la mediana (cosa que no puede ser, porque es justamente ella la que estamos buscando). Tampoco se puede perder mucho tiempo en buscar un buen pivote, porque haría demasiado lento el programa. Una opción sería elegir tres elementos y utilizar como pivote la mediana de esos tres, pero en el peor caso eso sigue siendo una mala opción. Hay un algoritmo de elección del pivote llamado "partición con base en la mediana de la mediana de cinco", que consiste en:

Se puede probar que, utilizando este método, y en el peor de los casos, cada llamada a la función recursiva desprecia a más del 30% de los elementos. Esto hace que el algoritmo de selección rápida sea lineal, a pesar de que utilizamos un algoritmo auxiliar para la búsqueda del pivote. El problema completo sería:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int seleccionrapida(int *,int *,int,int,int);
int hallamediana(int *,int *,int);

int main()
{
   int num,a,m,k;
   int *array,*pos;

   scanf(" %d",&num); // Pedir el tamaño del array
   array=(int *)malloc(sizeof(int)*num);
   for(a=0;a<num;a++) // Dar valores al array
      scanf(" %d",&array[a]);
   scanf(" %d",&k); // Pedir el valor k
   k--;

   pos=(int *)malloc(sizeof(int)*num);

   m=seleccionrapida(array,pos,0,num-1,k); // Para llamar a la función

   printf("%d\n",m);

   return(0);
 }

int seleccionrapida(int *array,int *pos,int desde,int hasta,int k)
{
   int i,d,aux; // i realiza la búsqueda de izquierda a derecha
      // y j realiza la búsqueda de derecha a izquierda.

   // Hallar la falsa mediana para tomarla como pivote
   for(i=desde;i<=hasta;i++)
      pos[i-desde]=i;
   d=hallamediana(array+desde,pos,hasta-desde+1);

   aux=array[d]; // Poner la falsa mediana al principio.
   array[d]=array[desde];
   array[desde]=aux;
   for(i=desde+1,d=hasta;;) // Valores iniciales de la búsqueda.
   {
      for(;i<=hasta && array[i]<=array[desde];i++); // Primera búsqueda
      for(;d>=0 && array[d]>=array[desde];d--); // segunda búsqueda
      if(i<d) // si no se han cruzado:
      {
         aux=array[i]; // Intercambiar.
         array[i]=array[d];
         array[d]=aux;
       }
      else // si se han cruzado:
         break; // salir del bucle.
    }
   if(d==desde-1) // Si la segunda búsqueda se sale del array
      d=desde; // es que el pivote es el elemento
         // más pequeño: se cambia con él mismo.
   aux=array[d]; // Colocar el pivote
   array[d]=array[desde]; // en su posición.
   array[desde]=aux;

   if(d==k)
      return(array[d]); // El pivote es el elemento buscado
   else if(d>k)
      return(seleccionrapida(array,pos,desde,d-1,k)); // Buscar en el primer array.
   else
      return(seleccionrapida(array,pos,d+1,hasta,k)); // Buscar en el segundo array.
 }

int hallamediana(int *array,int *pos,int num)
{
   int a,*array2,b,c,d;

   if(num<5) // Si hay menos de 5 elementos
      return(pos[0]); // vale el primero (lo que devuelve esta
             // función es el índice de la mediana en la variable "array" de la función
             // seleccionrapida que llama por primera vez a esta función.

   // Hallar la mediana de cada cinco elementos.
   array2=(int *)malloc(sizeof(int)*((num/5)+4));
   for(a=0;a+4<num;a+=5)
   {
      memcpy(array2+(a/5),array,sizeof(int)*5);
      for(b=0;b<5;b++)
         for(c=b+1;c<5;c++)
            if(array2[b]>array2[c])
            {
               d=array2[b];
               array2[b]=array2[c];
               array2[c]=d;
               d=pos[b];
               pos[b]=pos[c];
               pos[c]=d;
             }
      array2[a/5]=array[a+2];
      pos[a/5]=pos[a+2];
    }

   // Hallar la mediana de las medianas.
   a=hallamediana(array2,pos,num/5);
   free(array2);
   return(a);
 }

Multiplicación de matrices

Dadas dos matrices A y B de tamaño n x n, hallar C, el producto de las dos. Un primer algoritmo se saca de la definición de producto de matrices: C_{i j} es el producto escalar de la i-ésima fila por la j-ésima columna. Su tiempo de ejecución sería O(n³):

int i,j,k;
int A[n][n],B[n][n],C[n][n];

// Dar valores a A y B.

for(i=0;i<n;i++)
   for(i=0;i<n;i++)
   {
      C[i][j]=0;
      for(i=0;i<n;i++)
         C[i][j]+=A[i][k]*B[k][j];
    }

Pero este tiempo de ejecución también se puede mejorar. Si n es una potencia de 2, se pueden dividir A, B y C en cuatro submatrices cada una, de la forma:

Ahora, para hallar las submatrices de C, basta con utilizar que:

C_1,1 = A_1,1·B_1,1 + A_1,2·B_2,1
C_1,2 = A_1,1·B_1,2 + A_1,2·B_2,2
C_2,1 = A_2,1·B_1,1 + A_2,2·B_2,1
C_2,2 = A_2,1·B_1,2 + A_2,2·B_2,2

Con este método el tiempo de ejecución es de T(n) = 8·T(n/2) + O(n²), o lo que es lo mismo, O(n³), con lo que no habría diferencia entre este método y el primero propuesto. Hay que reducir el número de multiplicaciones por debajo de 8. Esto se logra utilizando el algoritmo de Strassen. Definimos las siguientes matrices:

M₁ = (A_1,2 - A_2,2)·(B_2,1 + B_2,2)
M₂ = (A_1,1 + A_2,2)·(B_1,1 + B_2,2)
M₃ = (A_1,1 - A_2,1)·(B_1,1 + B_2,1)
M₄ = (A_1,1 + A_1,2)·B_2,2
M₅ = A_1,1·(B_1,2 - B_2,2)
M₆ = A_2,2·(B_2,1 - B_1,1)
M₇ = (A_2,1 + A_2,2)·B_1,1

para las que se necesitan 7 multiplicaciones diferentes, y ahora se calculan las submatrices de C utilizando sólo sumas:

C_1,1 = M₁ + M₂ - M₄ + M₆
C_1,2 = M₄ + M₅
C_2,1 = M₆ + M₇
C_2,2 = M₂ - M₃ + M₅ - M₇

El nuevo tiempo de ejecución es de T(n) = 7·T(n/2) + O(n²), es decir, de T(n) = O(n^log₂7) = O(n^2.81). Este algoritmo sólo es mejor que el directo cuando n es muy grande, y es más inestable cuando se utiliza con números reales, por lo que tiene una aplicabilidad limitada.

Para el caso general en el que n no es potencia de 2, se pueden rellenar las matrices con ceros hasta que las dos matrices sean cuadradas y n sea una potencia de 2.

El programa queda así:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max(int,int);
int **multiplicamatriz(int **,int **,int); // Función recursiva que multiplica matrices
int **suma(int **,int **,int); // suma de matrices
int **resta(int **,int **,int);// Resta de matrices
void libera(int **,int); // Libera memoria

int main()
{
   int **mapa1,**mapa2,**sol;
   int f1,c1,f2,c2,a,b,m,m1;

   scanf(" %d %d",&f1,&c1); // Tamaño de la primera matriz
   scanf(" %d %d",&f2,&c2); // Tamaño de la segunda matriz
   m1=max(f1,max(c1,max(f2,c2)));

   for(m=1;m<m1;m*=2); // El tamaño de las matrices cuadradas a multiplicar
   //debe ser de la forma 2k, si no se completan con ceros.

   mapa1=(int **)malloc(sizeof(int *)*m); // Se crea la primera matriz
   for(a=0;a<m;a++)
   {
      mapa1[a]=(int *)malloc(sizeof(int)*m);
      memset(mapa1[a],0,sizeof(int)*m);
    }
   for(a=0;a<f1;a++) // Se cogen los datos de la primera matriz.
      for(b=0;b<c1;b++)
         scanf(" %d",&mapa1[a][b]);

   mapa2=(int **)malloc(sizeof(int *)*m); // Se crea la sedunda matriz.
   for(a=0;a<m;a++)
   {
      mapa2[a]=(int *)malloc(sizeof(int)*m);
      memset(mapa2[a],0,sizeof(int)*m);
    }
   for(a=0;a<f2;a++) // Se cogen los datos de la segunda matriz.
      for(b=0;b<c2;b++)
         scanf(" %d",&mapa2[a][b]);

   sol=multiplicamatriz(mapa1,mapa2,m); // Se multiplican.

   for(a=0;a<f1;a++) // Se imprime el resultado.
   {
      for(b=0;b<c2;b++)
         printf("%d ",sol[a][b]);
      printf("\n");
    }

   return(0);
 }

int max(int a,int b)
{
   return((a>b)?a:b);
 }

int **multiplicamatriz(int **mapa1,int **mapa2,int num)
{
   int **sol,**M[8],**f1,**f2,**aux,**aux2;
   int **A[2][2],**B[2][2],**C[2][2];
   int a,q,w,r;

   sol=(int **)malloc(sizeof(int *)*num);
   for(a=0;a<num;a++)
      sol[a]=(int *)malloc(sizeof(int)*num);

   if(num==1)
   {
      sol[0][0]=mapa1[0][0]*mapa2[0][0];
      return(sol);
    }
// Crear las submatrices de A y B.
   for(q=0;q<2;q++)
   {
      for(w=0;w<2;w++)
      {
         A[q][w]=(int **)malloc(sizeof(int *)*(num/2));
         for(a=0;a<num/2;a++)
         {
            A[q][w][a]=(int *)malloc(sizeof(int)*(num/2));
            for(r=0;r<num/2;r++)
               A[q][w][a][r]=mapa1[a+(num/2)*q][r+(num/2)*w];
          }

         B[q][w]=(int **)malloc(sizeof(int *)*(num/2));
         for(a=0;a<num/2;a++)
         {
            B[q][w][a]=(int *)malloc(sizeof(int)*(num/2));
            for(r=0;r<num/2;r++)
             B[q][w][a][r]=mapa2[a+(num/2)*q][r+(num/2)*w];
          }
       }
    }
// Hallar las matrices M.
   f1=resta(A[0][1],A[1][1],num/2);
   f2=suma(B[1][0],B[1][1],num/2);
   M[1]=multiplicamatriz(f1,f2,num/2);
   libera(f1,num/2);
   libera(f2,num/2);

   f1=suma(A[0][0],A[1][1],num/2);
   f2=suma(B[0][0],B[1][1],num/2);
   M[2]=multiplicamatriz(f1,f2,num/2);
   libera(f1,num/2);
   libera(f2,num/2);

   f1=resta(A[0][0],A[1][0],num/2);
   f2=suma(B[0][0],B[0][1],num/2);
   M[3]=multiplicamatriz(f1,f2,num/2);
   libera(f1,num/2);
   libera(f2,num/2);

   f1=suma(A[0][0],A[0][1],num/2);
   f2=B[1][1];
   M[4]=multiplicamatriz(f1,f2,num/2);
   libera(f1,num/2);

   f1=A[1][1];
   f2=resta(B[0][1],B[1][1],num/2);
   M[5]=multiplicamatriz(f1,f2,num/2);
   libera(f2,num/2);

   f1=A[1][1];
   f2=resta(B[1][0],B[0][0],num/2);
   M[6]=multiplicamatriz(f1,f2,num/2);
   libera(f2,num/2);

   f1=suma(A[1][0],A[1][1],num/2);
   f2=B[0][0];
   M[7]=multiplicamatriz(f1,f2,num/2);
   libera(f1,num/2);

// Hallar las submatrices de C.

   C[0][0]=suma(M[1],M[2],num/2);
   aux=C[0][0];
   C[0][0]=resta(C[0][0],M[4],num/2);
   aux2=C[0][0];
   C[0][0]=suma(C[0][0],M[6],num/2);
   libera(aux,num/2);
   libera(aux2,num/2);

   C[0][1]=suma(M[4],M[5],num/2);

   C[1][0]=suma(M[6],M[7],num/2);

   C[1][1]=resta(M[2],M[3],num/2);
   aux=C[1][1];
   C[1][1]=suma(C[1][1],M[5],num/2);
   aux2=C[1][1];
   C[1][1]=resta(C[1][1],M[7],num/2);
   libera(aux,num/2);
   libera(aux2,num/2);

   for(a=1;a<=7;a++)
      libera(M[a],num/2);
// Unir las submatrices de matrices C en sol.
   for(q=0;q<num;q++)
      for(w=0;w<num;w++)
         sol[q][w]=C[q/(num/2)][w/(num/2)][q%(num/2)][w%(num/2)];
// Liberar las submatrices de A, B y C.
   for(q=0;q<2;q++)
      for(w=0;w<2;w++)
      {
         libera(A[q][w],num/2);
         libera(B[q][w],num/2);
         libera(C[q][w],num/2);
       }

   return(sol);
 }

int **suma(int **mapa1,int **mapa2,int num)
{ // sumar mapa1 y mapa2.
   int a,b;
   int **sol;
   sol=(int **)malloc(sizeof(int *)*num);
   for(a=0;a<num;a++)
   {
      sol[a]=(int *)malloc(sizeof(int)*num);
      for(b=0;b<num;b++)
         sol[a][b]=mapa1[a][b]+mapa2[a][b];
    }
   return(sol);
 }

int **resta(int **mapa1,int **mapa2,int num)
{ // Restar mapa2 de mapa1.
   int **sol;
   int a,b;
   sol=(int **)malloc(sizeof(int *)*num);
   for(a=0;a<num;a++)
   {
      sol[a]=(int *)malloc(sizeof(int)*num);
      for(b=0;b<num;b++)
         sol[a][b]=mapa1[a][b]-mapa2[a][b];
    }
   return(sol);
 }

void libera(int **mapa,int num)
{
   int a;
   for(a=0;a<num;a++) // Liberar la tabla dinámica de 2D.
      free(mapa[a]);
   free(mapa);
 }

Multiplicación de dos enteros

Este problema apareció en la OIE'2000 y su solución más efectiva es la que utiliza la técnica "divide y vencerás".

El tamaño no es lo importante: Enunciado y Solución.

Ficheros

Multiplicación de matrices en C/C++: multmatrices.cpp