multiply.cpp

使用动态规划解决数乘问题 给定一个m位数字和乘号数量n,n<m,求怎样将乘号插入数中

//数乘问题
//给定一个m位数字和乘号数量n,n<m,求怎样将乘号插入数中，使得积最大
//例123，乘号个数1，则12*3为最大
//该程序使用动态规划算法
#include<iostream>
using  namespace std;

int mul[10][10][10];          //全局数组,mul[a][b][x]记录数字的第a位到第b位中放置x个乘号的最大积
int pos[10][10];              //在最大积的情况下，pos[a][b]记录第a位到第b位中下个乘号的位置，为0表示无乘号
int A[10];                    //记录输入的数字

//将数字第a位到第b位合成一个b-a+1位数
int num(int a,int b)          
{
	int i,num=0;
	for(i=a;i<=b;i++)
		num=num*10+A[i];
	return num;
}

//对数字第a位到第b位进行连乘
int prod(int a,int b)
{
	int i,prod=1;
	for(i=a;i<=b;i++)
		prod*=A[i];
	return prod;
}

//递归函数,返回数字的第a位到第b位中放置x个乘号的最大积
int multiply(int a,int b,int x)
{
	int temp;
	if(mul[a][b][x]!=0)
		return mul[a][b][x];
	else 
	{
		if(x>b-a)                  //乘号数量大于数字个数-1,出错
	    	return 0;
    	else if(x==0)              //乘号数量为0,直接得到b-a+1位数
	    	temp=num(a,b);
    	else if(x==b-a)            //乘号数量=数字个数-1,在每两位数间都加*
		{
			temp=prod(a,b);
			for(int i=a;i<b;i++)
				pos[i][x]=i;
		}
    	else                        //乘号位置从a至b,找寻最大乘积
		{
	    	int j,max=0,maxj=0;
	    	for(j=a;j<b;j++)
			{
		    	temp=num(a,j)*multiply(j+1,b,x-1);
				if (temp>max)
				{
					max=temp;
					maxj=j;
				}
			}
			temp=max;
			pos[a][x]=maxj;
		}
		mul[a][b][x]=temp;
    	return temp;
	}
}
			

main()
{
	int a,b,x,length,i,j;
	char again;
	do
	{
		char input[10];
		cout<<"Please input a number(between 0 and 999999999)\n";
		cin>>input;
		cout<<"Please input the number of '*'\n";
		cin>>x;
		i=1;
		while(input[i-1]>='0'&&input[i-1]<='9')
		{
			A[i]=input[i-1]-48;
			i++;
			if (i==10) break;
		}
        
        b=i-1;a=1;
		//计算最大积
	    int res=multiply(a,b,x);
        //通过数组pos找寻最大积下的乘号位置
    	i=a;j=x;
    	while(j!=0)
		{
	    	cout<<num(i,pos[i][j]);
	        i=pos[i][j]+1;
	        j--;
	    	cout<<"*";
		}
    	cout<<num(i,b);
    	cout<<"="<<res<<endl;
  
    	cout<<"Again?";
    	cin>>again;
	}while(again!='n'&&again!='N');
}