//Program for OBST#include<stdio.h>float e[6][6],w[6][6],t;int root[6][6];float p[6],q[6];void obst(int i, int j){ int value = root[i][j]; if(i==value) { printf("left child of k%d is d%d\n",value,value-1); } else { printf("left child of k%d is k%d\n",value,root[i][value-1]); obst(i,value-1); } if(j==value) { printf(" right child of k%d is d%d\n",value,value); } else { printf(" right child of k%d is k%d\n",value,root[value+1][j]); obst(value+1,j); }}int main(){p[1]=0.15;p[2]=0.10;p[3]=0.05;p[4]=0.10;p[5]=0.2;q[0]=0.05;q[1]=0.10;q[2]=0.05;q[3]=0.05;q[4]=0.05;q[5]=0.1;int l,i,n=5,r,j;for(i=1;i<=(n+1);i++){ e[i][i-1]=q[i-1]; w[i][i-1]=q[i-1];}for(l=1;l<=n;l++){ for(i=1;i<=(n-l+1);i++) { j=i+l-1; e[i][j]=10000; w[i][j]=w[i][j-1]+p[j]+q[j]; for(r=i;r<=j;r++) { t=e[i][r-1]+e[r+1][j]+w[i][j]; if(t<e[i][j]) { e[i][j]=t; root[i][j]=r; } } }}printf("w :\n");for(i=1;i<=(n+1);i++){ for(j=i-1;j<=(n);j++) { printf("%f ",w[i][j]); } printf("\n");}printf("e:\n");for(i=1;i<=(n+1);i++){ for(j=i-1;j<=n;j++) { printf("%f ",e[i][j]); } printf("\n");}printf("Root \n");for(i=1;i<=n;i++){ for(j=i;j<=n;j++) { printf("%d ",root[i][j]); } printf("\n");}printf("Root is k%d\n",root[1][n]);obst(1,n);} Output:
Comments
Post a Comment