Printable View
I'm supposed to write a program that uses recursive functions to print out all the possible outcomes when flipping a coin 'n' times. I've been told to try a binary tree, but we haven't learned those yet and I have no idea how to use them. I'm pretty stumped on this one, does anyone have any suggestions to get me started?
What, so you want to produce a function that prints:
Enter N: 2
heads heads
heads tails
tails heads
tails tails
I don't see how a binary tree will help here.
If N is relatively small (say less than 31), you could just use an integer to print the binary value as heads for zero and tails for one (or the other way around), and just count up to 2 to the power of n (or possibly down from the same).
[I presume we ignore "standing on it's side here". ]
--
Mats
the concept of permutations would be useful here. a permutation is basically the set of the different possible outcomes of an event. if you dont know set notation or what it is, take a quick look somewhere of what it is)
for example (code tag is used because required when using curly braces):the number of (uniquely ordered) outcomes for flipping a coin (which has 2 possibilities) n times is 2^n. that would be the theory of it. it isnt necessary for your program, but it may help to understand.Code:flipping the coin n=1 times gives the possible outcomes: {H, T}, 2 outcomes
flipping n=2 times gives the possible outcomes { (HH), (HT), (TT), (TH)}, 4 outcomes
flipping n=3 times gives outcomes: { (HHH), (HHT), (HTH), (HTT), (THH), (THT), (TTH), (TTT)}, 8 outcomes
printing these outcomes could be done recursively with a base case of two outcomes, "T" and "H". for example, to print out the outcomes with n=2 we could do:
printOutcomes(2) = (1st outcome 'T'): T + printOutcomes(2-1) = T + T, T + H
= (2nd outcome 'H'): H + printOutcomes(2-1) = H + T, H + H
where "+" denotes concatenation, ie "T + T" is "TT". notice the four outcomes are all of the possible ones, as listed earlier.
i hope im not being too vague that you cant understand, yet i hope im not being too explicit that i did the work for you.
I think I see what you're saying. I'll give it a try and see what I can come up with. Thanks!
If its using recursion then you want to start off calling the function twice. Once for heads; once for tails. You could have three parameters with a prototype something like:
'depth' would indicate how many times the function has been called. So, each time you call the function you increment it.Code:int heads_tails(int depth, int n, int head_or_tails);
'n' would be your target level of recursion. So, when depth == n you want to print the value. Otherwise keep recurring with two function calls; one for heads; one for tails.
'heads_or_tails' could be a boolean value indicating what side the coin landed on.I guess I cant say much more than that without giving you the code for it.
nadroj's points are very estute. You should also make a couple considerations about how you would do these permutations.Quote:
Originally Posted by nadroj
If you have a strongly devised formula to back up your program you can simply use the math as the driving force behind what should happen, and the rest simply becomes a matter of demonstration.
So if you know that the number of permutations for n will be 2^n then is it not safe to assume you could design your loop around that fact?
You can use some applied statistics too when you consider nadroj's example:
I arranged these so you can spot some pattersn. H will be in the first slot, 2^(n-1) times, right? The same is true for T. The reason these details are useful is because its a whole lot easier to be able to calculate these things in one shot than it is to have your program need to execute nested loops in order to physically render stats. Though I will conceed that on a modern computer either way will provide almost instant results. I am just hoping to steer you towards a general style of thinking.Quote:
Originally Posted by nadroj