华为校招一道上机题：等式变换

傷城~ 2022-09-29 12:55 170阅读 0赞

参考来源：[http://blog.csdn.net/Hackbuteer1/article/details/39253767][http_blog.csdn.net_Hackbuteer1_article_details_39253767]

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

**解题思路：**

后续级数很多，但都只有三种选择，加，减，连接符，肯定要用递归要解决。

#include<iostream>  
    #include<cstdio>  
    using namespace std;  
    
    int ops[21];  
    const char sym[3] = {'+' , '-' , ' '};  
    int result , num;  
    
    void dfs(int layer, int currentResult, int lastOp, int lastSum)  
    {  
        lastSum *= (layer > 9) ? 100 : 10;  
        lastSum += layer;  
        if(layer == 9)  
        {  
            currentResult += (lastOp) ? (-1 * lastSum) : lastSum;  
            if(currentResult == result)  
            {  
                ++num;  
                printf("1");  
                for(int i = 2 ; i <= 9 ; ++i)  
                {  
                    if(sym[ops[i-1]] != ' ')  
                        printf(" %c ", sym[ops[i-1]]);  
                    printf("%d", i);  
                }  
                printf(" = %d\n" , result);  
            }  
            return;  
        }  
        ops[layer] = 2;  
        dfs(layer + 1 , currentResult , lastOp , lastSum);   //Continue  
        currentResult += (lastOp)? (-1 * lastSum) : lastSum;  
        ops[layer] = 0;  
        dfs(layer + 1 , currentResult , 0 , 0);  //Plus  
        ops[layer] = 1;  
        dfs(layer + 1 , currentResult , 1 , 0);  //Minus  
    }  
    
    int main(void)  
    {  
        while(scanf("%d", &result) != EOF)  
        {  
            num = 0;  
            dfs(1 , 0 , 0 , 0);  
            printf("%d\n" , num);  
        }  
        return 0;  
    }

[http_blog.csdn.net_Hackbuteer1_article_details_39253767]: http://blog.csdn.net/Hackbuteer1/article/details/39253767