描述
等式变换 （华为2015校招机试第3题+清华软院2016推免第3题+第三届蓝桥杯真题）
描述: 输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足该输入整数的所有等式的个数。
要求
运行时间限制: 无限制
内存限制: 无限制
输入: 正整数，等式右边的数字
输出: 使该等式成立的个数
样例输入: 5
样例输出: 21
思路/分析
这题看似是一道填运算符号的题，其实我们可以把填运算符号问题转换为填数问题，1~9个数字中有8个空，每个空有3种不同运算符号的填法。
不妨假设数字0为不填符号、数字1位填+，数字2为填-；因此，这道题的思路变清晰明了，直接可使用DFS深搜回溯的方法，进行暴力填数。
不过此题，相比较于一般的DFS类型题，写起来要复杂很多。思路参考—>https://blog.****.net/roman1232008/article/details/11705577
AC代码
#include<iostream>
#include<cstring>
using namespace std;
int cnt=0;//记录符合等式要求的次数
int tnum;//等式右边的目标值
//思路：9个数字中有8个空格，每个空格有3种填法
//0表示不填，1表示+，2表示-
int cal(char opChar,int sum,string number){
if(opChar=='+'){
sum+=atoi(number.c_str()); //计算和,string—>c_str —>int
}
else if(opChar=='-'){
sum-=atoi(number.c_str()); //计算差,string—>c_str —>int
}
return sum;
}
//result运算符号数组,s为运算数数组
int show(int result[]){//输出表达式,传进来result运算符号数组
int sum=0;//当前表达式的运算和
char opChar='+';
string s[]={"1","2","3","4","5","6","7","8","9"};
string number; //number表示当前最右边的运算数
string expression;//expression表示当前的运算表达式（含符号）
number+=s[0];
expression+=s[0];
for(int i=0;i<8;i++){
if(result[i]==0){//当前运算符号为空
number+=s[i+1];
expression+=s[i+1];
}
else if(result[i]==1){//当前运算符号为+
sum=cal(opChar,sum,number);
number.clear();
opChar='+';
number+=s[i+1];
expression+='+';//"+"
expression+=s[i+1];
}
else if(result[i]==2){//当前运算符号为-
sum=cal(opChar,sum,number);
number.clear();
opChar='-';
number+=s[i+1];
expression+='-';//"-"
expression+=s[i+1];
}
}//end of for
sum=cal(opChar,sum,number);
if(sum==tnum){
cout<<expression.c_str()<<"="<<tnum<<endl;
cnt++;
}
}
void dfs(int layer,int result[]){//dfs层数从0开始
if(layer>=8){//0~7共8个数，第8层出口
show(result);
return ;
}
else{
for(int i=0;i<3;i++){//8层,每层要枚举3种运算符号
result[layer]=i;
dfs(layer+1,result);
result[layer]=0;//回溯，回复原状态
}
}
}
int main(int argc, char** argv) {
while(cin>>tnum){
int result[8];//={0};
memset(result,0,sizeof(result));
dfs(0,result);
cout<<cnt<<endl;
}
return 0;
}