题目要求大致为已知如上数字符号，求按此计算的最大值和最小值
思路如下：
①由于计算的过程当中，一定有一个运算符是多余的，所以哪一个运算符可以省去，因此，可以采用两个数组V[]与op[]，来存放相应的数字与运算符。依次去掉一个运算符，每去掉一个就是一种新的情况，取这些情况的最大和最小值。
②在去掉一个运算符后，计算结果就是一个较长的式子，不同的运算先后情况会产生不同的结果，可以将不同的结果取最大值与最小值，来作为步骤①的一种情况。最小值为在最小值中取得最小值，最大值为在最大值中取得最大值。
fmax=max{（max（f[num]））}，fmin=min{（min（f[num]））}。
③接下来针对的是f[num]的具体解。在已知已经出现了一个待运算的式子以后，我们可以根据不同的运算符处理顺序将式子做出相应的运算（相当于在不同的位置添加不同数目的括号），已知在经过了一系列运算后，可以最终演变成两个数之间的运算，可能有两种情况，一种是两数相加，一种是相乘，进行相乘或者相加的两个数又是通过一系列运算得到的，也各自成一列式子，由不同的运算顺序得到。
④由此观之，这些运算应该是有两个数之间的递归算法得到，经过不同的划分，得到每一个式子的最大以及最小值，直到一个式子是由两个数字组成，为原始形象。
⑤由于全部存放是浪费空间的，由于在最终求解时只需要知道一种情况的最大和最小，那么，就可以根据两个数字之间的运算符，只保留每次运算后的最大和最小值两种情况。
⑥具体分析：在开始的时候由于封号两边的数字都直接由数字组成，不是由一段式子运算得到，所以最大和最小值都是本身，设两数字为a,b；数字之间符号为‘+‘，那么最大值为a+b,最小值也是a+b，数字之间符号为‘✲’么最大值为ab,最小值也是ab，在所以情况中找到最大值与最小值，假设符号左边的最大和最小为a，b，右边最大和最小为c，d。那么假设最后符号为+，那么最大和最小值应为max{a+c,a+d,b+c,b+d}，min{a+c,a+d,b+c,b+d}，如果符号为‘✲‘，那么那么最大和最小值应为max{ac,ad,bc,bd}，min{ac，ad,bc,bd}。
具体代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX_POINT 20
int chain_value[MAX_POINT][MAX_POINT][2]; //chain[i][j][0]表示从v[i]节点开始，边长为j的链的最大值
//chain[i][j][1]表示从v[i]节点开始，边长为j的链的最小值
//从某个节点开始，即从该结点前开始分割，不同的分割方式。
int n,*v;
char *op;
int get_max_sum();
void chain_max(int start, int len, int k);
void get_max_min(int a, int b, int c, int d, int start, int index, int len);
int main()
{
int i;
char ch;
scanf("%d",&n);
v = (int *)malloc(n*sizeof(int));
op = (char *)malloc(n*sizeof(char));
ch = getchar(); //数据输入
for (i = 0; i < n; i++)
{
scanf("%c",&op[i]);
ch = getchar();
scanf("%d",&v[i]);
ch = getchar();
}
printf("MAX:%d\n",get_max_sum()); //得到最大值
return 0;
}//main
int get_max_sum()
{
int i,k,start,max,tmp,len;
for (i = 0; i < n; i++)
{
chain_value[i][0][0] = v[i]; //链长为0，即单个点的值
chain_value[i][0][1] = v[i]; //以每个结点为起始结点进行判断，如果长度为，即不经过任何的运算，那么最大和最小的结果都是相同的，即原数本身。
}
for (len = 1; len < n; len++) //控制链的长度，
{ //n在前期手动输入，表示数字的个数||符号的个数||多边形的长度。
for (start = 0; start < n ; start++) //起点start配合链长，就可以得出除去某条边的效果
{
chain_value[start][len][0] = -9999;
chain_value[start][len][1] = 9999;
//所有的结点最大设为-9999，最小为9999，用来进行大小比较时取得正确的最大最小值
for (k = 0; k < len; k++) //不同的操作符号的位置，k表示数学符号的下标
{
chain_max(start,len,k);//取得最大*********************************************
}
}
}
max = chain_value[0][n-1][0]; //最终的最大值
for (start = 1; start < n; start++)
{
tmp = chain_value[start][n-1][0];
max = max > tmp ? max : tmp;
}
return max;
}
void chain_max( int start, int len, int k)//start表示初始位置，len表链长，k为一个小于len的整数
{
int index,a,b,c,d; //a<= m1 <= b c<= m2 <=d
//ab存放符号左边的最小值和最大值，cd存放符号右边的最小值和最大值。
index = (start+k+1)%n; //表示符号(op)或者符号后面的操作数的下标（不同的起始点之后的第k个字符（数字）），在接下来的运算中作为右边式子的起始位置
a = chain_value[start][k][1];
b = chain_value[start][k][0]; //从start到k的最大和最小值，即左边的最大和最小
c = chain_value[index][len-k-1][1];
d = chain_value[index][len-k-1][0]; //右边的最大和最小值
//最开始时，a=b=chain_value[0][0][1];d=c= chain_value[1][0][1];当k增加
get_max_min(a,b,c,d,start,index,len); //根据符号的不同情况确定该段式子的最小和最大值。
}
void get_max_min(int a, int b, int c, int d, int start, int index, int len)
{
int max_max,min_min,max_min,min_max;
int max,min;
max = chain_value[start][len][0]; //先将max，min初始化
min = chain_value[start][len][1];
if ('+' == op[index])
{
max = max > (b + d) ? max : (b + d);
min = min < (a + c) ? min : (a + c); //如果为加，求得最大值和最小值
}
else if ('x' == op[index])//如果为乘，求得最大值和最小值
{
max_max = b * d;
min_min = a * c;
max_min = b * c;
min_max = a * d;
max = max > max_max ? max :max_max;
max = max > min_min ? max : min_min;
max = max > max_min ? max : max_min;
max = max > min_max ? max : min_max;
min = min < max_max ? min :max_max;
min = min < min_min ? min : min_min;
min = min < max_min ? min : max_min;
min = min < min_max ? min : min_max;
}
chain_value[start][len][0] = max; //该最大值和最小值是在start到len的最大和最小值，将其正确赋值
chain_value[start][len][1] = min;
}
网友评论