// 表达式中插入乘号问题
# 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;
}
