表达式中插入乘号问题.cpp

输入N位数,在其中插入R个乘号, 使得所得的结果最大.

// 表达式中插入乘号问题
# include<stdio.h>
# include<stdlib.h>
# include<math.h>
int N,R;          //N存放总个数,R乘需要插入乘号的个数
double MAX=0;          
char c[100];     //用来存放输入的表达式
int a[100],b[100];

int change(int left,int right)  //将字符串转换成数字
{
	int i,wei=right-left,s=0;
	for(i=left;i<=right;i++,wei--)
	{
	  //s=s+pow(c[i]-48,wei);
	    s=s+(c[i]-48)*pow(10,wei);
	}
	return s;
}

int max(void)    //更新最大值的实现
{
	int k=1,i;
	double s=1;
	for(i=1;i<=R;i++)
	{
		s=s*change(k,a[i]);
		k=a[i]+1;
	}
	s=s*change(k,N);
	if(s>MAX)
	{
		MAX=s;
		for(i=1;i<=N;i++)
			b[i]=a[i];
	}
	return 0;
}


int combine(int n,int r)   //递归求组合数
{
	int i;
	if(n<r)               //输入数据有误
		return 0;
	else if(r<1)          //组合数已经完全确定
		max();
	else                 //继续填充组合数
	{
		for(i=n;i>=r;i--)
		{
			a[r]=i;
			combine(i-1,r-1);
		}
	}
	return 0;
}


int print(void)    //输出满足要求的结果
{
	int i,j,k=1;
	printf("%.0f=",MAX);
	for(i=1;i<=R;i++)
	{
		for(j=k;j<=b[i];j++)
			printf("%c",c[j]);
		printf("*");
		k=b[i]+1;
	}

	for(j=k;j<=N;j++)
		printf("%c",c[j]);
	return 0;
}

int main(void)
{
	int i;
	printf("请输入表达式的长度,即待查入乘号的个数:\n");
	scanf("%d%d",&N,&R);
	getchar();
	printf("请输入这个表达式:\n");
	for(i=1;i<=N;i++)
		scanf("%c",&c[i]);
	combine(N-1,R);
	//printf("you are a good boy!\n");
	print();
	printf("\n");
    return 0;
}