递归树函数？

Question

我有一项任务,我已经坚持了太久.我应该考虑从1到N的所有可能的表达式,如下所示:

n = 5;

1 % 2 % 3 % 4 % 5 = ?

其中%可以是加法,减法或乘法(+, - ,*)我要做的是考虑这些操作的所有可能组合,并计算结果表达式等于n本身的数量.

因此,例如,对于n = 4,答案是1,因为只有一个表达式等于n.

1 + 2 - 3 + 4 = 4

还有一些注意事项 - 乘法比其他两个操作更强大.所以举个例子

1 + 2 + 3 * 4 * 5 + 6 

需要解析为

1 + 2 + (3 * 4 * 5) + 6

此外,乘法只能用一个最大的5次连续(而不是在全部),所以任何下N = 20将能够适应整数.为了解决这个问题,我编写了这个递归树,但是在更高的值(例如n = 15)时,我的输出变得不正确.

[N ] - [Expected result] [My program's result]
[5 ] - [              3] [                  3] 
[6 ] - [              1] [                  1]
[9 ] - [             27] [                 27]
[15] - [           3932] [               3911]
[16] - [           9803] [               9327]
[17] - [          23209] [              22942]

我一直在尝试诊断这个差不多一个星期而且无法让它正常工作......我试图使代码尽可能可读并在必要时进行评论.只是为了解释代码的作用 - 它构建了一个树,其中(+, - 和*)是每次迭代的分支.每个节点是直到该点的表达式的总和,因此当我们达到depth = n时,所有结束节点都是可能的表达式总和 - 我们所要做的就是检查它们是否等于n.如下图所示:

#include <stdio.h>

int n;
int result = 0;

void tree(int depth, int sum, int mul, int last) {
    //DEPTH = recursion from 1 to n
    //SUM = the sum of the expression
    //MUL = counter to track how many consecutive multiplications have been done
    //LAST = previous number added to sum

    //if n nodes reached
    if (depth == n) {
        if (sum == n) {
            //count result
            result++;
        }
        return;  
    }
    //build tree
    depth++;
    if (mul % 5 != 0) { //if multiplication hasn't been used 5x in a row
        tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
    } else {
        //else dont build a multiplication branch, but reset the counter
        mul = 1;
    }
    //build addition and subtraction trees
    tree(depth, sum + depth, mul, depth);
    tree(depth, sum - depth, mul, depth * -1);
}

int main(int argc, char **argv) {
    scanf("%i", &n);
    tree(1, 1, 1, 1);
    printf("%i\n", result);
    return 0;
}

更新1:MUL COUNTER CORRECTED

#include <stdio.h>

int n;
int result = 0;

void tree(int depth, int sum, int mul, int last) {
    //DEPTH = recursion from 1 to n
    //SUM = the sum of the expression
    //MUL = counter to track how many consecutive multiplications have been done
    //LAST = previous number added to sum

    //if n nodes reached
    if (depth == n) {
        if (sum == n) {
            //count result
            result++;
        }
        return;  
    }
    //build tree
    depth++;
    if (mul < 5) { //if multiplication hasn't been used 5x in a row
        tree(depth, (sum - last) + (last * depth), mul + 1, last * depth);
    } else {
        //else dont build a multiplication branch, but reset the counter
        mul = 0;
    }
    //build addition and subtraction trees
    tree(depth, sum + depth, mul, depth);
    tree(depth, sum - depth, mul, depth * -1);
}

int main(int argc, char **argv) {
    scanf("%i", &n);
    tree(1, 1, 0, 1);
    printf("%i\n", result);
    return 0;
}

更改:根据答案更正了计数器和起始值(谢谢!),但程序在高值时仍会产生错误的结果,更新数据:

[N ] - [Expected result] [My program's result]
[5 ] - [              3] [                  3] 
[6 ] - [              1] [                  1]
[9 ] - [             27] [                 27]
[15] - [           3932] [               3924]
[16] - [           9803] [               9781]
[17] - [          23209] [              23121]

结果更接近!!

Answer 1

你的算法有问题：

• 计数器mul应从 开始0。

• 你应该测试约束if (mul < 5)而不是if (mul % 5 != 0)

• 0当您递归不同的运算符时，您应该始终通过。

另请注意，建议避免全局变量，尤其是像 和 这样简短且无意义的n名称result。最好使用向其传递指针的状态结构。

这是一个改进的版本，可以从命令行获取参数并打印解决方案：

#include <stdio.h>
#include <stdlib.h>

struct state {
    int n;
    int result;
    char ops[20];
};

void print_exp(struct state *sp, int depth, int sum) {
    for (int i = 1; i < sp->n; i++) {
        printf("%d %c ", i, sp->ops[i]);
    }
    printf("%d = %d\n", sp->n, sum);
}

void tree(struct state *sp, int depth,int sum, int mul, int last, char op) {
    // DEPTH = recursion from 1 to n
    // SUM = the sum of the expression
    // MUL = counter to track how many consecutive multiplications have been done
    // LAST = previous number added to sum

    //if n nodes reached
    sp->ops[depth - 1] = op;
    if (depth == sp->n) {
        if (sum == sp->n) {
            //count result
            sp->result++;
            print_exp(sp, depth, sum);
        }
        return;
    }
    depth++;
    if (mul < 5) { //if multiplication hasn't been used 5x in a row
        // recurse with a multiplication
        tree(sp, depth, (sum - last) + (last * depth), mul + 1, last * depth, '*');
    }
    // recurse with addition and subtraction operators
    tree(sp, depth, sum + depth, 0, depth, '+');
    tree(sp, depth, sum - depth, 0, -depth, '-');
}

int main(int argc, char **argv) {
    struct state s = { 0, 0, "" };

    if (argc > 1)
        s.n = strtol(argv[1], NULL, 0);
    else
        scanf("%i", &s.n);
    tree(&s, 1, 1, 0, 1, '\0');
    printf("%i\n", s.result);
    return 0;
}