Árbol Binario de Huffman

Y para redondear el día, os dejo para que echéis un vistazo el algoritmo del árbol binario de Huffman. En C y de forma dinámica. Hasta luego!!!

#include <iostream.h>
#include <stdio.h>
#include <conio.h>

const int maxsize = 100;
const int null = 0;

struct huff_node
{
  char symbol;
  int freq;
  huff_node *parent;
  char childtype;
};

typedef huff_node *ptr;
ptr node[maxsize];

void create(int k); 
void print(int k);    
void twosmall(ptr &p, ptr &q, int numnode);   
                                              
                                             

int main()
{
  int numsymbols;
  ptr p, q, r;
  cout << "Introduce el numero de simbolos: ";
  cin >> numsymbols;
  for (int i = 0; i < numsymbols; i++)
    create(i);


  for (int j = numsymbols; j < 2*numsymbols - 1; j++)
    {
      r = new huff_node;
      node[j] = r;
      r->parent = null;
      twosmall(p, q, j);  
      p->parent = r;
      q->parent = r;
      p->childtype = 'L';
      q->childtype = 'R';
      r->symbol = ' ';
      r->freq = p->freq + q->freq;
    }
  cout << endl << endl;
  cout <<"simbolo-codigo: " << endl;
  for (int k = 0; k < numsymbols; k++)
    print(k);
    getch();
  return 0;
}

void create(int k)
{
  ptr t = new huff_node;
  cout << "introduce el simbolo numero " << k+1 << ": ";
  cin >> t->symbol;
  cout << "introduce su frecuencia: ";
  cin >> t->freq;
  t->parent = null;
  node[k] = t;
}

void print(int k)
{
  ptr t = node[k];
  char code[10];
  int size = 0;
  cout << t->symbol << " - ";

  while (t->parent != null)
    {
      if (t->childtype == 'L')
    code[size] = '0';
      else
    code[size] = '1';
      t = t->parent;
      size++;
    }

  for (int j = size-1; j >= 0; j--)
    cout << code[j];
  cout << endl;
}

void twosmall(ptr &p, ptr &q, int numnodes)
{
  int min1 = 9999;
  int min2 = 9999;
  p = null;
  q = null;

  for (int i = 0; i < numnodes; i++)
    {
      if (node[i]->parent == null)
    {
      if (node[i]->freq < min1)
        {
          min2 = min1;
          min1 = node[i]->freq;
          q = p;
          p = node[i];
        }
      else
        if (node[i]->freq < min2)
          {
        min2 = node[i]->freq;
        q = node[i];
          }
    }
    }
}

Algoritmo de Floyd

Os dejo el algoritmo de Floyd, para el que lo necesite. Esta realizado de forma dinámica en C. Espero que os sea útil!!!

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define max 50

int floyd(int matriz[max][max],int n);

int  main(){
     int n,i,j;
     int matriz[max][max];
   printf("\n PROBLEMA DE FLOYD");
   printf("\n\n Introduce el valor de nodos: ");
   scanf("%d",&n);
   for (i=0;i<n;i++){
      for (j=0;j<n;j++){
         printf(" Introduce el peso entre los nodos [%d][%d]:  ",i,j);
         scanf("%d",&matriz[i][j]);
         }
      }
   floyd(matriz,n);
   printf("\n");
   printf("\n");
   system("pause");
   return 1;
}

int floyd(int matriz[max][max],int n){
    int i,j,k;
    int mat[n][n],resul[n][n];
    for (i=0;i<n;i++){
        for (j=0;j<n;j++){
            mat[i][j]=matriz[i][j];
        }
    }
    for (i=0;i<=n;i++){
        for (j=0;j<n;j++){
            for (k=0;k<n;k++){
                if (mat[i][j]<(mat[i][k]+mat[k][j]))
                   mat[i][j]=mat[i][j];
                   else
                   mat[i][j]=(mat[i][k]+mat[k][j]);
            }
        }
    }
    printf("La matriz resultante (minima) es:\n");
    for (i=0;i<n;i++){
        for (j=0;j<n;j++){
            printf("%d  ",mat[i][j]);
        }
        printf("\n");
    }
}

Algoritmo de los almacenes

Trata sobre el problema de donde situar unos almacenes para que sea óptimo para un número de ciudades situadas en ciertas coordenadas. Realizado mediante algoritmo voraces con un coste O(n^3).

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 9999999
#define MIN -999
struct ciudad{
       int x;
       int y;
       int poblacion;
       };
      
float calcdistancia(int x, int y, int n, struct ciudad city[]);
void inicializar(int *xini, int *yini, int *xfin, int *yfin, float *distanciaSolucion);
int main(int argc, char *argv[]){
int n;
int xini, yini, xfin, yfin;
float distanciaSolucion, distancia=MAX,solX,solY;
printf("PROBLEMA DE LOS ALMACENES \n\n\n");
printf("Introduce el numero de ciudades del sistema: ");
scanf("%d",&n);
struct ciudad city[n];
int i;
for(i=0; i<n; i++){
         printf("\nIntroduce las coordenadas para la ciudad %d \n",i+1);
         printf(" Coordenada x "); scanf("%d",&city[i].x);
         printf(" Coordenada y "); scanf("%d",&city[i].y);
         printf(" Numero de habitantes aproximado "); scanf("%d",&city[i].poblacion);
         }
        
inicializar(&xini, &yini, &xfin, &yfin, &distanciaSolucion);
i=0;
for(i=0; i<n; i++){
         if(city[i].x <xini) xini=city[i].x;
         if(city[i].y <yini) yini=city[i].y;
         if(city[i].x >xfin) xfin=city[i].x;
         if(city[i].y >yfin) yfin=city[i].y;
}
int h;
for (h=xini; h<=xfin; h++){
    int j;
    for (j=yini; j<=yfin; j++){
        float distanciaActual = calcdistancia(h, j, n, city);
        if (distanciaSolucion > distanciaActual){
           distanciaSolucion = distanciaActual;
           solX = h;
           solY = j;
        }
    }
}
printf("\n\n");
printf("\nLas Coordenadas optimas para el almacen son, x %f y %f\n", solX, solY, distanciaSolucion);

system("PAUSE");
return 1;
}

void inicializar(int *xini, int *yini, int *xfin, int *yfin, float *distanciaSolucion){
     *xini=MAX;
     *yini=*xini;
     *xfin=MIN;
     *yfin=*xfin;
     *distanciaSolucion=MAX;
}
float calcdistancia(int x, int y, int n, struct ciudad city[]){
      float d=0;
      int i;
      for(i=0; i<n; i++)
               d +=sqrt(pow((x-city[i].x),2) + pow((y -city[i].y), 2))* city[i].poblacion;
      return d;
}

Algoritmo de las Monedas

Hoy os dejo el algoritmo típico de los Voraces, el problema del cambio de monedas. Espero que os resulte útil!


#include <stdio.h>
#include <stdlib.h>
float datos();
void calcular(float devolver,int cambio[15], float monedas[15]);
int main(int argc, char *argv[]){
    float monedas[] = {500, 200, 100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01};
    int cambio[]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    float devolver;
    printf("Introduce el importe que debemos devolver ");
    scanf("%f",&devolver);
    printf("\n %f",devolver);
    calcular(devolver, cambio, monedas);
    printf("\n");
    for(int i=0;i<15;i++)
            printf("\n Monedas de %.2f = %d ",monedas[i],cambio[i]);
    printf("\n");           
    system("PAUSE");
    return 1;
       
}
void calcular(float devolver, int cambio[15], float monedas[15]){
     int i=0;
     while(devolver>0){
           if(monedas[i]<=devolver){
               devolver-=monedas[i];
               cambio[i]++;                  
                       }
           else i++;
     }
}

Algoritmo de Dijkstra

Os dejo el algoritmo de Dijkstra en C, realizado por el método de los algoritmos Voraces. Espero que os sesa útil!!

#include <stdio.h>
#include <stdlib.h>
#define MAX 7
#define DISTMAX 998
int seleccionados(int *selec){
    int i;
    for(i=0;i<MAX;i++)
        if(selec[i]==0)
            return 0;
    return 1;
}
void shortpath(int coste[][MAX],int *ant,int *distancia){
    int selec[MAX]={0};
    int actual=0,i,k,dc,menordist,nuevadist;
    for(i=0;i<MAX;i++)
       distancia[i]=DISTMAX;
    selec[actual]=1;
    distancia[0]=0;
    actual=0;
    while(!seleccionados(selec)){
        menordist=DISTMAX;
        dc=distancia[actual];
        for(i=0;i<MAX;i++){
                          if(selec[i]==0){
                                          nuevadist=dc+coste[actual][i];
                                          if(nuevadist<distancia[i]){
                                                                  distancia[i]=nuevadist;
                                                                  ant[i]=actual;
                                                                  }//if
                                            if(distancia[i]<menordist){
                                                                      menordist=distancia[i];
                                                                      k=i;
                                            }//if(disstance..
                          }//if(selec..
        }//for
        actual=k;
        selec[actual]=1;
   }
}
int main(){
    //Inicializamos
    int coste[MAX][MAX]={{DISTMAX,2,4,7,DISTMAX,5,DISTMAX},{2,DISTMAX,DISTMAX,6,3,DISTMAX,8},{4,DISTMAX,DISTMAX,DISTMAX,DISTMAX,6,DISTMAX},{7,6,DISTMAX,DISTMAX,DISTMAX,1,6},{DISTMAX,3,DISTMAX,DISTMAX,DISTMAX,DISTMAX,7},{5,DISTMAX,6,1,DISTMAX,DISTMAX,6},{DISTMAX,8,DISTMAX,6,7,6,DISTMAX}};
    printf("\n Vamos a mostrar el arbol");
    for(int j=0;j<MAX;j++){
            printf("\n\n");
        for (int h=0;h<MAX;h++)
                 printf("\norigen %d   destino %d coste %d ", j,h,coste[j][h]);
                 //   coste %d ", j,h,coste[j][h]);
                 }
       
    int i,ant[MAX]={0},distancia[MAX];
    shortpath(coste,ant,distancia);
    printf("\n");
    for(i=0;i<MAX;i++)
       printf("\nEl coste al nodo %d es %d\n",i,distancia[i]);
    printf("\n");
    system("PAUSE");
    return 0;
}

Elemento Mayoritario en un Vector

Os dejo el algoritmo para saber si hay algún elemento mayoritario en un vector. Es un ejemplo sencillo, se puede modificar la forma de conseguir el vector. Yo lo tengo para un problema que era "PROBLEMA DE RODAMIENTOS". Está realizado por el método de Divide y Vence en C. Espero que os sea útil.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
bool xmayoritario (float T [MAX] , float x );
float buscar (float T[MAX]);
int main(int argc, char *argv[])
{
float arrayM[MAX],arrayNM[MAX];
arrayM[0]=1.6;
arrayNM[0]=1.1;
arrayM[1]=1.6;
arrayNM[1]=2.2;
arrayM[2]=1.4;
arrayNM[2]=3.3;
arrayM[3]=1.6;
arrayNM[3]=4.4;
arrayM[4]=1.1;
arrayNM[4]=5.5;
int i;
printf("PROBLEMA DE LOS RODAMIENTOS \n\n");
printf("\nLos rodamientos de la caja 1 tienen el siguiente tamaño\n");
for (i=0;i<MAX;i++){
    printf("\n %f",arrayM[i]);
}
printf("\n\nLos rodamientos de la caja 2 tienen el siguiente tamaño\n\n");
for (i=0;i<MAX;i++){
    printf("\n %f",arrayNM[i]);
}
float solok=buscar(arrayM);
if (solok>0){
   printf("\n\nSe ha encontrado el tamaño de un rodamiento mayoritario en la caja 1 y es: %f\n\n",solok);
   }else{
        printf("\n\nNo hay tamaño de rodamiento mayoritario en la caja 1\n\n");
        }
solok=buscar(arrayNM);
if (solok>0){
   printf("\n\nSe ha encontrado el tamaño de un rodamiento mayoritario en la caja 2 y es: %f\n\n",solok);
   }else{
         printf("\n\nNo hay tamaño de rodamiento mayoritario en la caja 2\n\n");
         }
system("PAUSE");
return 0;
}
bool xmayoritario (float T [MAX] , float x ){
     int k=0;
     int j;
     for (j=0;j<MAX;j++)
     if(T[j]==x)
                k++;
     return(k>=MAX/2);
}

float buscar(float T[MAX]){
      int i;
      for (i=0;(i<MAX/2);i++)
          if (xmayoritario (T ,T[i]))
             return T[i];
      return -1;
}

MergeSort

Algoritmo de búsqueda de un elemento en un Vector mediante Merge-Sort. El método es Divide y Vence, y está realizado en C.

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[])
{
    int x1=0, x2=0, x3=0;

    while (x1<n1 && x2<n2) {
        if (arreglo1[x1]<arreglo2[x2]) {
            arreglo3[x3] = arreglo1[x1];
            x1++;
        } else {
            arreglo3[x3] = arreglo2[x2];
            x2++;
        }
        x3++;
    }
    while (x1<n1) {
        arreglo3[x3] = arreglo1[x1];
        x1++;
        x3++;
    }
    while (x2<n2) {
        arreglo3[x3] = arreglo2[x2];
        x2++;
        x3++;
    }
}

void mezcla(int vector[], int n)
{
    int *vector1, *vector2, n1, n2,x,y;
    if (n>1)
    {
        if (n%2 == 0)
            n1=n2=(int) n / 2;
        else
        {
            n1=(int) n / 2;n2=n1+1;
        }
        vector1=(int *) malloc(sizeof(int)*n1);
        vector2=(int *) malloc(sizeof(int)*n2);
        for(x=0;x<n1;x++)
            vector1[x]=vector[x];
        for(y=0;y<n2;x++,y++)
            vector2[y]=vector[x];
        mezcla(vector1, n1);
        mezcla(vector2,n2);
        mezclar(vector1, n1, vector2, n2, vector);
        free(vector1);
        free(vector2);
    }     
}
void printlist(int vector[],int n)
{
   int i;
   for(i=0;i<n;i++){
      cout<< vector[i]<<"\t";
      }
      cout<<endl<<endl;
}

int main(){
    int i, vector[max];
    int n;
   
    cout<<"Introduce el número de elementos del vector :"<<endl;
    cin>>n;
  
    for(i=0;i<n;i++)
    {
       cout<<" vector["<<i+1<<"]=";
       cin>>vector[i];
    }
  
    cout<<"El vector introducido es:"<<endl;
    printlist(vector,n);
  
    mezcla(vector,n);

    cout<<"El vector ordenado mediante el método de mezclar es:"<<endl;
    printlist(vector,n); //imprimir la lista
   
    system("pause");
    return 0;
}

QuickSort

Algoritmo para ordenar un vector. Método mediante Divide y Vence realizado en C. Espero que sea útil!!

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
int pivote(int i,int j )
{
   return((i+j) /2);
}
void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = pivote(m,n);
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
      swap(&list[m],&list[j]); //Intercambiar elementos
      quicksort(list,m,j-1); //Llamadas recursivas para ordenar la primera mitad
      quicksort(list,j+1,n); //Llamada ercursiva para ordenar la segunda mitad
   }
}
void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++){
      cout<< list[i]<<"\t";
      }
      cout<<endl<<endl;
}
int main(int argc, char *argv[])
{
   int n;
   int list[max];
   int i = 0;
   cout<<"Introduce el número de elementos del vector :"<<endl;
   cin>>n;
  
   for(i=0;i<n;i++)
   {
       cout<<" list["<<i+1<<"]=";
       cin>>list[i];
   }
   cout<<"El vector introducido es:"<<endl;
   printlist(list,n);
  
 
   quicksort(list,0,n-1); //ordenar la lista
  
   cout<<"El vector ordenado mediante el método quicksort es:"<<endl;
   printlist(list,n); //imprimir la lista
   system ("pause");
   return EXIT_SUCCESS;
}

Búsqueda en un vector con coste Logarítmico O(log n)

Hoy os dejo un algorítmico el cual realiza una búsqueda en función de la posición de un vector con coste logarítmico. Empleando el sistema de Divide y Vence y en lenguaje de programación C. Espero que os sea útil!

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

int Selec(int a[], int k, int n);
int main(int argc, char *argv[]){
    int i,elem,array[12]={47,23,2,7,1,31,15,20,9,5,16,17},d;
    printf("\n PROBLEMA DE SELECCION DE ELEMENTOS \n");
    printf("\n");
    for (i=0;i<12;i++){
        printf(" %d",array[i]);
        }
    printf("\n\n Introduzca la posicion k: ");
    scanf("%d",&elem);
    printf(" \n Se ha seleccionado la posicion %d\n",elem);
    d=Selec(array,elem,12);
    printf("\n En el vector ordenado en la posicion %d esta %d",elem,d);
    printf("\n");
    system("PAUSE");
    return 1;
}

int Selec(int a[], int k, int n){
    int pri,u,v;
    pri=a[0];
    u=0;v=0;
    int m;
    int i;
    for(i=0;i<n;i++){
                     if (a[i]<pri) u++;
                     if (a[i]<=pri) v++;
    }
    if (k<=u){
       int j=0;
       int t[n];
       int h;
       for(h=0;h<n;h++){
                        if(a[h]<pri)
                                    t[j++]=a[h];
                                    }
                        return (Selec(t,k,j));
                        }
       if (k<=v){ return pri;}
       else {
            int t[n],j=0;
            int g;
            for(g=0;g<n;g++){
                             if(a[g]>pri) t[j++]=a[g];
                             }
            return (Selec(t,k-v,j));
            }
}

Búsqueda Binaria y Terciaria en C

Para empezar, os muestro algo sencillito como es realizar una búsqueda binaria y terciaria en un vector por el método de Divide y Vence, el lenguaje empleado para este algoritmo es C. Espero que os sea útil! Como veréis primero hay que introducir el vector y ordenarlo, después en el main comentas el método de búsqueda que quieras emplear y listo!

#include <cstdlib>
#include <iostream>
#define max 100
using namespace std;
void introducirVector(float A[max],int n)
{
 int i;
  for(i=0;i<n;i++)
  {
       cout<<" A["<<i+1<<"]=";
       cin>>A[i];
  }
  cout<<endl;
}
void mostrarVector(float V[max],int n)
{
   int i;
    for(i=0;i<n;i++)
   {
        cout<< V[i]<<"\t";      
   }
   cout<<endl<<endl;
}
//Con este método ordenaremos el vector previamente a la búsqueda//
void ordenarSeleccion(float V[max],int n)
{
   int i,j,k;
   float temp;
    for(i=0;i<n-1;i++)
    {        k=i;         
             temp=V[i];
             for(j=i+1;j<n;j++)
             {   if(V[j]<temp) //Intercambio
                   {  k=j;
                      temp=V[j];
                    }     
             }
             V[k]=V[i] ;
             V[i]=temp;                  
    }
}
//Busqueda de un elemento en el vector//
int  busquedaBinaria(float V[max],int n ,int dato)
{
  int mitad,izq,der;
  izq=0;
  der=n-1;
  while(izq<=der)
    {mitad=(izq+der)/2;//elemento central del vector para dividirlo
    if(dato>V[mitad])        
     izq=mitad+1;
    else if(dato<V[mitad])
    der=mitad-1;
    else return mitad;
     }
  return -1;//En caso de que no se encuentre
}
int  busquedaTerciaria(float V[max],int prim, int n ,int dato)
{
     int izq,der,nterc;
     izq=prim;
     der=n;
     cout<<"0izq vale"<<izq<<endl;
     cout<<"0der vale"<<der<<endl;
     if (izq>=der){
        V[der]=dato;
        return der;
     }
     nterc=(der-izq+1)/3;//dividimos por un tercio
     cout<<"nterc vale"<<nterc<<endl;
     cout<<"dato vale"<<dato<<endl;
     system("pause");
     if(dato==V[nterc]){
      return nterc; }
       else if(dato<V[nterc]){ 
         cout<<"1izq vale"<<izq<<endl;
         cout<<"1der vale"<<der<<endl;         
         busquedaTerciaria(V,izq,nterc,dato);
         }
       else if(dato==V[der-nterc])
         return der-nterc;
       else if(dato<V[der-nterc]){   
         cout<<"2izq vale"<<izq<<endl;
         cout<<"2der vale"<<der<<endl;
         busquedaTerciaria(V,izq+nterc+1,der-nterc-1,dato);
         }
         else
           cout<<"3izq vale"<<izq<<endl;
           cout<<"3der vale"<<der<<endl;
           busquedaTerciaria(V,der-nterc+1,der,dato);
           }
int main(int argc, char *argv[])
{
     float A[max];
     int n,p=0,dato;
     int pos;
     cout<<"Introduce el número de elementos del vector :";
     cin>>n;
     introducirVector(A,n);
     cout<<"El vector introducido es:"<<endl;
     mostrarVector(A,n);
     ordenarSeleccion(A,n);
     cout<<"El vector ordenado:"<<endl;
     mostrarVector(A,n);
     cout<<"Introduzca el número a buscar:";
     cin>>dato;
     pos=busquedaTerciaria(A,1,n,dato);
     //pos=busquedaBinaria(A,n,dato);
     {  if(pos ==-1)
           cout<<"el dato no esta en el vector"<<endl;
        else
        cout<<"El número se encontro en la posicion:"<<pos +1<<endl;
     }
    system("PAUSE");
   return EXIT_SUCCESS;
}

Presentación

Para empezar el Blog, comentar que soy un Ingeniero que me dedico a programar, como muchos de vosotros seréis o acabaréis siendo jeje. Iré colgando algoritmos en función del tiempo del que disponga y los conocimientos que tenga. Si alguno necesita alguna ayuda simplemente dejar vuestro comentario y cuando pueda contestaré. Un saludo

PD.: La mayoría de los algoritmos están hechos por mi, por lo que seguramente sean mejorables. Por lo que podéis comentar las mejoras y se mira.