Aldo - 1 year ago 53

C Question

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

What I have to do is consider all possible combinations of these operations and

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

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;

}

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

}

`#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: 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!!

Answer Source

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