实验十.cpp

二分搜索

#include<stdio.h>
#define MAX 30                                   //假定的有序集的最大元素个数

double a[MAX+1],b[MAX+1];                        //储存集合S的存取概率分布
double m[MAX+1][MAX+1],w[MAX+1][MAX+1];          //m记录所求的最优值，w为分析中w(i,j)的概率和
int s[MAX+1][MAX+1];                             //保存最优子树T(i,j)的根结点中元素

void erfenjiansuo(int n)
{
	for(int i=0; i<=n; i++)
	{
		w[i+1][i] = a[i];                         //叶结点概率
 		m[i+1][i] = 0.0;                            //最优路线 m(i,i-1)=0
	}
	for(int r=0; r<n; r++)                        //i取值的右边界距离集合右边界的距离
	{
		for(int i=1; i<=n-r; i++)                 //i取值范围
		{
			int j=i+r;           
			w[i][j]=w[i][j-1]+a[j]+b[j];          //由w(i,j-1)计算w(i,j)
			m[i][j]=m[i+1][j];                    //选第i个元素为根时，没有左子树，只计算右子树贡献
			s[i][j]=i;         
			for(int k=i+1; k<=j; k++)             //选择根为xk的可能
			{
				double t=m[i][k-1] + m[k+1][j];   //选xk为根结点，左、右子树的贡献
				if(t<m[i][j])                     //如果当前选择的xk更优
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}	
			m[i][j]+=w[i][j];
		}
	}
}

void jiansuoshu(int n)
{
	for(int i=0; i<=n; i++)
	{
		w[i+1][i] = a[i];                         //叶结点概率
 		m[i+1][i] = 0;                           //最优路线
		s[i+1][i] = 0;
	}
	for(int r=0; r<n; r++)                       //i取值的右边界距离集合右边界的距离
	{
		for(int i=1; i<=n-r; i++)                //i取值范围
		{
			int j=i+r , i1, j1;     
			i1 = s[i][j-1]>i ? s[i][j-1] : i;
			j1 = s[i+1][j]<j ? s[i+1][j] : j;

			w[i][j]=w[i][j-1]+a[j]+b[j];        //由w(i,j-1)计算w(i,j)
			m[i][j]=m[i][i1-1]+m[i1+1][j];     //选第i1个元素为根时，计算左、右子树贡献
			s[i][j]=i1;                        //选择xi1为xi~xj序列的根结点
			
			for(int k=i1+1; k<=j1; k++)        //以i1+1和j1为左右边界时，选择根为xk的可能
			{
				double t=m[i][k-1] + m[k+1][j];//选xk为根结点，左、右子树的贡献
				if(t<m[i][j])                  //如果当前选择的xk比“最优”的更优
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}	
			m[i][j]+=w[i][j];                  //加上根使每个结点的贡献增加的w(i,j)
		}
	}
}

void shuchujiedian(int ll, int rr)
{
	printf("r(%d,%d)=%d\n",ll,rr,s[ll][rr]);
	if(ll<s[ll][rr])
	{
		shuchujiedian(ll, s[ll][rr]-1);
	}
	if(rr>s[ll][rr])
	{
		shuchujiedian(s[ll][rr]+1, rr);
	}
	return;
}

int main()
{
	freopen("in.txt","r", stdin);
	
	int n,i,casen=1;
	scanf("%d",&n);
	while(n)
	{
		for(i=1; i<=n; i++)
			scanf("%lf",&b[i]);
		for(i=0; i<=n; i++)
			scanf("%lf",&a[i]);	
		jiansuoshu(n);
		printf("此例子:\n",casen++);
		shuchujiedian(1, n);
		printf("结果为:%lf \n\n",m[1][n]);
		scanf("%d",&n);
	}
	return 0;
}