Recursive tree function?

Question

I have a task that I've been stuck with for too long. I should consider all possible expressions from 1 to N as follows:

n = 5; 1 % 2 % 3 % 4 % 5 = ? 

where % can be addition, subtraction or multiplication (+, -, *) I have to consider all possible combinations of these operations and calculate how many resulting expressions will be equal to n itself.

So, for example, for n = 4, the answer is 1, because there is only one expression equal to n.

 1 + 2 - 3 + 4 = 4 

There are a few cautions: multiplication is more strongly associated than the other two operations. For example,

 1 + 2 + 3 * 4 * 5 + 6 

need to analyze how

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

In addition, multiplication can be used only 5 times per line (not in general), therefore everything that is under n = 20 can be placed in integers. To solve this problem, I wrote this recursive tree, but with higher values ​​like n = 15, my result becomes wrong.

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

I’ve been trying to diagnose this for almost a week and can’t make it work properly ... I tried to make the code as readable as possible and comment on where it is needed. Just to explain what the code does - it creates a tree where (+, - and *) are branches at each iteration. Each node is the sum of the expression to this point, so when we reach depth = n, all the end nodes are all kinds of sums of the expression - all we need to do is check to see if they are equal to n. Illustrated below:

 #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; } 

UPDATE 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; } 

Changes: Fixed counters and initial values ​​in accordance with the answers (thanks!), But the program still produces incorrect results at high values, updated data:

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

The results are closer!

Answer 1

There are problems in your algorithm:

• mul counter must start at 0 .

• you should check the constraint with if (mul < 5) instead of if (mul % 5 != 0)

• you should always pass 0 when repeated for another statement.

Also note that global variables are recommended to be avoided, especially with short and meaningless names like n and result . It is better to use a state structure to which you pass the pointer.

Here is an improved version that can take an argument from the command line and prints solutions:

 #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) sn = strtol(argv[1], NULL, 0); else scanf("%i", &s.n); tree(&s, 1, 1, 0, 1, '\0'); printf("%i\n", s.result); return 0; } 

Answer 2

I'm not sure if this solves all the problems, but this is a mistake.

This code:

 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; } 

wrong.

First of all, you start with mul equal to 1. Thus, it will take the true branch for the following values: 1, 2, 3, 4

Thus, you get only 4 multiplications.

Try this instead:

 if (mul % 6 != 0) { //if multiplication hasn't been used 5x in a row ^ Notice... tree(depth, (sum - last) + (last * depth), mul + 1, last * depth); } 

Or better - don't use % - just use <

 if (mul < 5) { //if multiplication hasn't been used 5x in a row ^ Notice... tree(depth, (sum - last) + (last * depth), mul + 1, last * depth); } 

and start using mul equal to 0, i.e. tree(1, 1, 0, 1); .

Answer 3

The main problem that I see is that you are not resetting the mul counter. After you take the + or - branch, you must reset to allow 5 consecutive multiplications. One + or - breaks this line.

So, in addition to the answer reset from 4386427 (use the null option, I hope you find it less confusing), you will need

 tree(depth, sum + depth, 0, depth); tree(depth, sum - depth, 0, depth * -1); 

They acknowledge that the multithreaded sequence counter is currently 0.