2
$\begingroup$

I want to find out what this algorithm is called

int s(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    } else if (n >= m) {
        return s(m, m - 1) + 1;
    } else {
        return s(m - n, n) + s(m, n - 1);
    }
}

table

I think it counts possible sums with limited summands

like s(5,5)=7

  1. 1+1+1+1+1
  2. 2+1+1+1
  3. 2+2+1
  4. 3+1+1
  5. 3+2
  6. 4+1
  7. 5
$\endgroup$
  • $\begingroup$ This algorithm is obviously called s. I think what you really want to ask it what the value it computes represents in terms of the values of $m$ and $n$. $\endgroup$ – Marc van Leeuwen Jun 5 '13 at 12:14
  • $\begingroup$ It may also be noted that in the table the value of $m$ increases horizontally, the value of $n$ vertically. $\endgroup$ – Marc van Leeuwen Jun 5 '13 at 12:15
0
$\begingroup$

Found a solution:

for (int y = 1; y <= m; y++) {
    for (int x = 1; x <= m; x++) {

        if (x == 1 || y == 1) {
            arr[y][x] = 1
        } else if (x == y) {

            arr[y][x] = arr[y - 1][x] + 1

        } else if (y > x) {
            arr[y][x] = arr[y - 1][x]

        } else if (x > 1 && y > 1) {

            arr[y][x] = arr[y - 1][x] + arr[y][x - y]
        }   

    }

}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.