-5

I am stuck on this i will try to explain it by an example? Let say A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.

I am unsuccessful in writing any code that is why I am asking but I will try to explain my problem in c# way. I got list of int [1,2,3] out of this i need to find possible combination of 3 which can be 1+1+1, 1+2, 2+1. How do i achieve that in code?

Atul Chaudhary
  • 3,698
  • 1
  • 31
  • 51
  • 2
    Please try illustrating your problem with code. – kayess Feb 04 '16 at 14:10
  • @James Thorpe if u look at my question it is different from ur marked duplicate question response. I am asking about combination for given sum not just combination. I just dont know why people downvote question without even reading it :( – Atul Chaudhary Feb 04 '16 at 14:22
  • Once you have a way of enumerating all possible combinations, you can just sum each combination to see if it matches your target. – Matthew Watson Feb 04 '16 at 14:27
  • I just solved this using recursion - if you know what that concept is then I think that will be the easiest approach. At each recursive step, recurse down the next possible steps considering the steps already taken. Build up a list/dict/etc. of valid combinations while unwinding the recursive stack. This is a neat problem because once you solve it you can easily expand it to handle any step intervals & max distance. – Andrew_CS Feb 04 '16 at 15:01

1 Answers1

1

To give ourselves some ideas, let's start with illustrations.

Suppose the distance is 5 inches. s is step and j is jump. Then the solution would consist of:

5 steps solution:
s-s-s-s-s

4 steps solution:
s-s-s-j
s-s-j-s
s-j-s-s
j-s-s-s

3 steps solution:
s-j-j
j-s-j
j-j-s

And then another case when the distance is 4:

4 steps solution:
s-s-s-s

3 steps solution:
s-s-j
s-j-s
j-s-s

2 steps solution:
j-j

And another is when the distance is 6, we will have:

6 steps solution:
s-s-s-s-s-s

5:
s-s-s-s-j
s-s-s-j-s
s-s-j-s-s
s-j-s-s-s
j-s-s-s-s

4:
s-s-j-j
s-j-s-j
s-j-j-s
j-s-s-j
j-s-j-s
j-j-s-s

3:
j-j-j

Supposing the distance is D, from the illustration above, we can already derive few characteristics:

  1. The number of possible number of actions (A) is [D=6, A=4; D=5, A=3; D=4; A=3]. We can also easily find [D=3, A=2; D=2, A=2; D=1, A=1]

    Thus you see the pattern for A: 1,2,2,3,3,4. And for D:1,2,3,4,5,6. And you got your first relationship:

    A = int(D/2) + 1

  2. You also notice the next pattern. Take a look on the example for D=6. You have the following to count:

    6 steps: given 6 take 0    
5 steps: given 5 take 1    
4 steps: given 4 take 2    
3 steps: given 3 take 3

    Here you find another pattern: note that this is combination problems. The result for D=6 is given by:

    6C0 + 5C1 + 4C2 + 3C3

  3. Also note that, suppose combination is noted by aCb, a keeps decreasing from D to D-A+1 while b increase from 0 to A-1.

Now knowing those pattern syou could easily solve the problem by:

  1. Creating a for loop from D to D-A+1.
  2. In that for loop you have two vars: a and b. a keeps increasing, b keeps decreasing

  3. Create simple function which receives a & b and has operation of aCb.

    http://www.mathwords.com/c/combination_formula.htm

    aCb = a!/(b!(a-b)!)

  4. Sum the result in each loop of the for loop.

And you are done!

Ian
  • 30,182
  • 19
  • 69
  • 107