Pseudocode recursive function
Solution 1
For the second question, you could use the law of total probability (transferred to expected values - you possibly have to search for this).
M(a)
denotes the number of glasses (as you suggested), E()
is the expected value of something. This law of total probability then yields:
E(M(a)) = sum(E(M(a) | b=i) * Pr(b=i), i=1..a-1) =
= ... =
= 1/(a-1) * (1+sum(E(M(i)+M(a-i), i=1..a-1)))
As far as I understood, the base case M(1)=0
holds.
If you transform the above recurrence relation and try it out (e.g. in a small python program), you should be able to recognize a simple pattern that possibly can be proven via induction.
Solution 2
The first answer is fine.
The second, however, is not. Consider a=1
. Your answer is two glasses or milk, whereas the correct answer is zero. Hint: Try working through some small examples by hand to get a feel for what's going on in the algorithm.
Solution 3
For your first question note that both expressions below are less than a, and recursion stops when a equals 1, and what can you observe about how many times milk() is called? Is it bounded?
b < a
a-b < a
MILK(1) returns (no recursion)
Work out the number of drinks of milk by hand for a couple of values, you will see a pattern. That will help.
Note that the random number generation adds complexity, but ask yourself, is the result any different if you pick b=1, b=2, b=a/2, or b=a-1?
Your answer is correct, but the above should help you explain your reasoning.
Once you have calculated the number of drinks for a couple of calls to MILK(v), you should be able to advance a formula for MILK(v) = formula(v).
Try MILK(3), MILK(4), MILK(5), MILK(9),
Note that Ruby can express your algorithm with little added syntax,
rdm = Random.new
def milk(a)
if(a==1) then
print "eat cookie\n";
else
print "drink milk\n";
b = Random.rand(1..a-1)
print "rand (1,#{a-1}) #{b}\n";
milk(b)
milk(a-b)
end
end
ARGV.each { |argi| milk(argi.to_i); }
pyramid
Updated on June 19, 2022Comments
-
pyramid over 1 year
I'm studying for my midterm and one of the practise questions asks:
Consider the recursive pseudo algorithm Milk(a), which takes as an input integer a>=1.
MILK(a) if a = 1; then eat cookie; else drink glass of milk; select a random integer b with 1 <= b <= a-1 MILK(b); MILK(a-b); endif
1) Explain why for any integer a>= 1 algorithm MILK(a) terminates
I think for this one because of the n-1, the possibility for m becomes smaller and smaller for the input into the recursive function MILK(b);, eventually reaching 1 which satisfies condition a = 1; therefore eating a cookie and so terminating the algorithm.
2) Let M(a) be the amount of glasses of milk you drink when running MILK(a). Determine the exact value of M(a)
For this one I assume it will be M(a) = a + a, since every time you run it 'a' is the input and adding every input together will give you the total.
How are my answers looking? Or this completely incorrect. Thank you!
-
pyramid about 10 yearsThanks, but can I say in B(n) = n + n - 1(total number of ns). So if it's 2 for example, it will be 2+2-2 as n will eventually hit 1? Sorry if my answer is a bit confusing.
-
Mashmagar about 10 years@pyramid Where did B(n) come from? Is that the same as M(a)?
-
pyramid about 10 yearsOh yea sorry, I looked at the wrong question. B(n) is the same as M(a). I meant M(a)= a + a -1