Á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;
}