coin flipping

This is a discussion on coin flipping within the C Programming forums, part of the General Programming Boards category; I'm supposed to write a program that uses recursive functions to print out all the possible outcomes when flipping a ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Location
    Orlando, Florida
    Posts
    22

    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?

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Location
    Orlando, Florida
    Posts
    22
    I think I see what you're saying. I'll give it a try and see what I can come up with. Thanks!
    Last edited by MiroMage; 10-01-2008 at 06:14 PM.

  5. #5
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    Post

    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.

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote 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:
    Quote 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. flipping number question..
    By transgalactic2 in forum C Programming
    Replies: 4
    Last Post: 12-09-2008, 08:02 AM
  2. coin toss
    By ejd81882 in forum C Programming
    Replies: 3
    Last Post: 10-14-2008, 12:53 PM
  3. Problems with a simple coin flipping program
    By Thileepan_Bala in forum C Programming
    Replies: 14
    Last Post: 01-18-2008, 07:33 PM
  4. Another Coin Counting Program
    By MipZhaP in forum C++ Programming
    Replies: 4
    Last Post: 01-21-2005, 01:02 AM
  5. Stack functions as arrays instead of node pointers
    By sballew in forum C Programming
    Replies: 8
    Last Post: 12-04-2001, 10:13 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21