Algoritmia/Apéndice B: implementación en C

De Wikilibros, la colección de libros de texto de contenido libre.

[editar] Introducción

[editar] Capítulo 3: divide y vencerás

[editar] Subvector de suma máxima

const int n=1000; //tamaño del vector (0..n-1)
typedef int Tvector[n];
//estructura del vector
struct vector{
       int ini;
       int fin;
       int suma;
};

vector subvector_optimo(Tvector v,int lon,int c,int f){
   //Variables locales
   vector izq,der,cent; //Se divide el vector en tres subvectores
   vector optimo; //valor devuelto por el metodo
   int m,i;
   int suma=0;
   int tamanio_izq,tamanio_der; /*tamaños del subvector izquierdo y 
   derecho respectivamente*/
   if(f-c+1<=lon){ /*Se comprueba si el vector tiene mayor longitud 
    que el subvector que se esta buscando si la longitud del vector
    es menor que la del subvector entonces se suman todas las 
    posiciones hasta el final del vector*/
         for(i=c;i<=f;i++){  //coste lineal
                suma=suma+v[i];
         };
         optimo.ini=c;       /*operaciones con coste cte*/
         optimo.fin=f;
         optimo.suma=suma;
   }
   else{ /*el vector tiene mayor longitud que la solicitada*/
               m=(c+f)/2; /*Se halla el punto medio del vector (coste cte)*/
               izq=subvector_optimo(v,lon,c,m);  //coste T(n/2)
               /*si el vector izquierdo es de menor longitud
               que "lon" entonces se amplia por la derecha hasta
               llegar a la longitud "lon" pasada por parametro*/
               tamanio_izq=izq.fin-izq.ini + 1;
               if(tamanio_izq< lon){
                    while(tamanio_izq<lon){
                           izq.fin++;
                           izq.suma+=v[izq.fin];
                           tamanio_izq++;
                    }
               }
               der=subvector_optimo(v,lon,m+1,f);    //coste T(n/2)
               /*si el vector derecho es de menor longitud que "lon"
               entonces se amplia por la izquierda hasta llegar
               a la longitud "lon" pasada por parametro*/
               tamanio_der=der.fin-der.ini + 1;
               if(tamanio_der< lon){
                       while(tamanio_der<lon){
                               der.ini--;
                               der.suma+=v[der.ini];
                               tamanio_der++;
                       }
               }
               cent=subvector_central(v,lon,c,f);
               /*Se calcula cual de los tres subvectores tiene 
               mayor suma*/
               /*Todas las operaciones son de coste cte*/
               if(izq.suma>=der.suma){
                       if(izq.suma>=cent.suma)
                               optimo=izq;
                       else optimo=cent;
               }
               else if (der.suma>=cent.suma)
                       optimo=der;
               else optimo=cent;
       };
       return optimo;
};//fin subvector_optimo

vector subvector_central(Tvector v,int lon,int c,int f){
  //variables locales
  int m,suma,suma_max;
  int inicio,final;/*variables que indican el inicio y el final del
  subvector pasando por el centro*/
  vector optimo;/*valor devuelto por el metodo*/
  m = (c+f)/2; //Se calcula el punto medio del vector
  suma_max=INT_MIN;   /*Se le asigna el minimo valor de los enteros 
                      para poder hacer las comparaciones
                       con "suma", ya que los elementos del vector
                      no valdran nunca el minimo el valor entero*/
  suma = 0;
  inicio = m-lon+1;
  final = m+lon-1;        /*operaciones con coste cte*/
  if (inicio < 0){
        inicio = 0; /*Se inicializa a cero para que no busque
                    en posiciones inexistentes en el vector*/
  };
  if (final > n-1){
       /*Si se le pasamos una longitud "lon" mas grande que la  
mitad del vector,tomando como posicion de inicio "m" nos pasaremos  
del rango del vector original. De ahi la asignacion "final = m+lon- 
1" que nos da el limite hasta donde podriamos calcular un subvector 
de longitud "lon" con inicio en el punto medio "m". Si "final" se
pasa del rango solo podremos calcular n-lon+1 subvectores de
longitud "lon", o lo que es lo mismo, solo podremos calcular  
subvectores con inicio entre 0 y n-lon.*/
 /*Calculamos el subvector maximo de forma iterativa*/
        for(int i=inicio; i<=n-lon ;i++){  //se hara n-lon-inicio+1 veces
               suma=0;
               for(int j=0;j<lon;j++){  //se hara lon veces
                      suma=suma+v[j+i];
               };
               if(suma>=suma_max){
                       suma_max=suma;
                       optimo.suma=suma_max;/*operaciones con coste cte*/
                       optimo.ini=i;
                       optimo.fin = optimo.ini+lon-1;
               };
        };
  }else{/* "final" cae dentro del rango del vector y por tanto se  
 pueden calcular todos los posibles subvectores de longitud "lon" 
 que pasen por el centro (m), incluidos los que tienen como inicio
 la mitad del vector (m).*/
 /*igual que en el otro caso, se calcula el subvector maximo de 
 forma iterativa*/
       for(int i=inicio; i<=m ;i++){  //se hara m-inicio+1 veces
               suma=0;
               for(int j=0;j<lon;j++){  //se hara lon veces
                       suma=suma+v[j+i];
               };
               if(suma>=suma_max){
                       suma_max=suma;
                       optimo.suma=suma_max; /*operaciones con
                                              coste cte*/
                       optimo.ini=i;
                       optimo.fin = optimo.ini+lon-1;
               };
       };
  };
  return optimo;
}//fin subvector_central