Thread: coin flipping

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?

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):

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

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.

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.

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:

Code:

int heads_tails(int depth, int n, int head_or_tails);

'depth' would indicate how many times the function has been called. So, each time you call the function you increment it.

'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.

Originally Posted by nadroj

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.

nadroj's points are very estute. You should also make a couple considerations about how you would do these permutations.

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:

Originally Posted by nadroj

(HHH)(TTT)
(HHT)(TTH)
(HTH)(THT)
(HTT)(THH)

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.