obst.cpp

Optimal binary search tree

#include<stdio.h>
#include<conio.h>
main()
{
int n,i,j,d,k,R[100][100],kmin,s;
float P[100],A[100][100],minval,sum;



clrscr();


printf("Enter Nunber of keys : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter probability of key %d : ",i+1);
scanf("%f",&P[i]);
}



for(i=0;i<=n;i++)
{
 for(k=0;k<=n;k++)
 {
 A[i][k]=0.0;
 R[i][k]=0;
 }
}


for(i=0;i<n;i++)
{
A[i][i]=0;
//printf("\n%f",A[i][i]);
A[i][i+1]=P[i];
//printf("\n%f",A[i][i+1]);
R[i][i]=i;
//printf("\n%d",R[i][i]);
}


A[i+1][i+1]=0;

printf("\n\n\n");

for(i=0;i<n;i++)
{
printf("\t%3.2f",P[i]);
}

printf("\n\n");

for(i=0;i<=n;i++)
{
 for(k=0;k<=n;k++)
 {
 printf("\t%3.2f",A[i][k]);

 }
printf("\n");

}
///////////////////////////////////////////////////

for(d=1;d<n-1;d++)
{
for(i=1;i<n-d;i++)
  {
    j=i+d;
    minval=1000.0;
    for(k=i;k<=j;k++)
    { if ((A[i-1][k-1]+A[k][j])<minval )
	 { minval=A[i-1][k-1]+A[k][j];
	  kmin=k;}


     }
     R[i][j]=kmin;
     sum=P[i-1];
     for(s=i;s<j;s++)
     {
      sum=sum+P[s];
     }
   A[i-1][j]=minval+sum;

  }

}

//////////////////////////////////////////////////////////

printf("\n\n");

for(i=0;i<=n;i++)
{
 for(k=0;k<=n;k++)
 {
 printf("\t%3.2f",A[i][k]);

 }
 printf("\n");

}


getch();
return(0);
}