问题描述
计算器和计算机的大量普及也有其弊端。即便是受过专业技术训练的学生们也很可能缺乏计算能力。由于电脑的大量使用，很多人无法心算出7*8这样的算式，甚至是用纸和笔也算不出13*。不过谁在意呢？
Bartjens教授十分在意——因为他比较传统。他决定给学生布置一些计算作业，并且不能使用电子设备。为了批改方便，他决定使得几乎所有题答案都是2000，不过不全是，否则会被学生发现然后就不仔细计算了。
不幸的是，Bartjens教授的打印机实在是太旧了，不能和新的打印机兼容。打印出了题目后，教授发现所有的符号都丢失了！例如2100-=，被打印成了2100100=。不过，数字和等号被正确的打印了。
更糟糕的是，教授的试题原稿不见了。因此，他需要恢复出这些题原来的样子。如果答案是2000，那么2100100=可能是：
-=
**+=
**-=
**=
*-*-+=
Bartjen教授记得几点：
.他写的数字没有前导零。例如2**=就是不可行的。
.他写0的时候不会写多个0。例如2*+=就是不可行的。
.他只用二元运算符，不用取负。所以2*-*-+=也不合法。
.他只用+、-、*，不用/和括号。
.这些算式按照正常的优先级顺序计算。
你需要帮助barjen教授恢复这些题目。你需要在算式中插入至少一个运算符，使得答案是2000。有多少种可能的算式呢？
输入格式
输入包含一组数据。这组数据有n个数字（<=n<=），后面跟着一个=号。
输出格式
输出包含若干行，每一行是一个可行的解，具体格式见样例。按字典序从小到大输出这些字符串。如果无解，输出一行IMPOSSIBLE。
样例输入
=
【样例输出】
**+=
**-=
-=
数据规模和约定
<=n<=
题目描述
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define USE_LEN 10
#define OPERATE_LEN 4
#define RES 2000 int flag = ; void judge(int index,const char *arr,const char *ch)
{
int i,j,tmp,sum,res;
int tmp_num[USE_LEN]; //存储组合的数字
char tmp_ch[USE_LEN]; //1.验证是否符合要求
tmp=sum=;
for (i= ; i<index ; i++) //遍历输入的数字
{
//组合数字
if (sum == )
{
sum = arr[i]-'';
}
else
{
sum = sum*+(arr[i]-'');
} if (ch[i]!=' ')
{
tmp_num[tmp] = sum;
tmp_ch[tmp] = ch[i];
sum = ;
tmp ++;
}
else
{
if (sum== && i!=index-)
return ;//0***的数字不符合要求
}
} //2.验证是否满足要求
res = tmp_num[];
i=,j=; //i标记运算符下标 , j标记数字
while (j < tmp)
{
if (tmp_ch[j] =='*')
{
sum = tmp_num[j];
while (tmp_ch[j] == '*')
{
sum *= tmp_num[++j];
}
}
else
{
sum = tmp_num[j];
} switch(tmp_ch[i])
{
case '+':res +=sum;break;
case '-':res -=sum;break;
case '*':res *=sum;break;
}
i = j++;
} //3.打印符合要求的式子
if (res == RES)
{
flag ++;
for (i= ; i<index ; i++)
{
printf("%c",arr[i]);
if (ch[i]!=' ' && ch[i]!=)
printf("%c",ch[i]);
}
printf("=\n");
}
return ;
} void dfs(int index,int len,const char *arr,char *ch)
{
int i;
char operate[OPERATE_LEN] = {'*','+','-',' ',}; //可用运算符
if (len == )//运算符插入完成 (符号数比数字少1)
{
judge(index+,arr,ch); //判断插入运算符后的式子是否符合要求
return ;
}
else
{
for (i= ; i<OPERATE_LEN ; i++)
{
ch[index] = operate[i];//插入运算符
dfs(index+,len-,arr,ch);
}
} return ;
} int main(void)
{
char arr[USE_LEN]; //存储输入数据
char ch[USE_LEN]; //存储插入的符号 (放在每个数字后面) memset(arr,,sizeof(arr));
memset(ch,,sizeof(ch)); scanf("%s",arr);
if (strcmp(arr,"2000=") == ) //至少插入一个运算符
{
printf("IMPOSSIBLE");
return ;
}
else
{
dfs(,strlen(arr)-,arr,ch); //枚举情况
} if (flag == )
printf("IMPOSSIBLE"); return ;
}
C解法
解题思路：
将运算符“*”，“+”，“-”，“ ”插入到数字中，
枚举其不同组合情况下符合条件的。
采用DFS搜索满足条件的组合