Aldo Aldo - 1 month ago 4
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:

tree

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

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