Basic Recursion Exercise
My teacher gave me an exercise on recursion (I think so), and the task is as below:
Given 3 integers, N, T and P.
N represents the number of blanks.
T represents the total amount of all blanks.
P represents the minimum amount of each blank.
If N=3, T=34 and P=10, there will be 15 possible ways to fill the blanks:
14 10 10
13 11 10
13 10 11
12 11 11
12 10 12
11 11 12
11 10 13
10 11 13
10 10 14
11 12 11
10 12 12
12 12 10
10 13 11
11 13 10
10 14 10
My biggest problem is on the recursion part, can somebody please help? Thanks a lot!
Given 3 integers, N, T and P.
N represents the number of blanks.
T represents the total amount of all blanks.
P represents the minimum amount of each blank.
If N=3, T=34 and P=10, there will be 15 possible ways to fill the blanks:
14 10 10
13 11 10
13 10 11
12 11 11
12 10 12
11 11 12
11 10 13
10 11 13
10 10 14
11 12 11
10 12 12
12 12 10
10 13 11
11 13 10
10 14 10
My biggest problem is on the recursion part, can somebody please help? Thanks a lot!
lolz.
You're not being very specific in your question...
|
|
You're not being very specific in your question...
Recursion way:
You only need to calculate values for P*N < T (if P*N < T there are zero possibilities). Otherwise you'll need a recursive function something like this:
more involved than I initially thought, should be possible if you have to use recursion. Think you need to pass three values to a recursive function, one the number of blanks left, one the value T - P*N, and a pointer/reference to keep track of the possibilities
Math way:
This is equivalent to a probability problem where you have to distribute identical balls into urns. From the arguments given N represents the number of urns and T - P*N the number of balls. Note that if P*N > T there are zero possibilities as there are not enough balls. It can be shown that the number of possible distributions for such a setup is:
possible = (T - P*N + N - 1)C(N-1)
where aCb is the binomial coefficient a! / ((a-b)!b!)
If you want me to explain this seemingly magical equation let me know. Also ! means "factorial" if you are unfamiliar with the notation.
So for the example given we have:
(34 - 10*3 + 3 - 1)C(3-1) = (34 - 30 + 3 - 1)C(3-1) = 6C2 = 6! / ((6-2)!2!) = 6*5 / 2 = 15
So you can do this problem by calculating binomial coefficients. Now since we're working with computers instead of pure mathematics you'll want to keep the numbers you work with as small as possible when calculating the coefficients. Say you have 50C47. That's equivalent to (50*49*48) / (3*2*1). You could calculate the 50*49*48 first, then divide by 3*2*1, but this leads to overflowing numbers quickly. Alternatively you could calculate 50/3 first then multiply by 49/2 the multiply by 48/1, which gives the same result. Note that you'll need to do double division then convert to int to avoid truncating values. Also note that even using this method you'll eventually lose precision as double only guarantees a limited amount of precision, but for your assignment this shouldn't be an issue.
Finally to be excessively pedantic you could use a library which gives arbitrary precision to your double values so you don't lose precision even for very large binomial coefficients, but that's a little much for this assignment.
You only need to calculate values for P*N < T (if P*N < T there are zero possibilities). Otherwise you'll need a recursive function something like this:
more involved than I initially thought, should be possible if you have to use recursion. Think you need to pass three values to a recursive function, one the number of blanks left, one the value T - P*N, and a pointer/reference to keep track of the possibilities
Math way:
This is equivalent to a probability problem where you have to distribute identical balls into urns. From the arguments given N represents the number of urns and T - P*N the number of balls. Note that if P*N > T there are zero possibilities as there are not enough balls. It can be shown that the number of possible distributions for such a setup is:
possible = (T - P*N + N - 1)C(N-1)
where aCb is the binomial coefficient a! / ((a-b)!b!)
If you want me to explain this seemingly magical equation let me know. Also ! means "factorial" if you are unfamiliar with the notation.
So for the example given we have:
(34 - 10*3 + 3 - 1)C(3-1) = (34 - 30 + 3 - 1)C(3-1) = 6C2 = 6! / ((6-2)!2!) = 6*5 / 2 = 15
So you can do this problem by calculating binomial coefficients. Now since we're working with computers instead of pure mathematics you'll want to keep the numbers you work with as small as possible when calculating the coefficients. Say you have 50C47. That's equivalent to (50*49*48) / (3*2*1). You could calculate the 50*49*48 first, then divide by 3*2*1, but this leads to overflowing numbers quickly. Alternatively you could calculate 50/3 first then multiply by 49/2 the multiply by 48/1, which gives the same result. Note that you'll need to do double division then convert to int to avoid truncating values. Also note that even using this method you'll eventually lose precision as double only guarantees a limited amount of precision, but for your assignment this shouldn't be an issue.
Finally to be excessively pedantic you could use a library which gives arbitrary precision to your double values so you don't lose precision even for very large binomial coefficients, but that's a little much for this assignment.
Topic archived. No new replies allowed.