Aldo - 1 year ago 64
C Question

# Recursive tree function?

I have an assignment I've been stuck on for too long. I'm supposed to consider all possible expressions from 1 to N like this:

``````n = 5;

1 % 2 % 3 % 4 % 5 = ?
``````

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

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

``````1 + 2 - 3 + 4 = 4
``````

There is also a couple more caveats to this - multiplication binds stronger than the other two operations. So for example

``````1 + 2 + 3 * 4 * 5 + 6
``````

needs to be parsed as

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

Additionally, multiplication can only be used a maximum of 5 times in a row (not in total), so anything under n=20 will be able to fit in integers.
To tackle this problem I wrote this recursive tree, but at higher values such as n=15 my output becomes incorrect.

``````[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]
``````

I've been trying to diagnose this for almost a week and can't get it working properly... I tried to make the code as readable as possible and commented where necessary. Just to explain what the code does - it builds a tree where the (+,- and *) are branches each iteration. Each node is the sum of the expression up to that point, so when we reach depth = n, all of the ending nodes are all possible expression sums - all we have to do is check if they 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;
}
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;
}
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: Corrected the counter and starting values in accordance to answers (thank you!), but the program still produces incorrect results at high values, updated data:

``````[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]
``````

The results are closer!!

There are problems in your algorithm:

• the `mul` counter should start at `0`.

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

• you should always pass `0` when you recurse for a different operator.

Note also that it is recommended to avoid global variables, especially with such short and meaningless names as `n` and `result`. It is better to use a state structure to which you pass a pointer.

Here is an improved version that can take the argument from the command line and prints the 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)
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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download