华为的一道机试题
(http://blog.csdn.net/zombie_slicer/article/details/37346025)
第三题：等式变换
输入一个正整数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前面也加+/-。思路没什么影响，从结果中去掉最开始一位为 -号的就行。
本方法的思路是：每个数字(除1之外)的所有数字前的符号都有三种选项：+/-/空，"空"代表不加符号，也就是与前一个数字相连。
将所有数字的符号用一个三进制的数来表示，用0代表+，1代表-，2代表空。21201202，就代表12-34+5-67+89。代码中由于计算三进制的方便，将其以倒序的方式表示的，且1前面可以用+/-号，三进制通过一个int型的数字转换成了string。
于是，从0到22222222就可以代表所有的结果的可能了，转换成int就是从0到6560，一共也才6561种，计算量并不大。从0到6560遍历一遍看结果是否与输入的值一致，再统计总的一致的次数即可得到答案。
string get_3x(int number)
{
string symbols = "";
int remain = 0;
while(number)
{
remain = number % 3;
number = number / 3;
symbols += (remain + ‘0‘);
}
int zero_count = 9 - symbols.size();
for(int i =0; i < zero_count; i++)
symbols += ‘0‘;
return symbols;
}
// 0 +
// 1 -
// 2 nul
void equation_transfer(int number)
{
int equal_count = 0;
const int table_size = 13122; // 2 * 3^8
for(int i = 0; i < table_size; i++)
{
string symbol = get_3x(i);
int x = 0;
int y = 0;
// cout << symbol << endl;
for(int j = 8; j >= 0; j--)
{
if(symbol[j] == ‘0‘)
{
x = x + y;
y = 9 - j;
}
else if(symbol[j] == ‘1‘)
{
x = x + y;
y = -(9-j);
}
else
{
if(y < 0)
y = y * 10 - (9-j);
else
y = y * 10 + (9-j);
}
}
if((x+y) == number)
{
equal_count++;
cout << symbol << endl;
}
}
cout << equal_count << endl;
}
原文：http://www.cnblogs.com/ljxuan/p/3961117.html