最大乘积——高精度乘法

乘积最大

Description

问题描述:
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样
一道题目:

设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

Input

程序的输入共有两行:
第一行共有2个自然数N,K (6<=N<=40，1<=K<=6)
第二行是一个K度为N的数字串。

Output

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

Sample Input

4 2

1231

Sample Output

62

状态转移方程：

f[i][j]=max{f[i-1][m]*a[m..j]} i<=m<=j

f[i][j]代表前j个数用i个乘号连接得到的最大值，a[m..j]代表从a[]的第m个到第j个数字组成的数。转移方程不算难，但此题要用

高精度乘法。乘法有两种写法：一种是完全模拟乘法竖式的演算过程，另一种是通过总结规律得到的算法。下面列出两种程序的写法。

法一：

 

1 #include < stdio.h >
2 #include < stdlib.h >
3 #include < string .h >
4 char f[ 7 ][ 41 ][ 2010 ],a[ 40 ],b[ 2000 ];
5 int n,k,length[ 7 ][ 41 ];
6 /*length[][]记录高精度数的长度*/
7 int plus( char * p, int l1, char * q, int l2, int le)
8 {
9 int c,s = 0 ,l;
10 int i;
11 for (i = l1 - 1 ;i >= 0 ;i -- )p[i + le] = p[i];
12 for (i = 0 ;i < le;i ++ )//对错位的处理：后移与前几位补0，因为数值是倒存的
13 {
14 p[i] = ' 0 ' ;
15 l1 ++ ;
16 }
17 if (l1 > l2)l = l1;
18 else l = l2;
19
20 for (i = 0 ;i < l;i ++ )
21 {
22 s += p[i] + q[i] - 2 * ' 0 ' ;
23 c = s % 10 ;
24 s /= 10 ;
25 q[i] = c + ' 0 ' ;
26 }
27 while (s != 0 )
28 {
29 c = s % 10 ;
30 s /= 10 ;
31 q[i ++ ] = c + ' 0 ' ;
32 }
33
34 return i;
35 }
36
37 int mul( char * p, int l1, int fr, int l2, char * q, int l3)
38 {
39 int c,s = 0 ;
40 int i,j;
41 char s1[ 40 ],s2[ 2000 ];//s1[]记录a[]中从fr开始，长度为l2的数
42 for(i=0;i<l2;i++ )
43 s1[i]=a[l2+fr-i-1 ];
44 for (i = 0 ;i < l1;i ++ )//用s1[]的每一位乘以p[]的每一位，注意错位的
45 if (p[i] != ' 0 ' )//是0就不必乘了
46 {
47 memset(s2, 48 , sizeof (s2));
48 for (j = 0 ;j < l2;j ++ )
49 {
50 s += (p[i] - ' 0 ' ) * (s1[j] - ' 0 ' );
51 c = s % 10 ;
52 s = s / 10 ;
53 s2[j] = c + ' 0 ' ;
54 }
55 while (s != 0 )
56 {
57 c = s % 10 ;
58 s /= 10 ;
59 s2[j ++ ] = c + ' 0 ' ;
60 }
61 l3 = plus(s2,j,q,l3,i);//q[]中存每一位乘过后的值
62 }
63 return l3;
64 }
65
66
67 int max( char * p, char * q, int l1, int l2)
68 {
69 if (l1 > l2) return 1 ;
70 else if (l2 > l1) return 0 ;
71 else
72 {
73 int i;
74 for (i = l1 - 1 ;i >= 0 ;i -- )
75 if (p[i] > q[i]) return 1 ;
76 else if (q[i] > p[i]) return 0 ;
77 return 0 ;
78 }
79 }
80
81 int main()
82 {
83 FILE * in , * out ;
84 in = fopen( " maxmu3.in " , " r " );
85 out = fopen( " maxmu.out " , " w " );
86 int i,j,k,m,l1,l2,i1;
87 fscanf( in , " %d %d " , & n, & k);
88 fscanf( in , " %s " ,a);
89
90 memset(f, 48 , sizeof (f));//不能初始化为0，因为f[][][]是字符型，字符型0的ASCII码是48
91 memset(length, 0 , sizeof (length));
92 for(i=1;i<=n;i++ )
93 {
94 for(j=0;j<i;j++ )
95 f[0][i][j]=a[i-j-1 ];
96 length[0][i]= i;
97 }
98
99 for (i = 1 ;i <= k;i ++ )
100 for (j = i + 1 ;j <= n;j ++ )
101 {
102 length[i][j] = mul(f[i - 1 ][i],length[i - 1 ][i],i,j - i,f[i][j],length[i][j]);
103 for (m = i + 1 ;m <= j;m ++ )
104 {
105 memset(b, 48 , sizeof (b));//每次都要初始化
106 l1 = mul(f[i - 1 ][m],length[i - 1 ][m],m,j - m,b, 0 );
107 if (max(b,f[i][j],l1,length[i][j]))
108 {
109 memset(f[i][j], 48 , sizeof (f[i][j]));//有必要先将f[i][j]清空
110 strcpy(f[i][j],b);
111 length[i][j] = l1;
112 }
113 }
114 }
115
116 for (i = length[k][n] - 1 ;i >= 0 ;i -- )
117 fprintf(out,"%c",f[k][n][i]);
118 fprintf(out,"\n");
119 fclose(in);
120 fclose(out);
121 return 0;
122 }

举例说明：123*456列为竖式计算是：

1 2 3

* 4 5 6

————————

 

7 3 8 ————由mul（）函数计算可得

6 1 5

4 9 2

————————

5 6 0 8 8

最后将中间红色区的数加起来的工作就由plus()函数做了。注意plus（）还要处理错位。

法二：

1 int mul( int * p, int l1, int fr, int l2, int * q, int l3)
2 {
3 int i,j;
4 int c,s = 0 ;
5 int s1[ 40 ];
6
7 for (i = 0 ;i < l2;i ++ )
8 s1[i] = a[l2 + fr - i - 1 ];
9
10 for (i = 0 ;i < l1;i ++ )
11 for (j = 0 ;j < l2;j ++ )
12 q[i + j] = q[i + j] + p[i] * s1[j];
13
14 for (i = 0 ;i <= l1 + l2 - 2 ;i ++ )
15 {
16 c = (q[i] + s) % 10 ;
17 s = (q[i] + s) / 10 ;
18 q[i] = c;
19 }
20
21 while (s != 0 )
22 {
23 c = (q[i] + s) % 10 ;
24 s = (q[i] + s) / 10 ;
25 q[i ++ ] = c;
26 }
27 return i;
28 }

 

注意法二已将字符串转化为了int型，其他没变。该方法是这样相乘的：

q[i+j]=q[i+j]+s1[j]*p[i];

最后再处理进位，显然比法一要简单多。

当然还有不用高精度的方法，也列出来了。

1 #include < stdio.h >
2 #include < stdlib.h >
3 #include < string .h >
4 long f[ 7 ][ 41 ];
5 char a[ 40 ];
6 int n,k;
7
8 int mul( int x, int f, int le)
9 {
10 int i,s = 0 ,m = 1 ;
11 for(i=le-1;i>=0;i-- )
12 { s +=(a[i+f]-'0')* m;
13 m*=10 ;
14 }
15 return s * x;
16
17 }
18 int main()
19 {
20 FILE * in , * out ;
21 in = fopen( " maxmu1.in " , " r " );
22 out = fopen( " maxmu.out " , " w " );
23 int i,j,k,m,sum;
24 long max;
25 char x;
26 fscanf( in , " %d %d " , & n, & k);
27 fscanf( in , " %s " ,a);
28
29 for(i=1;i<=n;i++ )
30 {
31 sum=0;m=1 ;
32 for(j=i-1;j>=0;j--)
33 {
34 sum+=(a[j]-'0')* m;
35 m*=10 ;
36 }
37 f[0][i]= sum;
38 }
39
40 for (i = 1 ;i <= k;i ++ )
41 for (j = i + 1 ;j <= n;j ++ )
42 {
43 f[i][j] = mul(f[i - 1 ][i],i,j - i);
44 for (m = i + 1 ;m <= j;m ++ )
45 {
46 max = mul(f[i - 1 ][m],m,j - m);
47 if (f[i][j] < max)
48 f[i][j] = max;
49 }
50 }
51
52 fprintf( out , " %ld " ,f[k][n]);
53 fclose( in );
54 fclose( out );
55 return 0 ;
56 }
57

 

状态转移还一样，只是这次可以直接乘，所以在数的存储处理上不必倒着存（上面两个完整程序中红色区域是对数的存储处理）。