Archive for the “Algoritmica” Category

Aquí en el propio blog ya tenía una entrada que explicaba como se multiplicaban las matrices en C, tanto de forma iterativa como recursiva, pero debido a las continuas actualizaciones y a los cambios que hice hace bastante tiempo en el blog, se perdieron y a día de hoy son…, imposibles de leer vaya.

El primer ejemplo que pondré será el iterativo, además de que nos servirá para aprender como se transforma un algoritmo iterativo con bucles, en uno recursivo en distintas funciones.

Empezamos teniendo dos matrices llamadas A y B, con las dimensiones AFxAC y BFxBC, y debemos de asegurarnos antes de que CA y FB son iguales, si no, no podríamos realizar la multiplicación.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void multiplicarIT(int ma[N][M], int mb[N][M], int mc[N][M], int fa, int cb, int ca)
{
int i, j, k, r, c;
 
for(i=0; i<fa; i++)
{
/* Realiza el producto de matrices y guarda
el resultado en una tercera matriz*/
for(j=0; j<cb; j++)
{
mc[i][j]=0;
for(k=0; k<ca; k++)
{
mc[i][j]=mc[i][j]+(ma[i][k]*mb[k][j]);
}
}
}
 
printf("Resultado: \n");
for (r=0 ; r<fa; r++)
{
for(c=0; c<cb; c++)
printf(" %2d ",mc[r][c]);
printf("\n");
}
}

Los dos primeros bucles for sirven para ir posicionandonos en el elemento de la matriz que vamos a obtener, es decir, determinar las dos coordenadas del elemento que formará la matriz final. El tercer bucle for sirve para realizar las multiplicaciones de todos los elementos que salen de dichar coordenadas.

La multiplicación iterativa no es muy dificil de codificar, teniendo claro el concepto de multiplicación de matrices, es fácil realizar la codificación.

Realizar la misma operación pero de forma recursiva sigue el mismo concepto que el anterior, tan solo, hay que traducir los bucles en 3 funciones para las llamadas recursivas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void primerFOR(int ma[N][M], int mb[N][M], int mc[N][M], int fa, int cb, int i)
{
 
    if(i>fa);
    else
    {
        segundoFor(ma,mb,mc, fa, cb, i, 0);
        primerFOR(ma,mb,mc,fa,cb,i+1);
    }
}
 
void segundoFor(int ma[N][M], int mb[N][M], int mc[N][M], int fa, int cb, int i, int j)
{
 
    if(j>fa);
    else
    {
        mc[i][j]=0;
        tercerFor(ma,mb,mc, fa, cb, i, j, 0);
        segundoFor(ma,mb,mc, fa, cb, i, j+1);
    }
 
}
 
void tercerFor(int ma[N][M], int mb[N][M], int mc[N][M], int fa, int cb, int i, int j, int k)
{
 
    if(k>cb);
    else
    {
        mc[i][j]+=ma[i][k]*mb[k][j];
        tercerFor(ma,mb,mc, fa, cb, i, j, k+1);
    }
}

Cada uno de los 3 bucles del iterativo, son una función, teniendo como caso base el límite del propio bucle. Las llamadas a las distintas funciones se hacen en orden, es decir, la primera función llamará a la segunda, y esta a la tercera, cuando la tercera acabe, se volverá a llamar a la segunda para mover el índice del segundo bucle, y así repetitivamente. Los índices se mueven en las llamadas a las funciones, ya que cada llamada será equivalente a una iteración de la función iterativa.

La operación de la multiplicación es la misma que en la iterativa.

Comments No Comments »

Con esta entrada vamos a aprender a realizar un simple ejercicio de recursividad en C. Este ejercicio consiste en la suma de los elementos de un vector (ordenado o sin ordenar) de forma recursiva en lenguaje C.

Recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas. Para que se entienda mejor a continuación se exponen algunos ejemplos:

* Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x – 1); como el tamaño de Factorial(x – 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

* Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)

Fuente: Wikipedia

Si alguien quiere saber más sobre la recursividad, puede leer el artículo entero en la wikipedia.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include
#include
 
int main()
{
    int n = 3;
    int t[] = {1,2,3,4};
 
    printf("Resultado de la suma recursiva: %d", sumaVector(t,n));
    return 0;
}
 
int sumaVector(int t[], int n){
    int r = 0;
 
    if(n==0){
        r += t[0];
    }else{
        r = t[n] + sumaVector(t,n-1);
    }
    return r;
}

Este es el codigo para la realización del ejercicio.

Este ejercicio no es nada complicado. El caso base es cuando llegamos al último elemento del vector, es decir, como vamos a empezar por el final (posición n-1), el final de la ejecución será cuando lleguemos al principio del vector (n=0).

Mientras no lleguemos al principio del vector, sumamos el elemento anterior al que estamos sumando restando en uno la posición (n-1) en la llamada recursiva.

Comments No Comments »

   Beat diabetes   Diabetes diet