Birthday Problem

Discussion in 'C++' started by Sandra, Apr 12, 2004.

  1. Sandra

    Sandra Guest

    I was given this problem for extra credit and I am just stuck !
    BTW - I am not asking for source code and I am not asking anyone to do
    my homework as I do want to learn .. I just need a hint or two to get
    moving and I need to know if what I have written so far is leading me
    in the right direction ~

    Ok - The problem is to find out how many people need to be in a room
    for a 95% chance that someone in that room will match my birthday

    I wrote a program that will calculate that percentage for any 2
    bithdays to match, but that is not the same thing :)

    Here is what I have so far:


    #include "stdafx.h"
    #include <time.h>
    #include <iostream>
    using namespace std;

    int _tmain(int argc, _TCHAR* argv[])
    {
    int sample[1000];
    int i=1,j=1;
    int a =0;
    srand( (unsigned)time( NULL ) );

    while (a != 325)
    { sample=rand()%365+1;
    //cout<<" "<<sample;
    a = sample;
    i++;
    if (a==325) cout<<"\n\n\n Match "<<a<<" at "<<i<<"\n";
    }

    return 0;

    This puts random numbers from 1-365 in an array - reads the array and
    tries to detect an exact match
    The problem is that the match is so random - how do I come up with a
    95% chance? Is there any exact answer ?

    As I said - just need some hints to move along..

    Any replies will be appreciated,

    Thanks,

    Sandra
     
    Sandra, Apr 12, 2004
    #1
    1. Advertisements

  2. Sandra

    osmium Guest

    You are off to a bad start. There are two ways to approach this, simulate
    it and compute it. I think your instructor want you to compute it and you
    are simulating.

    Given a bazillion people in a room.
    The fist person will not match anyone. The next person will have a
    *different* birthday with probability 364/365. The next 363/365. And so on.

    Now write a program, monitoring for the 95% threshold as you go. I think
    there is an algorithm *too* but I don't think that is wanted here.

    Yes, there is an exact answer to the question posed.
     
    osmium, Apr 12, 2004
    #2
    1. Advertisements



  3. This is a problem that should be solved analytically rather than with brute
    force, unless you were specifically told to use brute force. If it's the
    latter, consider a naive way to do it by hand: check the probability if the
    group is of size 1. Then check if the group is of size 2. And so on, until
    you hit 95%. There are more sophisticated ways to search that space, but
    you're better off taking things one step at a time (no pun intended). Again,
    if you have a choice, solve it analytically (any beginning text on
    probabilities will have that very example).

    Claudio Puviani
     
    Claudio Puviani, Apr 12, 2004
    #3
  4. Sandra

    John Carson Guest


    Right answer to the wrong question.
     
    John Carson, Apr 12, 2004
    #4
  5. The following code, I believe, calculates the number of people that
    must be in a room for there to be a 95% chance that at least two
    people will have the same birthday - perhaps you can make use of the
    general idea for your problem. Or perhaps I will prove to be very
    wrong, in which case you should not listen to me ;)

    #include <iostream>

    using namespace std;

    int main(void)
    {
    int i=366; // includes February 29
    while( (float)i/(float) 366 > .05 )
    i--;
    cout << "The number is " << i << "\n";
    return 0;
    }
     
    Christopher Benson-Manica, Apr 12, 2004
    #5
  6. Sandra

    Buster Guest

    It's Step One of a correct solution.
     
    Buster, Apr 12, 2004
    #6
  7. Holy cow, maybe I should go to lunch and get some blood sugar back in
    me - that code is REALLY wrong!!! I guess on the bright side I don't
    have to feel guilty about giving you undue help... I'd post something
    closer to the correct answer, but I don't think I trust myself after
    that egregious blunder. Sorry :(
     
    Christopher Benson-Manica, Apr 12, 2004
    #7
  8. Sandra

    Julie Guest

    Are you supposed to calculate the answer, or (simulated) empirically
    determine? From the looks of your code, it looks like you are going the
    empirical route.
     
    Julie, Apr 12, 2004
    #8
  9. * (Sandra) schriebt:
    I think it would be better if you posted the exact assignment, because
    as stated there is nothing involving C++ or even programming. With n
    persons in the room the chance that none of them matches your birthday
    is simply (364/365)^n (you need to think of it this way to get logical
    "and" for simple multiplication of probabilities), so the chance that at
    least one of them match is <censored/>; with the treshold at 0.95 that
    gives 0.95 = <censored/> thus n = <censored/> ~= 1091.94. Thus


    #include <iostream>
    int main() { std::cout << 1092 << std::endl; }


    would be one solution program, or perhaps


    #include <iostream>
    int main() { std::cout << 1091 + 1 << std::endl; }


    if the text requires "computation", but I can't imagine that's what the
    problem is about.

    So please do post the exact assignment text.

    You absolutely don't need that.

    In C++ write


    #include <ctime>


    but you don't need that either, unless it's really a requirement to use
    Monte Carlo method or some such.

    In standard C++ this is not a valid 'main' function. In standard
    C++ one possible declaration of the 'main' function is


    int main()


    As for the rest of the code, as others have replied it's doubtful
    that the intention is to do a simulation.

    But that of course depends on the exact text of the assignment.
     
    Alf P. Steinbach, Apr 12, 2004
    #9
  10. Sandra

    osmium Guest

    There is not any exact answer by using the Monte Carlo simulation you are
    started on. You could compute till doomsday and you still wouldn't have an
    exact answer. That's one reason why analysis is preferred to simulation in
    simple problems such as this. Also, simulation doesn't give you much in the
    way of insight into the problem and what a a good solution might be. In
    general, in real problems, simulation is much easier than analysis.
     
    osmium, Apr 12, 2004
    #10
  11. FWIW, here is something that might actually compute the correct
    answer. Yeesh, Mondays...

    #include <iostream>

    using namespace std;

    int main(void)
    {
    int i=366; // includes February 29
    double numerator=i, denominator=i;
    while( numerator/denominator > .05 ) {
    numerator*=--i;
    denominator*=366;
    }
    cout << "The number is " << 366-i+1 << "\n";
    return 0;
    }
     
    Christopher Benson-Manica, Apr 12, 2004
    #11
  12. Please DO NOT post what you think is a complete answer to someone
    else's homework problem.

    I shall not call you an idiot, moron, etc., here.

    But I reserve the right to hold that opinion, and be advised that's the
    opinion most will (very privately) have on seeing such a posting.
     
    Alf P. Steinbach, Apr 12, 2004
    #12
  13. But I don't think it's complete - it solves a subtly different
    problem, and perhaps a really different problem :)
    I would hope that if I'm annoying people, they'd just tell me - I'm
    very bad at catching subtle hints :(
     
    Christopher Benson-Manica, Apr 12, 2004
    #13
  14. You can be sure that at least I will be very clear about such things... ;-)
     
    Alf P. Steinbach, Apr 12, 2004
    #14
  15. And I won't mind it a bit :)
     
    Christopher Benson-Manica, Apr 12, 2004
    #15
  16. Sandra

    Erik Guest

    I was given this problem for extra credit and I am just stuck !
    #include <math.h>
    #include <iostream>

    const bool i_am_born_on_feb_29 = false;

    int main() {
    std::cout << (int)std::ceil(std::log(0.05) /
    (std::log(i_am_born_on_feb_29 ? 365.0 : 364.25) - std::log(365.25)));
    }
     
    Erik, Apr 12, 2004
    #16
  17. Please DO NOT post what you think is a complete answer to someone
    else's homework problem.

    Be advised most people, on seeing such a posting, will think of you as an
    an uncaring Swedish idiot -- and certainly I do.

    Perhaps that's why you're posting anonymously?
     
    Alf P. Steinbach, Apr 12, 2004
    #17
  18. Sandra

    John Carson Guest


    Perhaps. Provided you are prepared to go around the world a couple of times
    in order to get there.
     
    John Carson, Apr 12, 2004
    #18
  19. Sandra

    Erik Guest

    Please DO NOT post what you think is a complete answer to someone
    I don't think his teacher will accept that answer, unless he's studying
    mathematics, in which case he probably wouldn't ask in this NG.

    If he can't solve a problem like that analytically, he will most definitely
    fail his mathematics classes.

    And if he does hand in my suggestion, the teacher will hopefully learn
    from his mistake and create a more meaningful question for next year
    (one that can't be more easily solved using mathematics than programming).
    I guess this assignment was part of the first programming class, in which
    it is important to show the students what programming can be used for,
    not teach more complex methods to solve simple mathematical problems.

    However, I did give him one hint (that he must handle the Feb 29 case).

    You can see me as anything you want to, but not many others do.
    That's more of a religious issue. I don't like giving out my name, and
    certainly not my email address, on the internet.
     
    Erik, Apr 12, 2004
    #19
  20. Are you sure that Sandra is a "he"?

    You're an idiot all right.

    Did you notice that Sandra wrote


    I am not asking for source code and I am not asking anyone to do
    my homework as I do want to learn


    Did you read the FAQ before posting,


    <url: http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2>


    as you're required to do?

    Perhaps your English is not quite up to the task? What kinds of
    moron students are they admitting these days at Lund's?

    That's quite understandable.
     
    Alf P. Steinbach, Apr 12, 2004
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.