[华为机试真题][2014]63.等式变换

时间:2022-06-15 18:53:20

题目

输入一个正整数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

代码

/*---------------------------------------
* 日期:2015-07-06
* 作者:SJF0115
* 题目:等式变换
* 来源:华为机试真题
-----------------------------------------*/

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 整型转换为字符串
string Int2Str(int num){
string str;
if(num == 0){
str = '0';
return str;
}//if
int tmp = num;
while(num){
str.insert(str.begin(),num % 10 + '0');
num /= 10;
}//while
return str;
}

/*
当前计算值 result
符合的等式个数 count
等式结果 x
相邻数合并的结果 sequence 1 + 2 + 345 345 就是 sequence
*/

void helper(vector<int> &num,int index,int x,int result,int sequence,int &count,string op){
if(index == num.size()){
if(result + sequence == x || result - sequence == x){
++count;
if(result + sequence == x){
op += "+"+Int2Str(sequence);
}//if
else{
op += "-"+Int2Str(sequence);
}//else
cout<<op<<endl;
}//if
return;
}//if
// 连续数
helper(num,index+1,x,result,sequence * 10 + num[index],count,op);

// 加法 +
if(op.size() > 0){
// 以num[index]为sequence的起点
helper(num,index+1,x,result + sequence,num[index],count,op+"+"+Int2Str(sequence));
}//if
else{
// 以num[index]为sequence的起点
helper(num,index+1,x,result + sequence,num[index],count,op+Int2Str(sequence));
}//else


if(op.size() > 0){
// 减法-
// 以num[index]为sequence的起点
helper(num,index+1,x,result - sequence,num[index],count,op+"-"+Int2Str(sequence));
}//if
}

int TransformationEquation(vector<int> num,int x){
int count = 0;
string op = "";
helper(num,1,x,0,num[0],count,op);
return count;
}

int main(){
int n,x;
int num;
//freopen("C:\\Users\\Administrator\\Desktop\\acm.in","r",stdin);
while(cin>>n>>x){
vector<int> vec;
for(int i = 0;i < n;++i){
cin>>num;
vec.push_back(num);
}//for
cout<<TransformationEquation(vec,x)<<endl;
}//while
return 0;
}