[数据结构与算法]4152:最佳加法表达式

4152:最佳加法表达式

没有考虑高精度高精度列式计算，出现runtime error中途崩溃
考虑之后我崩溃了，太不细心的我~~

#include <bits/stdc++.h>
using namespace std; 
#define MAX 100
#define inf 9999999999
//int a[MAX][MAX];
char a[MAX];
int value[MAX][MAX];//从i到j这一段数字组合成一个数的值 
int dp[MAX][MAX];//把m个加号放到前n个数字中 的运算结果 
int main(int argc, char** argv) {
	int m;//要放m个加号
	while(cin>>m){
		int len=0;
		char x; 
		while(cin>>x){
			a[++len]=x;
		for(int i=1;i<=len;i++){
			value[i][i]=a[i]-'0';
			for(int j=i+1;j<=len;j++){
				value[i][j]=value[i][j-1]*10+a[j]-'0';
			}
		} 
		for(int j=1;j<=len;j++){
			dp[0][j]=value[1][j];
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=len;j++){
				if(i>j-1)dp[i][j]=inf;
				else{
					int res=inf;	
//要在j个数放i个加号，先在所有能放的最后一个位置k里
//放一个，得到的结果是从k到j这段数的值 + i-1个加号放在前 k个数的结果
//考虑到k是加号能放的最后一个位置，k的取值范围只能是i(后一个)~j-1(后一个)
					for(int k=i;k<j;k++)
					res=min(res,dp[i-1][k]+value[k+1][j]);
					dp[i][j]=res;
				}
			}
		}
		}
		cout<<dp[m][len];
	} 
	return 0;
}

思想其实与上面的一致，不过是加法的方法和一些数值的表现形式变化了，下面的代码注释之处与运行之处形成对照。

#include <bits/stdc++.h>
using namespace std; 
#define MAX 100
struct kkk{
	char res[MAX];
};
//#define inf 9999999999
char a[MAX];
kkk value[MAX][MAX];//从i到j这一段数字组合成一个数的值 
kkk dp[MAX][MAX];//把m个加号放到前n个数字中 的运算结果 
void Assign(char a[],char b[],int x,int y){//把a的一段赋值给b数组0 3  1234->
	int k=0;
	for(int i=x;i<=y;i++){
		b[k++]=a[i];
	}
	b[k]='\0';
}
void plusy(char a[],char b[],int t1[],int t2[],int ans0[],char ans1[]){
 //a,b是要列竖式相加的两个字符数组，两数相加从低位开始，可数组的习惯是从前往后
 //	因此将要相加的字符数组转置存在另外两个数组(做一个transition)得出
 //结果数组ans0后在转置回去ans1 
 //用字符型数组固然节省空间，但字符之间做加法再转化为int型和各自转成int型再相加结果不一样 
	int len1=strlen(a);
	int len2=strlen(b);
// 	for(int i=0,j=0;i<len1,j<len2;i++,j++){//0123  3210 len==4
// 		t1[len1-1-i]=a[i]-'0';
// 		t2[len2-1-j]=b[j]-'0';
//	 }
	for(int i=0;i<len1;i++){//0123  3210 len==4
 		t1[len1-1-i]=a[i]-'0';
	 }
	 	for(int i=0;i<len2;i++){//0123  3210 len==4
 		t2[len2-1-i]=b[i]-'0';
	 }
	 int len=max(len1,len2);//即使长度短的哪个串其余的位置都为0
	for(int k=0;k<len;k++){
	 	ans0[k]+=(t1[k]+t2[k]);
	 	ans0[k+1]=ans0[k]/10;
	 	ans0[k]=ans0[k]%10;
	 }
	 if(ans0[len])len++;//最高位存在进位 
//	 要考虑最后几位全为0的情况，转置回去就是数字首位为0，要去掉
	while(ans0[len-1]==0&&len>=1){//k>=1是为了放置整个数组都是0，就得留一个0，k就是数组长度 
	 len--;
	} 
	 for(int i=0;i<len;i++){
	 	ans1[len-1-i]=ans0[i]+'0';
	 }
	 ans1[len]='\0';
}
//void plusy(kkk a,kkk b,int q[],int w[],int c[],char cz[])
//{
//    int lena=strlen(a.res),lenb=strlen(b.res),i,j;
//    for(int i=0,j=lena-1;j>=0;++i,j--)
//    {
//        q[i]=a.res[j]-48;
//    }
//    for(int i=0,j=lenb-1;j>=0;++i,j--)
//    {
//        w[i]=b.res[j]-48;
//    }
//    int g=max(lena,lenb);
//    for(int i=0;i<g;++i)
//    {
//        c[g-i]+=q[i]+w[i];
//        if(c[g-i]>=10)
//        {
//            c[g-i]-=10;
//            c[g-i-1]+=1;
//        }
//    }
//    if(c[0])
//        i=0;
//    else
//        i=1;
//    for(j=0;i<=g;++i,j++)
//    {
//        cz[j]=c[i]+48;
//    }
//    cz[j]='\0';
//}

int compare(kkk ka,char b[]){//a>b
//	char a[]=ka.res;
	char a[MAX];
	memcpy(a,ka.res,sizeof(ka.res));
	int len1=strlen(a);
	int len2=strlen(b);
	if(len1>len2)return 1;
	else if(len1<len2)return 0;
	else if(len1==len2)
//	return strcmp(a,b);×××
if( strcmp(a,b)>0)return 1;
else return 0; 
//	return(a>b);-----------------------错误啦？？？？ 
//	或者return(a>b); //我以为string类型的字符串才能直接这样比较，
//	字符数组声明的字符串只能用strcmp呢，就要str.size()和strlen(a) 
//	return strcmp(a,b);//长度相同就按字典序比较 
}

int main(int argc, char** argv) {
	int m;//要放m个加号
	while(cin>>m){
		cin>>a+1;
		int len=strlen(a+1);
//differ1:初始要根据给出的一串数a算出任意一段数组成的值，之前要把值的大小求出
//直接赋值给value数组的int类型数据，现在只要把这段数存入value数组就好
//（之前每个数组元素是个数，现在是组成数的一个字符数组（怕这段数太长int表示不了 
//		for(int i=1;i<=len;i++){
//			value[i][i]=a[i]-'0';
//			for(int j=i+1;j<=len;j++){
//				value[i][j]=value[i][j-1]*10+a[j]-'0';
//			}
//		} 
				for(int i=1;i<=len;i++){
			for(int j=i;j<=len;j++){
				Assign(a+1,value[i][j].res,i-1,j-1);
			}
		} 
//当要放0个加号，则得到的dp结果就等于这段数组成的值value结果 
		for(int j=1;j<=len;j++){
//			dp[0][j]=value[1][j];现在字符数组不能直接赋值
//			Assign(value[1][j].res,dp[0][j].res,0,j-1);
			Assign(a+1,dp[0][j].res,0,j-1);
		}
		kkk min;//来盛放最小的dp[i][j],为什么要借助min呢，
//		因为要得到最小的先要经过一番比较的  
			for(int i=1;i<=m;i++){
			for(int j=1;j<=len;j++){
//				if(i>j-1)dp[i][j]=inf;
//				else{
//					int res=inf;
				memset(min.res,9,sizeof(min.res));
				min.res[MAX]='\0';
				//相当于初始化为inf，一有更小的就替换 
				if(i<=j-1){
			
//要在j个数放i个加号，先在所有能放的最后一个位置k里
//放一个，得到的结果是从k到j这段数的值 + i-1个加号放在前 k个数的结果
//考虑到k是加号能放的最后一个位置，k的取值范围只能是i(后一个)~j-1(后一个)
					for(int k=i;k<j;k++){
					int t1[MAX];memset(t1,0,sizeof(t1));
				int t2[MAX];memset(t2,0,sizeof(t2));
				int ans0[MAX];memset(ans0,0,sizeof(ans0));
				char ans1[MAX];memset(ans1,0,sizeof(ans1));
//				res=min(res,dp[i-1][k]+value[k+1][j]);
				plusy(dp[i-1][k].res,value[k+1][j].res,t1,t2,ans0,ans1);
				if(compare(min,ans1)){//ans<min,则min=ans 
					int len1=strlen(ans1);
					Assign(ans1,min.res,0,len1-1);
				}
					}
//					dp[i][j]=res;
					int minlen=strlen(min.res);
					Assign(min.res,dp[i][j].res,0,minlen-1);
				}
				}
			}
			//		cout<<dp[m][len];
			cout<<dp[m][len].res<<endl;
//			cout<<"niaho"<<endl;
//			int i=0;
//			while(dp[m][len].res[i]!='\0'){
//				cout<<dp[m][len].res[i++]<<endl;
//			}
//			cout<<endl;
		}
		return 0;
	} 

最后附上一道 高精度大整数加法
10:大整数加法

#include <bits/stdc++.h>
using namespace std;
#define MAX 200
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
	void plusy(char a[],char b[],int t1[],int t2[],int ans0[],char ans1[]){
 //a,b是要列竖式相加的两个字符数组，两数相加从低位开始，可数组的习惯是从前往后
 //	因此将要相加的字符数组转置存在另外两个数组(做一个transition)得出
 //结果数组ans0后在转置回去ans1 
 //用字符型数组固然节省空间，但字符之间做加法再转化为int型和各自转成int型再相加结果不一样 
	int len1=strlen(a);
	int len2=strlen(b);
// 	for(int i=0,j=0;i<len1,j<len2;i++,j++){//0123  3210 len==4
// 		t1[len1-1-i]=a[i]-'0';
// 		t2[len2-1-j]=b[j]-'0';
//	 }
 	for(int i=0;i<len1;i++){//0123  3210 len==4
 		t1[len1-1-i]=a[i]-'0';
	 }
	 	for(int i=0;i<len2;i++){//0123  3210 len==4
 		t2[len2-1-i]=b[i]-'0';
	 }
	 int len=max(len1,len2);//即使长度短的哪个串其余的位置都为0
	for(int k=0;k<len;k++){
	
	 	ans0[k]+=(t1[k]+t2[k]);
	 	ans0[k+1]=ans0[k]/10;
	 	ans0[k]=ans0[k]%10;
	 }
	 if(ans0[len]==1)len++;//最高位存在进位 
//	 要考虑最后几位全为0的情况，转置回去就是数字首位为0，要去掉
	while(ans0[len-1]==0&&len>1){
	//k>=1是为了放置整个数组都是0，就得留一个0，
	//不对，k就是数组长度 ，所以k一定得大于1 
	 len--;
	} 
	 for(int i=0;i<len;i++){
	 	ans1[len-1-i]=ans0[i]+'0';
	 }
	 ans1[len]='\0';
}
void plusy2(char a[],char b[],int q[],int w[],int c[],char cz[])
{
    int lena=strlen(a),lenb=strlen(b),i,j;
    for(int i=0,j=lena-1;j>=0;++i,j--)
    {
        q[i]=a[j]-48;
    }
    for(int i=0,j=lenb-1;j>=0;++i,j--)
    {
        w[i]=b[j]-48;
    }
    int g=max(lena,lenb);
    	
	 cout<<"t1-> "<<q<<endl;
	cout<<"t2-> "<<w<<endl;
		 cout<<"lenmax-> "<<g<<endl;
    for(int i=0;i<g;++i)
    {
        c[g-i]+=q[i]+w[i];
        if(c[g-i]>=10)
        {
            c[g-i]-=10;
            c[g-i-1]+=1;
        }
    }
    if(c[0])
        i=0;
    else
        i=1;
    for(j=0;i<=g;++i,j++)
    {
        cz[j]=c[i]+48;
    }
    cz[j]='\0';
}

int main(int argc, char** argv) {
				int t1[MAX];
				int t2[MAX];
				int ans0[MAX];
				char ans1[MAX];
				char a[MAX];
				char b[MAX];
				cin>>a>>b;
				memset(t1,0,sizeof(t1));
				memset(t2,0,sizeof(t2));
				memset(ans0,0,sizeof(ans0));
				memset(ans1,0,sizeof(ans1));
				plusy(a,b,t1,t2,ans0,ans1);
				int i=0;
				cout<<ans1;

	return 0;
}