华为机试等式变换

【华为机试】等式变换

问题描述

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

c 代码

// An highlighted block
#include <iostream>
#include <string>
using namespace std;

void dfs(int* a, int index, int subsum, int subsum1, int x, int* count, string s) {
    if (index == 8) {
        subsum = subsum   subsum1;
        if (subsum == x) {
              count[0];
            cout << s << endl;
        }
        return;
    }
    // op = ' '  
    dfs(a, index   1, subsum, subsum1 > 0 ? (10 * subsum1   a[index   1]) : (10 * subsum1 - a[index   1]), x, count, s   to_string(a[index   1]));
    // op = ' '
    dfs(a, index   1, subsum   subsum1, a[index   1], x, count, s   ' '   to_string(a[index   1]));
    // op = '-'
    dfs(a, index   1, subsum   subsum1, -a[index   1], x, count, s   '-'   to_string(a[index   1]));
}


int main(int argc, const char** argv)
{
    int a[9] = { 1,2,3,4,5,6,7,8,9 };
    int x;
    string s;
    s = "1";
    int count[1] = { 0 };
    while (cin >> x) {
        dfs(a, 0, 0, 1, x, count, s);
        cout << count[0] << endl;
    }
    return 0;
}

这篇好文章是转载于：学新通技术网