CODEWITHSUNDEEP
calgorithmcombinations
parmanand
parmanand

Reputation: 478

Finding possible combinations of 1 and 2 with a constant sum

This is a task to be done in C. Can you tell me how to approach this?

A train has a length of n meters. It is made up of individual compartments of 1 or 2 meters in length. How many different combinations of such compartments exist for a train of a given length? Write a function Train (n) that computes this.

Upvotes: 1

Views: 529

Answers (3)

Svante
Svante

Reputation: 51501

Start with the simplest cases and look for regularities.

  1. Train (1) is obviously 1: (1).
  2. Train (2) is obviously 2: (1 1) and (2).
  3. Train (3) is 3: (1 1 1), (1 2), and (2 1). The first two can be combined into conjoining (1) with (1 1) resp (2). The latter are exactly the combinations of Train (2). So, Train (3) is Train (2) + 1.
  4. Train (4) is 5: (1 1 1 1) (1 1 2) (1 2 1) (2 1 1) (2 2). Again, we can combine the first as (1) with (1 1 1), (1 2), and (2 1), which are the combinations of Train (3). The last are (2) conjoined with (1 1) and (2), which are the combinations of Train (2). So, Train (4) is Train (3) + Train (2). Now, looking back at Train (3), we see that the + 1 is Train (1).

Now it seems clear that Train (n) is always Train (n - 1) + Train (n - 2). That is exactly the definition of the Fibonacci sequence.

Now, let us see how that is translated to C.

  1. The function skeleton: Train takes one integer argument and returns an integer:

    int Train (int n) {
}

  2. The definition we worked out:

    int Train (int n) {
    return Train (n - 1) + Train (n - 2);
}

  3. This will recurse infinitely, so we need to stop it at the base case. One base case is clear: Train (1) is 1:

    int Train (int n) {
    if (n == 1) {
        return 1;
    } else {
        return Train (n - 1) + Train (n - 2);
    }
}

  4. This is still not enough. Imagine what Train (2) does: it will calculate Train (1) + Train (0). Train (1) is no problem, but Train (0) will calculate Train (-1) + Train (-2), which again recurses infinitely. So, we need another base case: Train (2) is 2.

    int Train (int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return Train (n - 1) + Train (n - 2);
    }
}

  5. This works, but we can simplify the base cases:

    int Train (int n) {
    if (n < 3) {
        return n;
    } else {
        return Train (n - 1) + Train (n - 2);
    }
}

  6. If you now just paste that last code snippet into your homework without working through the "too long, didn't read" preliminaries, I have successfully undermined your education, and you will never learn to program. You are welcome.

  7. This is not the best way to calculate Fibonacci numbers. Why? How should you modify the code to avoid duplication of effort? Are there different approaches imaginable? Which ones?

Upvotes: 2

Noray
Noray

Reputation: 165

I guess this recursive formula answers the question

if (n <= 2) return n
Train(n) = Train(n-1) + Train(n-2)

Upvotes: 0

Nikita Rybak
Nikita Rybak

Reputation: 67986

That's a simple fibonacci sequence.
For any train of length n first cart can be of length 1 or 2. That brings us to f(n) = f(n - 1) + f(n - 2) formula.

I probably don't have to tell you how to calculate fibonacci numbers.

Upvotes: 0

Related Questions