数字序列和为0--一串数字添加符号使其结果为0

迷南。 2022-09-17 12:24 121阅读 0赞

**题目：序列123...N，N介于3和9之间，在其中加入+、-或者空格，使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问，如何获得所有组合？**

**思路：**

*  **由于N是从3至9的范围，解决方案就是针对每个N的取值，先计算三个分隔符“\_ + -”填入序列1-N的所有可能组合的情况总数**
 *  **设置所有情况的组合序列（采用3进制的思想，即set函数）**
 *  **对每种组合计算表达式值，如果为0则输出（利用栈&状态机，calculate函数）**

#include <stdio.h>
     
    /*
     * Initialize the string with 1 to 9 and seperated by whitespace
     * for len in range(3, 9+1):
     *    for each possibility of seperators:
     *        calculate the result, if it's zero, output
     */
     
    int calculate(char input[], int n)
    {
        //Use a simple state machine to interpret the input as an expression
        int stack[3] = {0}, sp = 0, i = 0;
        for(; i < n*2-1; ++i)
        {
            switch(input[i])
            {
            case ' ':
                stack[sp] = stack[sp]*10;
                break;
            case '+':
            case '-':
                if(sp == 0)
                {
                    stack[1] = input[i];
                    sp = 2;
                }else
                {
                    stack[0] = stack[0]+(stack[1]=='-' ? -1 : 1)*stack[2];
                    stack[1] = input[i];
                    stack[2] = 0;
                }
                break;
            default: //digits
                stack[sp] += input[i]-'0';
                break;
            }
        }
        if (sp == 2)
        {
            stack[0] = stack[0]+(stack[1]=='-' ? -1 : 1)*stack[2];
        }
        return stack[0];
    }
     
    void set(char str[], int n, int num)
    {
        //Transform num into base3 to generate the presentation of seperators
        int sp;
        char choice[] = " +-";
        for(sp = (n-1)*2-1; sp > 0; sp -=2)
        {
            str[sp] = choice[num%3];
            num /= 3;
        }
    }
     
    void result0()
    {
        char str[18] = "1 2 3 4 5 6 7 8 9";
        int n, sp, all;
        for (n = 3; n <= 9; ++n)  // 3-9
        {
            all = 1;
            for (sp = 1; sp < n; ++sp) //Count the num of possibilities on 1-n
            {
                all *= 3;
            }
            while(all)
            {
                set(str, n, --all);
                if (calculate(str, n) == 0)
                {
                    str[n*2-1] = '\0';
                    printf("%s = 0\n", str);
                }
            }
        }
    }
     
    int main()
    {
        result0();
        return 0;
    }

**代码说明：**

**对于每个N，先计算出所有可能组合情况的数目，然后根据所有的情况数目all，将\[1,all\]的值传给函数set，并根据每个数值的三进制（分隔符只有三种情况，如果是四种分隔符，那就是四进制了）表示为str赋值。**

for (sp = 1; sp < n; ++sp)
    {
        all *= 3;
    }
    while(all)
    {
        set(str, n, --all);
    ......

**    Set函数的本质是将每一种分隔符的排列情况映射为一个整数（即1-all之间的数字），由于这些数字是连续的，而连续的整数转换为某个进制上的表示是不会有重复的，故遍历这个区间，就可以通过进制转换表示出所有的可能，有多少个数被转换，就能输出多少种可能。当元素有k种取值、总共n种情况时都可以用这一招！！**

**    Calculate函数就是计算每一种set后的表达式值，采用了简单的自动机思想和简单的栈（数组）。值得说明的是，calculate程序程序的功能是计算中缀表达式的值，因此需要使用栈来保存操作数的值。由于题目中操作符只有加和减，两者是同一优先级的，因此可以直接简化为一个从左向右的扫描过程，同时栈只需要保存两个操作数的值即可（所以stack数组的长度才是3，其中一个用于保存操作符）。如果运算符不止一个优先级，那么栈就必须是变长了，而且需要一个独立的操作符栈，同时执行过程就会是中缀转后缀的算法了。因此这个函数是针对题目的特定优化和简化。**

**ps:[这是从网上看到的一个方法][Link 1]，确实很好，这里还是想分析一下其中的奥妙。**

**    下面还有一个比较纯粹的解法，使用的深度优先搜索：**

#include <iostream>
    #include <string>
    using namespace std;
     
    /* parameter description
     *
     * N，1-N 的数字串
     * k，处理到第几个字符了,k范围[1-N]
     * val，当前表达式的值
     * result，结果字符串
     * pre，记录前一个操作符，用于遇到空格时考虑
     */
    void dfs(int N, int k, int val, string& result, char pre)
    {
        if(k > N)
        {
            if(val == 0)
            {
                printf("%s\n", result.c_str());
            }
            return;
        }
        /* deal space */
        int val_space = val;
        if(pre == '-')
        {
            val = val+(k-1)-((k-1)*10+k); //在上一次的操作上，首次是符号入栈 然后是数字如栈 在这里需要将上一次的数字转换
        }else if(pre == '+')
        {
            val = val-(k-1)+((k-1)*10+k);
        }else
        {
            val = val * 10 + k;
        }
        result.push_back(' ');
        result.push_back(k + '0');
        dfs(N, k+1, val, result, ' ');
     
        val = val_space;
        result.pop_back();
        result.pop_back();
     
        /* deal + */
        val += k;
        result.push_back('+');
        result.push_back('0' + k);
        dfs(N, k+1, val, result, '+');
     
        val -= k;
        result.pop_back();
        result.pop_back();
     
        /* deal - */
        val -= k;
        result.push_back('-');
        result.push_back('0' + k);
        dfs(N, k+1, val, result, '-');
     
        val += k;
        result.pop_back();
        result.pop_back();
    }
     
    void main()
    {
        string res = "1";
        for(int i = 3; i <= 9; ++i)
        {
            dfs(i, 2, 1, res, ' ');
        }
    }

**    这个思路就非常简单了，就是使用基本的搜索的方法来计算最终的结果是否有0.如果有0**

[Link 1]: http://www.ahathinking.com/archives/210.html#respond